Title: Iterative Collaborative Filtering for Sparse Matrix Estimation,
Abstract: The sparse matrix estimation problem consists of estimating the distribution
of an $n\times 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 converges to $0$ at the rate of $O(d^2 (pn)^{-2/5})$ as long as
$\omega(d^5 n)$ random entries from a total of $n^2$ entries of $Y$ are
observed (uniformly sampled), $\mathbb{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,
$\Omega(d^5 n \ln^2(n))$ entries. Our results are the best known sample
complexity results in this generality.