Learning low rank matrices from O(n) entries

Raghunandan H. Keshavan; Andrea Montanari; Sewoong Oh

doi:10.1109/ALLERTON.2008.4797720

Learning low rank matrices from O(n) entries

Raghunandan H. Keshavan, Andrea Montanari, Sewoong Oh

Coordinated Science Lab

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	46th Annual Allerton Conference on Communication, Control, and Computing
Pages	1365-1372
Number of pages	8
DOIs	https://doi.org/10.1109/ALLERTON.2008.4797720
State	Published - 2008
Event	46th Annual Allerton Conference on Communication, Control, and Computing - Monticello, IL, United States Duration: Sep 24 2008 → Sep 26 2008

Publication series

Name	46th Annual Allerton Conference on Communication, Control, and Computing

Other

Other	46th Annual Allerton Conference on Communication, Control, and Computing
Country	United States
City	Monticello, IL
Period	9/24/08 → 9/26/08

ASJC Scopus subject areas

Computer Networks and Communications
Software
Control and Systems Engineering
Communication

Access to Document

10.1109/ALLERTON.2008.4797720

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

Cite this

Learning low rank matrices from O(n) entries. / Keshavan, Raghunandan H.; Montanari, Andrea; Oh, Sewoong.

46th Annual Allerton Conference on Communication, Control, and Computing. 2008. p. 1365-1372 4797720 (46th Annual Allerton Conference on Communication, Control, and Computing).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Keshavan, RH, Montanari, A & Oh, S 2008, Learning low rank matrices from O(n) entries. in 46th Annual Allerton Conference on Communication, Control, and Computing., 4797720, 46th Annual Allerton Conference on Communication, Control, and Computing, pp. 1365-1372, 46th Annual Allerton Conference on Communication, Control, and Computing, Monticello, IL, United States, 9/24/08. https://doi.org/10.1109/ALLERTON.2008.4797720

@inproceedings{b5aa19d940c7489c9c4238dbd3e13d17,

title = "Learning low rank matrices from O(n) entries",

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.",

author = "Keshavan, {Raghunandan H.} and Andrea Montanari and Sewoong Oh",

year = "2008",

doi = "10.1109/ALLERTON.2008.4797720",

language = "English (US)",

isbn = "9781424429264",

series = "46th Annual Allerton Conference on Communication, Control, and Computing",

pages = "1365--1372",

booktitle = "46th Annual Allerton Conference on Communication, Control, and Computing",

}

TY - GEN

T1 - Learning low rank matrices from O(n) entries

AU - Keshavan, Raghunandan H.

AU - Montanari, Andrea

AU - Oh, Sewoong

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=64549091526&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=64549091526&partnerID=8YFLogxK

U2 - 10.1109/ALLERTON.2008.4797720

DO - 10.1109/ALLERTON.2008.4797720

M3 - Conference contribution

AN - SCOPUS:64549091526

SN - 9781424429264

T3 - 46th Annual Allerton Conference on Communication, Control, and Computing

SP - 1365

EP - 1372

BT - 46th Annual Allerton Conference on Communication, Control, and Computing

T2 - 46th Annual Allerton Conference on Communication, Control, and Computing

Y2 - 24 September 2008 through 26 September 2008

ER -