Learning Low Rank Matrices from O(n) Entries

Simple item page
dc.creatorKeshavan, Raghunandan H.
dc.creatorMontanari, Andrea
dc.creatorOh, Sewoong
dc.date2008-12-14
dc.date.accessioned2026-07-07T12:12:45Z
dc.date.available2026-07-07T12:12:45Z
dc.descriptionHow many random entries of an n by m, rank r matrix are necessary to reconstruct the matrix within an accuracy d? 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 d>0, C(r,d)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(log n) operations, for small rank.
dc.description8 pages, 11 figures, Forty-sixth Allerton Conference on Communication, Control and Computing, invited paper
dc.identifierhttps://arxiv.org/abs/0812.2599
dc.identifierhttp://arxiv.org/abs/0812.2599
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/210646
dc.subjectData Structures and Algorithms
dc.titleLearning Low Rank Matrices from O(n) Entries
dc.typetext

Files

Collections

arXiv