Thy Friend is My Friend: Iterative Collaborative Filtering for Sparse Matrix Estimation

The sparse matrix estimation problem consists of estimating the distribution of an n × n matrix Y, from a sparsely observed single instance of this matrix where the entries of Y are independent random variables. This captures a wide array of problems; special instances include matrix completion in the context of recommendation systems, graphon estimation, and community detection in (mixed membership) stochastic block models. Inspired by classical collaborative filtering for recommendation systems, we propose a novel iterative, collaborative filtering style algorithm for matrix estimation in this generic setting. We show that the mean squared error (MSE) of our estimator goes to 0 as long as ω(d²n) random entries from a total of n² entries of Y are observed (uniformly sampled), E[Y] has rank d, and the entries of Y have bounded support. The maximum squared error across all entries converges to 0 with high probability as long as we observe a little more, Ω(d²n ln²(n)) entries. Our results are the best-known sample complexity results in this generality. Our intuitive, easy to implement iterative nearest-neighbor style algorithm matches the conjectured sample complexity lower bound of d²n for a computationally efficient algorithm for detection in the mixed membership stochastic block model.