  We consider the problem of recovering a lowrank matrix M from a small number
of random linear measurements. A popular and useful example of this problem is
matrix completion, in which the measurements reveal the values of a subset of
the entries, and we wish to fill in the missing entries (this is the famous
Netflix problem). When M is believed to have low rank, one would ideally try to
recover M by finding the minimum-rank matrix that is consistent with the data;
this is, however, problematic since this is a nonconvex problem that is,
generally, intractable.
  Nuclear-norm minimization has been proposed as a tractable approach, and past
papers have delved into the theoretical properties of nuclear-norm minimization
algorithms, establishing conditions under which minimizing the nuclear norm
yields the minimum rank solution. We review this spring of emerging literature
and extend and refine previous theoretical results. Our focus is on providing
error bounds when M is well approximated by a low-rank matrix, and when the
measurements are corrupted with noise. We show that for a certain class of
random linear measurements, nuclear-norm minimization provides stable recovery
from a number of samples nearly at the theoretical lower limit, and enjoys
order-optimal error bounds (with high probability).
