Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published 2008 | Published
Book Section - Chapter Open

Exact Low-rank Matrix Completion via Convex Optimization

Abstract

Suppose that one observes an incomplete subset of entries selected uniformly at random from a low-rank matrix. When is it possible to complete the matrix and recover the entries that have not been seen? We show that in very general settings, one can perfectly recover all of the missing entries from a sufficiently large random subset by solving a convex programming problem. This program finds the matrix with the minimum nuclear norm agreeing with the observed entries. The techniques used in this analysis draw upon parallels in the field of compressed sensing, demonstrating that objects other than signals and images can be perfectly reconstructed from very limited information.

Additional Information

© 2008 IEEE. E. C. was partially supported by a National Science Foundation grant CCF-515362, by the 2006 Waterman Award (NSF) and by an ONR grant. The authors would like to thank Ali Jadbabaie, Pablo Parrilo, Ali Rahimi, Terence Tao, and Joel Tropp for fruitful discussions about parts of this paper. E. C. would like to thank Arnaud Durand for his careful proof-reading and comments.

Attached Files

Published - Candes2008p81102008_46Th_Annual_Allerton_Conference_On_Communication_Control_And_Computing_Vols_1-3.pdf

Files

Candes2008p81102008_46Th_Annual_Allerton_Conference_On_Communication_Control_And_Computing_Vols_1-3.pdf

Additional details

Created:
August 19, 2023
Modified:
October 20, 2023