  This paper provides the best bounds to date on the number of randomly sampled
entries required to reconstruct an unknown low rank matrix. These results
improve on prior work by Candes and Recht, Candes and Tao, and Keshavan,
Montanari, and Oh. The reconstruction is accomplished by minimizing the nuclear
norm, or sum of the singular values, of the hidden matrix subject to agreement
with the provided entries. If the underlying matrix satisfies a certain
incoherence condition, then the number of entries required is equal to a
quadratic logarithmic factor times the number of parameters in the singular
value decomposition. The proof of this assertion is short, self contained, and
uses very elementary analysis. The novel techniques herein are based on recent
work in quantum information theory.
