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 -