A Simpler Approach to Matrix Completion

Details A Simpler Approach to Matrix Completion A Simpler Approach to Matrix Completion

2009-10-05

arxiv.org/abs/0910.0651v2

Computer Science

Information Theory

13 pages. Fixed typos. Added references

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

A Simpler Approach to Matrix Completion does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Simpler Approach to Matrix Completion, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Simpler Approach to Matrix Completion will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-9196