article

Free access

A Simpler Approach to Matrix Completion

Author:

Benjamin RechtAuthors Info & Claims

The Journal of Machine Learning Research, Volume 12

Pages 3413 - 3430

Published: 01 December 2011 Publication History

Abstract

This paper provides the best bounds to date on the number of randomly sampled entries required to reconstruct an unknown low-rank matrix. These results improve on prior work by Candès and Recht (2009), Candès and Tao (2009), and Keshavan et al. (2009). The reconstruction is accomplished by minimizing the nuclear norm, or sum of the singular values, of the hidden matrix subject to agreement with the provided entries. If the underlying matrix satisfies a certain incoherence condition, then the number of entries required is equal to a quadratic logarithmic factor times the number of parameters in the singular value decomposition. The proof of this assertion is short, self contained, and uses very elementary analysis. The novel techniques herein are based on recent work in quantum information theory.

References

[1]

Rudolf Ahlswede and Andreas Winter. Strong converse for identification via quantum channels. IEEE Transactions on Information Theory, 48(3):569-579, 2002.

[2]

Andreas Argyriou, Charles A. Micchelli, and Massimiliano Pontil. Convex multi-task feature learning. Machine Learning, 2008. Published online first at http://www.springerlink.com/.

[3]

Carolyn Beck and Raffaello D'Andrea. Computational study and comparisons of LFT reducibility methods. In Proceedings of the American Control Conference, 1998.

[4]

Emmanuel Candès and Benjamin Recht. Exact matrix completion via convex optimization. Foundations of Computational Mathematics, 9(6):717-772, 2009.

[5]

Emmanuel J. Candès and Yaniv Plan. Matrix completion with noise. Proceedings of the IEEE, 98 (6):925-936, 2009.

[6]

Emmanuel J. Candès and Terence Tao. The power of convex relaxation: Near-optimal matrix completion. IEEE Transactions on Information Theory, 56(5):2053-2080, 2009.

[7]

Emmanuel J. Candés, Justin Romberg, and Terence Tao. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on Information Theory, 52(2):489-509, 2006. ISSN 0018-9448.

[8]

Alexander L. Chistov and Dima Yu. Grigoriev. Complexity of quantifier elimination in the theory of algebraically closed fields. In Proceedings of the 11th Symposium on Mathematical Foundations of Computer Science, volume 176 of Lecture Notes in Computer Science, pages 17-31. Springer Verlag, 1984.

[9]

Victor H. de la Peña and Stephen J. Montgomery-Smith. Decoupling inequalities for the tail probabilities of multivariate U-statistics. Annals of Probability, 23(2):806-816, 1995. ISSN 0091-1798.

[10]

Maryam Fazel. Matrix Rank Minimization with Applications. PhD thesis, Stanford University, 2002.

[11]

Maryam Fazel, Haitham Hindi, and Stephen Boyd. A rank minimization heuristic with application to minimum order system approximation. In Proceedings of the American Control Conference, 2001.

[12]

Jean Jacques Fuchs. On sparse representations in arbitrary redundant bases. IEEE Transactions on Information Theory, 50:1341-1344, 2004.

[13]

Sideny Golden. Lower bounds for the Helmholtz function. Physical Review, 137B(4):B1127-1128, 1965.

[14]

Gaston H. Gonnet. Expected length of the longest probe sequence in hash code searching. Journal of the Association for Computing Machinery, 28(2):289-304, 1981.

[15]

David Gross. Recovering low-rank matrices from few coefficients in any basis. IEEE Transactions on Information Theory, 57:1548-1566, 2011.

[16]

David Gross, Yi-Kai Liu, Steven T. Flammia, Stephen Becker, and Jens Eisert. Quantum state tomography via compressed sensing. Physical Review Letters, 105(15):150401, 2010.

[17]

Torben Hagerup and Christine Rüb. A guided tour of Chernoff bounds. Information Processing Letters, 33:305-308, 1990.

[18]

Raghunandan H. Keshavan, Andrea Montanari, and Sewoong Oh. Matrix completion from a few entries. IEEE Transactions on Information Theory, 56(6):2980-2998, 2009.

[19]

Yehuda Koren, Robert Bell, and Chris Volinsky. Matrix factorization techniques for recommender systems. Computer, 42(8):30-37, 2009.

[20]

Nathan Linial, Eran London, and Yuri Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15:215-245, 1995.

[21]

Mehran Mesbahi and George P. Papavassilopoulos. On the rank minimization problem over a positive semidefinite linear matrix inequality. IEEE Transactions on Automatic Control, 42(2):239-243, 1997.

[22]

Guillaume Obozinski, Ben Taskar, and Michael I. Jordan. Joint covariate selection and joint subspace selection for multiple classification problems. Statistics and Computing, pages 1-22, 2009.

[23]

Dmitry Panchenko. MIT 18.465: Statistical Learning Theory. MIT Open Courseware http://ocw.mit.edu/OcwWeb/Mathematics/18-465Spring-2007/CourseHome/, 2007.

[24]

Benjamin Recht, Maryam Fazel, and Pablo Parrilo. Guaranteed minimum rank solutions of matrix equations via nuclear norm minimization. SIAM Review, 52(3):471-501, 2010.

[25]

Jason D. M. Rennie and Nathan Srebro. Fast maximum margin matrix factorization for collaborative prediction. In Proceedings of the International Conference of Machine Learning, 2005.

[26]

Anthony Man-Cho So and Yinyu Ye. Theory of semidefinite programming for sensor network localization. Mathematical Programming, Series B, 109:367-384, 2007.

[27]

Nathan Srebro. Learning with Matrix Factorizations. PhD thesis, Massachusetts Institute of Technology, 2004.

[28]

Colin J. Thompson. Inequality with applications in statistical mechanics. Journal of Mathematical Physics, 6(11):1812-1823, 1965.

[29]

Kilian Q. Weinberger and Lawrence K. Saul. Unsupervised learning of image manifolds by semidefinite programming. International Journal of Computer Vision, 70(1):77-90, 2006.

Cited By

Li JCui WZhang X(2024)Projected Gradient Descent for Spectral Compressed Sensing via Symmetric Hankel FactorizationIEEE Transactions on Signal Processing10.1109/TSP.2024.337800472(1590-1606)Online publication date: 18-Mar-2024
https://dl.acm.org/doi/10.1109/TSP.2024.3378004
Kümmerle CMaggioni MTang S(2024)Learning Transition Operators From Sparse Space-Time SamplesIEEE Transactions on Information Theory10.1109/TIT.2024.341353470:9(6412-6446)Online publication date: 14-Jun-2024
https://dl.acm.org/doi/10.1109/TIT.2024.3413534
Li HPimentel-Alarcón D(2024)GrassCaré: Visualizing the Grassmannian on the Poincaré DiskSN Computer Science10.1007/s42979-023-02597-05:3Online publication date: 28-Feb-2024
https://dl.acm.org/doi/10.1007/s42979-023-02597-0
Show More Cited By

A Simpler Approach to Matrix Completion
1. Computing methodologies
2. Theory of computation

Recommendations

On $l_q$ Optimization and Matrix Completion

Rank minimization problems, which consist of finding a matrix of minimum rank subject to linear constraints, have been proposed in many areas of engineering and science. A specific problem is the matrix completion problem in which a low rank data matrix ...
The inverse of any two-by-two nonsingular partitioned matrix and three matrix inverse completion problems

A formula for the inverse of any nonsingular matrix partitioned into two-by-two blocks is derived through a decomposition of the matrix itself and generalized inverses of the submatrices in the matrix. The formula is then applied to three matrix inverse ...
A fast tri-factorization method for low-rank matrix recovery and completion

In recent years, matrix rank minimization problems have received a significant amount of attention in machine learning, data mining and computer vision communities. And these problems can be solved by a convex relaxation of the rank minimization problem ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image The Journal of Machine Learning Research

The Journal of Machine Learning Research Volume 12, Issue

2/1/2011

3426 pages

ISSN:1532-4435

EISSN:1533-7928

Issue’s Table of Contents

Publisher

JMLR.org

Publication History

Published: 01 December 2011

Published in JMLR Volume 12

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

141
Total Citations
View Citations
1,423
Total Downloads

Downloads (Last 12 months)71
Downloads (Last 6 weeks)11

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Li JCui WZhang X(2024)Projected Gradient Descent for Spectral Compressed Sensing via Symmetric Hankel FactorizationIEEE Transactions on Signal Processing10.1109/TSP.2024.337800472(1590-1606)Online publication date: 18-Mar-2024
https://dl.acm.org/doi/10.1109/TSP.2024.3378004
Kümmerle CMaggioni MTang S(2024)Learning Transition Operators From Sparse Space-Time SamplesIEEE Transactions on Information Theory10.1109/TIT.2024.341353470:9(6412-6446)Online publication date: 14-Jun-2024
https://dl.acm.org/doi/10.1109/TIT.2024.3413534
Li HPimentel-Alarcón D(2024)GrassCaré: Visualizing the Grassmannian on the Poincaré DiskSN Computer Science10.1007/s42979-023-02597-05:3Online publication date: 28-Feb-2024
https://dl.acm.org/doi/10.1007/s42979-023-02597-0
Hammoudeh ZLowd D(2024)Training data influence analysis and estimation: a surveyMachine Language10.1007/s10994-023-06495-7113:5(2351-2403)Online publication date: 1-May-2024
https://dl.acm.org/doi/10.1007/s10994-023-06495-7
Zimmermann RCheng K(2024)Randomized greedy magic point selection schemes for nonlinear model reductionAdvances in Computational Mathematics10.1007/s10444-024-10172-150:4Online publication date: 22-Jul-2024
https://dl.acm.org/doi/10.1007/s10444-024-10172-1
Garber DKaplan A(2023)On the Efficient Implementation of the Matrix Exponentiated Gradient Algorithm for Low-Rank Matrix OptimizationMathematics of Operations Research10.1287/moor.2022.133248:4(2094-2128)Online publication date: 1-Nov-2023
https://dl.acm.org/doi/10.1287/moor.2022.1332
Nguyen TUhlmann J(2023)Tensor Completion with Provable Consistency and Fairness Guarantees for Recommender SystemsACM Transactions on Recommender Systems10.1145/36046491:3(1-26)Online publication date: 7-Aug-2023
https://dl.acm.org/doi/10.1145/3604649
Cai HHuang LLi PNeedell D(2023)Matrix Completion With Cross-Concentrated Sampling: Bridging Uniform Sampling and CUR SamplingIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2023.326118545:8(10100-10113)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1109/TPAMI.2023.3261185
Tsakiris M(2023)Low-Rank Matrix Completion Theory via Plücker CoordinatesIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2023.325032545:8(10084-10099)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1109/TPAMI.2023.3250325
Shah DYu C(2023)Robust Max Entrywise Error Bounds for Tensor Estimation From Sparse Observations via Similarity-Based Collaborative FilteringIEEE Transactions on Information Theory10.1109/TIT.2023.323723169:5(3121-3149)Online publication date: 1-May-2023
https://dl.acm.org/doi/10.1109/TIT.2023.3237231
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents