  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.
