Exact Matrix Completion via Convex Optimization

By E.J. Candes, B. Recht. 2008

6,366 citations recorded by the source corpus.

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\ge 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.

Subfields: Biomedical Engineering, Computational Mechanics, Mathematical Optimization, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Biomedical Engineering

  1. E.J. Candes
  2. Prateek Jain
  3. Lei Zhang
  4. Stephen P. Boyd
  5. Xiaoming Yuan
  6. B. Recht
  7. Sujay Sanghavi
  8. M. Soltanolkotabi

In Computational Mechanics

  1. Martin J. Wainwright
  2. E.J. Candes
  3. Francis R. Bach
  4. Wotao Yin
  5. Prateek Jain
  6. Peter Richtárik
  7. Lei Zhang
  8. Zhouchen Lin

In Mathematical Optimization

  1. Prateek Jain
  2. Zhi-Quan Tom Luo
  3. E.J. Candes
  4. Srinadh Bhojanapalli
  5. Jason D. Lee
  6. Martin J. Wainwright
  7. Justin K. Romberg
  8. Stephen J. Wright

In Signal Processing

  1. Martin J. Wainwright
  2. E.J. Candes
  3. Prateek Jain
  4. Sahand N. Negahban
  5. Wotao Yin
  6. Bart Vandereycken
  7. Sewoong Oh
  8. Srinadh Bhojanapalli

Citations in the corpus