Matrix Completion from $O(n)$ Samples in Linear Time

Abstract

We consider the problem of reconstructing a rank-$k$ $n\times n$ matrix $M$ from a sampling of its entries. Under a certain incoherence assumption on $M$ and for the case when both the rank and the condition number of $M$ are bounded, it was shown in \cite{CandesRecht2009, CandesTao2010, keshavan2010, Recht2011, Jain2012, Hardt2014} that $M$ can be recovered exactly or approximately (depending on some trade-off between accuracy and computational complexity) using $O(n\text{poly}(\log n))$ samples in super-linear time $O(n^a\text{poly}(\log n))$ for some constant $a\ge 1$. In this paper, we propose a new matrix completion algorithm using a novel sampling scheme based on a union of independent sparse random regular bipartite graphs. We show that under the same conditions w.h.p. our algorithm recovers an $\epsilon$-approximation of $M$ in terms of the Frobenius norm using $O(n{\log }^2(1/\epsilon ))$ samples and in linear time $O(n{\log }^2(1/\epsilon ))$. This provides the best known bounds both on the sample complexity and computational complexity for reconstructing (approximately) an unknown low-rank matrix. The novelty of our algorithm is two new steps of thresholding singular values and rescaling singular vectors in the application of the "vanilla" alternating minimization algorithm. The structure of sparse random regular graphs is used heavily for controlling the impact of these regularization steps.

45 pages, 1 figure. Short version accepted for presentation at Conference on Learning Theory (COLT) 2017

References in corpus (4)

• Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
• Matrix Completion With Noise
• Low-rank Matrix Completion using Alternating Minimization
• Matrix Completion and Related Problems via Strong Duality

Cited by in corpus (7)

• ${\ell }_p$-Spread and Restricted Isometry Properties of Sparse Random Matrices
• Deterministic tensor completion with hypergraph expanders
• Matrix Completion and Related Problems via Strong Duality
• On the second eigenvalue of random bipartite biregular graphs
• Fast and Sample Efficient Inductive Matrix Completion via Multi-Phase Procrustes Flow
• Can Agents Learn by Analogy? An Inferable Model for PAC Reinforcement Learning
• Recommendation on a Budget: Column Space Recovery from Partially Observed Entries with Random or Active Sampling