Matrix Completion From a Few Entries
Top Cited Papers
- 18 May 2010
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 56 (6), 2980-2998
- https://doi.org/10.1109/tit.2010.2046205
Abstract
Let M be an n¿ × n matrix of rank r, and assume that a uniformly random subset E of its entries is observed. We describe an efficient algorithm, which we call OptSpace, that reconstructs M from |E| = O(rn) observed entries with relative root mean square error 1/2 RMSE ¿ C(¿) (nr/|E|)1/2 with probability larger than 1 - 1/n3. Further, if r = O(1) and M is sufficiently unstructured, then OptSpace reconstructs it exactly from |E| = O(n log n) entries with probability larger than 1 - 1/n3. 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.Keywords
Other Versions
This publication has 14 references indexed in Scilit:
- Fast computation of low-rank matrix approximationsJournal of the ACM, 2007
- Compressed sensingIEEE Transactions on Information Theory, 2006
- Spectral techniques applied to sparse random graphsRandom Structures & Algorithms, 2005
- Fast monte-carlo algorithms for finding low-rank approximationsJournal of the ACM, 2004
- Recovering the missing components in a large noisy low-rank matrix: application to SFMIEEE Transactions on Pattern Analysis and Machine Intelligence, 2004
- The Expected Norm of Random MatricesCombinatorics, Probability and Computing, 2000
- Matrices, Vector Spaces, and Information RetrievalSIAM Review, 1999
- The Geometry of Algorithms with Orthogonality ConstraintsSIAM Journal on Matrix Analysis and Applications, 1998
- On the second eigenvalue of random regular graphsPublished by Association for Computing Machinery (ACM) ,1989
- Minimization of functions having Lipschitz continuous first partial derivativesPacific Journal of Mathematics, 1966