Rate-Optimal Subspace Estimation on Random Graphs

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.