Information-Guided Sampling for Low-Rank Matrix Completion


The matrix completion problem, which aims to recover a low-rank matrix $\mathbf{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 \citet{SW1987}. 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.

ICML-21 Workshop on Information-Theoretic Methods for Rigorous, Responsible, and Reliable Machine Learning