Matrix Completion From a Few Entries

• Published in: IEEE transactions on information theory 2010-06, Vol.56 (6), p.2980-2998
• Main Authors: Keshavan, Raghunandan H, Montanari, Andrea, Sewoong Oh
• Format: Article
• Language: English
• Subjects: Algorithms; Collaboration; Gradient descent; Information filtering; Information filters; Information systems; Information theory; low rank; manifold optimization; Mathematical analysis; Mathematical model; Mathematical models; Matrices; Matrix; matrix completion; Mean square values; Motion pictures; Optimization methods; phase transition; Reconstruction; Reconstruction algorithms; Root mean square; Roots; Sparse matrices; spectral methods; Theory; Watches
• ISSN: 0018-9448; 1557-9654
• DOI: 10.1109/TIT.2010.2046205

Let M be an n¿ × n matrix of rank r, and assume that a uniformly random subset E of its entries is observed. We describe an efficient algorithm, which we call OptSpace, that reconstructs M from |E| = O(rn) observed entries with relative root mean square error 1/2 RMSE ¿ C(¿) (nr/|E|) 1/2 with probability larger than 1 - 1/n 3 . Further, if r = O(1) and M is sufficiently unstructured, then OptSpace reconstructs it exactly from |E| = O(n log n) entries with probability larger than 1 - 1/n 3 . This settles (in the case of bounded rank) a question left open by Candes and Recht and improves over the guarantees for their reconstruction algorithm. The complexity of our algorithm is O(|E|r log n), which opens the way to its use for massive data sets. In the process of proving these statements, we obtain a generalization of a celebrated result by Friedman-Kahn-Szemeredi and Feige-Ofek on the spectrum of sparse random matrices.