Abstract
Consider the matrix completion problem: Given only a subset of the entries of a low-rank matrix, recover the remaining ones. How many entries do we need to see to complete a matrix of rank r? How can such entries be sampled? If we sample entries adaptively, do we need to see as many samples? The last question is still quite open, but we propose an two-phase sampling algorithm and show precisely how adaptive sampling can require fewer samples for low-rank completion under general conditions on the matrix leverage scores.