Timezone: »

Rate-Optimal Subspace Estimation on Random Graphs
Zhixin Zhou · Fan Zhou · Ping Li · Cun-Hui Zhang

Wed Dec 08 12:30 AM -- 02:00 AM (PST) @
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