  An incoherent low-rank matrix can be efficiently reconstructed after
observing a few of its entries at random, and then solving a convex program
that minimizes the nuclear norm. In many applications, in addition to these
entries, potentially valuable prior knowledge about the column and row spaces
of the matrix is also available to the practitioner. In this paper, we
incorporate this prior knowledge in matrix completion---by minimizing a
weighted nuclear norm---and precisely quantify any improvements. In particular,
we find in theory that reliable prior knowledge reduces the sample complexity
of matrix completion by a logarithmic factor, and the observed improvement in
numerical simulations is considerably more magnified. We also present similar
results for the closely related problem of matrix recovery from generic linear
measurements.
