A Caltech Library Service

Exact Low-rank Matrix Completion via Convex Optimization

Candès, Emmanuel J. and Recht, Benjamin (2008) Exact Low-rank Matrix Completion via Convex Optimization. In: 2008 46th annual Allerton Conference on Communication, Control, and Computing. IEEE , Piscataway, NJ, pp. 806-812. ISBN 978-1-4244-2925-7.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Candès, Emmanuel J.0000-0001-9234-924X
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.
Funding AgencyGrant Number
NSF 2006 Waterman AwardUNSPECIFIED
Office of Naval Research (ONR)UNSPECIFIED
Record Number:CaltechAUTHORS:20100628-142119214
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:18832
Deposited By: Tony Diaz
Deposited On:14 Jul 2010 18:06
Last Modified:09 Mar 2020 13:18

Repository Staff Only: item control page