Iterative Collaborative Filtering for Sparse Matrix Estimation

Abstract

We consider sparse matrix estimation where the goal is to estimate an $n\times n$ matrix from noisy observations of a small subset of its entries. We analyze the estimation error of the popularly utilized collaborative filtering algorithm for the sparse regime. Specifically, we propose a novel iterative variant of the algorithm, adapted to handle the setting of sparse observations. We establish that as long as the fraction of entries observed at random scale as $\frac{{\log }^{1+\kappa }(n)}{n}$ for any fixed $\kappa >0$, the estimation error with respect to the $\max$-norm decays to $0$ as $n\to \infty$ assuming the underlying matrix of interest has constant rank $r$. Our result is robust to model mis-specification in that if the underlying matrix is approximately rank $r$, then the estimation error decays to the approximate error with respect to the $\max$-norm. In the process, we establish algorithm's ability to handle arbitrary bounded noise in the observations.

References in corpus (7)

• Percolation on sparse networks
• Graph limits and exchangeable random graphs
• Near-optimal bounds for phase synchronization
• Spectral Method and Regularized MLE Are Both Optimal for Top-$K$ Ranking
• Recovering communities in the general stochastic block model without knowing the parameters
• Bayesian estimation from few samples: community detection and related problems
• Nearest Neighbors for Matrix Estimation Interpreted as Blind Regression for Latent Variable Model

Cited by in corpus (6)

• Learning from Comparisons and Choices
• Tensor Completion with Nearly Linear Samples Given Weak Side Information
• Analysis of large sparse graphs using regular decomposition of graph distance matrices
• On the Estimation of Network Complexity: Dimension of Graphons
• Regular Partitions and Their Use in Structural Pattern Recognition
• Robust Max Entrywise Error Bounds for Tensor Estimation from Sparse Observations via Similarity Based Collaborative Filtering