Learning low rank matrices from O(n) entries

Raghunandan H. Keshavan, Andrea Montanari, Sewoong Oh

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

Abstract

How many random entries of an n × nα, rank r matrix are necessary to reconstruct the matrix within an accuracy δ? We address this question in the case of a random matrix with bounded rank, whereby the observed entries are chosen uniformly at random. We prove that, for any δ > 0, C(r,δ)n observations are sufficient. Finally we discuss the question of reconstructing the matrix efficiently, and demonstrate through extensive simulations that this task can be accomplished in nPoly(logn) operations, for small rank.

Original languageEnglish (US)
Title of host publication46th Annual Allerton Conference on Communication, Control, and Computing
Pages1365-1372
Number of pages8
DOIs
StatePublished - 2008
Event46th Annual Allerton Conference on Communication, Control, and Computing - Monticello, IL, United States
Duration: Sep 24 2008Sep 26 2008

Publication series

Name46th Annual Allerton Conference on Communication, Control, and Computing

Other

Other46th Annual Allerton Conference on Communication, Control, and Computing
CountryUnited States
CityMonticello, IL
Period9/24/089/26/08

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Software
  • Control and Systems Engineering
  • Communication

Fingerprint Dive into the research topics of 'Learning low rank matrices from O(n) entries'. Together they form a unique fingerprint.

Cite this