Adaptive strategy for restricted-sampling noisy low-rank matrix completion

In this paper we propose a novel adaptive algorithm that provably performs low-rank matrix completion (LRMC) from restricted sets of observations, under ideal or noisy measurements, in lieu of coherence assumptions, with minimal sampling rates and optimal computational complexity. We discuss the main advantages of the adaptive setting of LRMC, and complement our theoretical analysis with experiments, illustrating the effectiveness of our algorithm.