Matrix completion from a few entries

Raghunandan H. Keshavan, Andrea Montanari, Sewoong Oh

Research output: Contribution to journalArticlepeer-review

Abstract

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(r n) observed entries with relative root mean square error RMSE ≤ C (α) (nr/|E|)1/2 with probability larger than 1 - 1/n3 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 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)
Article number2046205
Pages (from-to)2980-2998
Number of pages19
JournalIEEE Transactions on Information Theory
Volume56
Issue number6
DOIs
StatePublished - Jun 2010

Keywords

  • Gradient descent
  • Low rank
  • Manifold optimization
  • Matrix completion
  • Phase transition
  • Spectral methods

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Fingerprint

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

Cite this