  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 by 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.
