Candès, Emmanuel J. and Recht, Benjamin (2009) Exact Matrix Completion via Convex Optimization. Foundations of Computational Mathematics, 9 (6). pp. 717-772. ISSN 1615-3375 http://resolver.caltech.edu/CaltechAUTHORS:20100106-133517824
- Published Version
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20100106-133517824
We consider a problem of considerable practical interest: the recovery of a data matrix from a sampling of its entries. Suppose that we observe m entries selected uniformly at random from a matrix M. Can we complete the matrix and recover the entries that we have not seen? We show that one can perfectly recover most low-rank matrices from what appears to be an incomplete set of entries. We prove that if the number m of sampled entries obeys m ≥ C n^(1.2)r log n for some positive numerical constant C, then with very high probability, most n×n matrices of rank r can be perfectly recovered by solving a simple convex optimization program. This program finds the matrix with minimum nuclear norm that fits the data. The condition above assumes that the rank is not too large. However, if one replaces the 1.2 exponent with 1.25, then the result holds for all values of the rank. Similar results hold for arbitrary rectangular matrices as well. Our results are connected with the recent literature on compressed sensing, and show that objects other than signals and images can be perfectly reconstructed from very limited information.
|Additional Information:||© The Author(s) 2009. This article is published with open access at Springerlink.com. Received: 30 May 2008. Revised: 6 February 2009. Accepted: 14 February 2009. Published online: 3 April 2009. Communicated by Michael Todd. E.C. was partially supported by a National Science Foundation grant CCF-515362, by the 2006Waterman 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 proofreading and comments. Open Access This article is distributed under the terms of the Creative Commons Attribution Noncommercial License which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.|
|Subject Keywords:||Matrix completion; Low-rank matrices; Convex optimization; Duality in optimization; Nuclear norm minimization; Random matrices; Noncommutative Khintchine inequality; Decoupling; Compressed sensing|
|Classification Code:||Mathematics Subject Classification (2000): 90C25 - 90C59 - 15A52|
|Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Tony Diaz|
|Deposited On:||07 Jan 2010 00:29|
|Last Modified:||26 Dec 2012 11:40|
Repository Staff Only: item control page