Information-Guided Sampling for Low-Rank Matrix Completion

The matrix completion problem, which aims to recover a low-rank matrix X from partial, noisy observations of its entries, arises in many machine learning applications. In this work, we present a novel information-theoretic framework for initial and sequential sampling of matrix entries for noisy matrix completion, based on the maximum entropy sampling principle in Shewry & Wynn (1987). The key novelty in our approach is that it makes use of uncertainty quantification (UQ) – a measure of uncertainty for unobserved entries – to guide the sampling procedure. Our framework reveals new insights on the role of coherence and coding design on sampling for matrix completion.