Matrix completion from a few entries

Raghunandan H. Keshavan, Sewoong Oh, Andrea Montanari

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Let M be an nα × n matrix of rank r « n, and assume that a uniformly random subset E of its entries is observed. We describe an efficient algorithm that reconstructs M from |E| = O(rn) observed entries with relative root mean square error RMSE ≤ C(α) (nr/|E|)1/2. Further, if r = O(1) and M is sufficiently unstructured, then it can be reconstructed exactly from |E| = O(n log n) entries. This settles (in the case of bounded rank) a question left open by Candès 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-Szemerédi and Feige-Ofek on the spectrum of sparse random matrices.

Original languageEnglish (US)
Title of host publication2009 IEEE International Symposium on Information Theory, ISIT 2009
Number of pages5
StatePublished - 2009
Event2009 IEEE International Symposium on Information Theory, ISIT 2009 - Seoul, Korea, Republic of
Duration: Jun 28 2009Jul 3 2009

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8102


Other2009 IEEE International Symposium on Information Theory, ISIT 2009
CountryKorea, Republic of

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Matrix completion from a few entries'. Together they form a unique fingerprint.

Cite this