Learning Low Rank Matrices from O(n) Entries
Loading...
Date
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Description
How 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.
8 pages, 11 figures, Forty-sixth Allerton Conference on Communication, Control and Computing, invited paper
8 pages, 11 figures, Forty-sixth Allerton Conference on Communication, Control and Computing, invited paper