Matrix Completion from a Few Entries

Abstract

Let M be a random (alpha n) x n matrix of rank r<<n, and assume that a uniformly random subset E of its entries is observed. We describe an efficient algorithm that reconstructs M from |E| = O(rn) observed entries with relative root mean square error RMSE <= C(rn/|E|)^0.5 . Further, if r=O(1), M can be reconstructed exactly from |E| = O(n log(n)) entries. These results apply beyond random matrices to general low-rank incoherent matrices. This settles (in the case of bounded rank) a question left open by Candes and Recht and improves over the guarantees for their reconstruction algorithm. The complexity of our algorithm is O(|E|r log(n)), which opens the way to its use for massive data sets. In the process of proving these statements, we obtain a generalization of a celebrated result by Friedman-Kahn-Szemeredi and Feige-Ofek on the spectrum of sparse random matrices.

30 pages, 1 figure, journal version (v1, v2: Conference version ISIT 2009)

References in corpus (6)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• A Singular Value Thresholding Algorithm for Matrix Completion
• Exact Matrix Completion via Convex Optimization
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• Uniqueness of Low-Rank Matrix Completion by Rigidity Theory
• Learning Low Rank Matrices from O(n) Entries

Cited by in corpus (38)

• A Gradient Descent Algorithm on the Grassman Manifold for Matrix Completion
• Tight oracle bounds for low-rank matrix recovery from a minimal number of random measurements
• Guaranteed Rank Minimization via Singular Value Projection
• Subspace Evolution and Transfer (SET) for Low-Rank Matrix Completion
• The Landscape of Empirical Risk for Non-convex Losses
• Spectral bandits for smooth graph functions
• Collaborative Spectrum Sensing from Sparse Observations Using Matrix Completion for Cognitive Radio Networks
• Introduction to Nonnegative Matrix Factorization
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• Achieving Budget-optimality with Adaptive Schemes in Crowdsourcing
• ADMiRA: Atomic Decomposition for Minimum Rank Approximation
• On Polynomial Time Methods for Exact Low Rank Tensor Completion
• Sharp oracle inequalities for the prediction of a high-dimensional matrix
• Rank-one matrix estimation: analysis of algorithmic and information theoretic limits by the spatial coupling method
• SET: an algorithm for consistent matrix completion
• Fault Tolerant Matrix Pencil Method for Direction of Arrival Estimation
• Recursive Importance Sketching for Rank Constrained Least Squares: Algorithms and High-order Convergence
• Matrix Completion for Low-Observability Voltage Estimation
• Cross: Efficient Low-rank Tensor Completion
• PCA from noisy, linearly reduced data: the diagonal case
• Low-rank Matrix Completion with Noisy Observations: a Quantitative Comparison
• IMP: A Message-Passing Algorithmfor Matrix Completion
• Recovering Structured Probability Matrices
• A Rank-Corrected Procedure for Matrix Completion with Fixed Basis Coefficients
• Regularization for Matrix Completion
• On the Landscape of Synchronization Networks: A Perspective from Nonconvex Optimization
• A Geometric Approach to Low-Rank Matrix Completion
• Robust Spectral Detection of Global Structures in the Data by Learning a Regularization
• Exponential error rates of SDP for block models: Beyond Grothendieck's inequality
• Achieving the Bayes Error Rate in Synchronization and Block Models by SDP, Robustly
• Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimization
• Optimal Inference in Crowdsourced Classification via Belief Propagation
• Matrix Completion by the Principle of Parsimony
• Rank-to-engage: New Listwise Approaches to Maximize Engagement
• Uncertainty-aware Low-Rank Q-Matrix Estimation for Deep Reinforcement Learning
• On the Estimation of Coherence
• Increasing Energy Efficiency in Sensor Networks: Blue Noise Sampling and Non-Convex Matrix Completion
• Accurate low-rank matrix recovery from a small number of linear measurements