Learning low rank matrices from O(n) entries

How many random entries of an n times nalpha, rank r matrix are necessary to reconstruct the matrix within an accuracy delta? 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 delta Gt 0, C(r, delta)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.