Timezone: »
Poster
Rate-Optimal Subspace Estimation on Random Graphs
Zhixin Zhou · Fan Zhou · Ping Li · Cun-Hui Zhang
We study the theory of random bipartite graph whose adjacency matrix is generated according to a connectivity matrix $M$. We consider the bipartite graph to be sparse, i.e., the entries of $M$ are upper bounded by certain sparsity parameter. We show that the performance of estimating the connectivity matrix $M$ depends on the sparsity of the graph. We focus on two measurement of performance of estimation: the error of estimating $M$ and the error of estimating the column space of $M$. In the first case, we consider the operator norm and Frobenius norm of the difference between the estimation and the true connectivity matrix. In the second case, the performance will be measured by the difference between the estimated projection matrix and the true projection matrix in operator norm and Frobenius norm. We will show that the estimators we propose achieve the minimax optimal rate.
Author Information
Zhixin Zhou (City University of Hong Kong)
Fan Zhou (Baidu Research)
Ping Li (Baidu Research USA)
Cun-Hui Zhang (Rutgers University)
More from the Same Authors
-
2021 Poster: A Comprehensively Tight Analysis of Gradient Descent for PCA »
Zhiqiang Xu · Ping Li -
2021 Poster: Backdoor Attack with Imperceptible Input and Latent Modification »
Khoa Doan · Yingjie Lao · Ping Li -
2021 Poster: A Note on Sparse Generalized Eigenvalue Problem »
Yunfeng Cai · Guanhua Fang · Ping Li -
2021 Poster: Mitigating Forgetting in Online Continual Learning with Neuron Calibration »
Haiyan Yin · peng yang · Ping Li -
2021 Poster: Learning Generative Vision Transformer with Energy-Based Latent Space for Saliency Prediction »
Jing Zhang · Jianwen Xie · Nick Barnes · Ping Li -
2019 Poster: Möbius Transformation for Fast Inner Product Search on Graph »
Zhixin Zhou · Shulong Tan · Zhaozhuo Xu · Ping Li -
2012 Poster: Entropy Estimations Using Correlated Symmetric Stable Random Projections »
Ping Li · Cun-Hui Zhang -
2012 Poster: Calibrated Elastic Regularization in Matrix Completion »
Cun-Hui Zhang · Tingni Sun -
2012 Poster: One Permutation Hashing »
Ping Li · Art B Owen · Cun-Hui Zhang