Matrix Completion from Noisy Entries
Preprint
Abstract
Given a matrix M of low-rank, we consider the problem of reconstructing it from noisy observations of a small, random subset of its entries. The problem arises in a variety of applications, from collaborative filtering (the `Netflix problem') to structure-from-motion and positioning. We study a low complexity algorithm introduced by Keshavan et al.(2009), based on a combination of spectral techniques and manifold optimization, that we call here OptSpace. We prove performance guarantees that are order-optimal in a number of circumstances.Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Hankel Matrix Rank Minimization with Applications to System Identification and RealizationSIAM Journal on Matrix Analysis and Applications, 2013
- ADMiRA: Atomic Decomposition for Minimum Rank ApproximationIEEE Transactions on Information Theory, 2010
- The Power of Convex Relaxation: Near-Optimal Matrix CompletionIEEE Transactions on Information Theory, 2010
- Matrix Completion With NoiseProceedings of the IEEE, 2010
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm MinimizationSIAM Review, 2010
- A Singular Value Thresholding Algorithm for Matrix CompletionSIAM Journal on Optimization, 2010
- Fixed point and Bregman iterative methods for matrix rank minimizationMathematical Programming, 2009
- Fast monte-carlo algorithms for finding low-rank approximationsJournal of the ACM, 2004
- The Expected Norm of Random MatricesCombinatorics, Probability and Computing, 2000
- The Geometry of Algorithms with Orthogonality ConstraintsSIAM Journal on Matrix Analysis and Applications, 1998