Information-Guided Sampling for Low-Rank Matrix Completion

Abstract

The noisy matrix completion problem, which aims to recover a low-rank matrix $\mathbf{X}$ from a partial, noisy observation of its entries, arises in many statistical, machine learning, and engineering applications. In this paper, we present a new, information-theoretic approach for active sampling (or designing) of matrix entries for noisy matrix completion, based on the maximum entropy design principle. One novelty of our method is that it implicitly makes use of uncertainty quantification (UQ) -- a measure of uncertainty for unobserved matrix entries -- to guide the active sampling procedure. The proposed framework reveals several novel insights on the role of compressive sensing (e.g., coherence) and coding design (e.g., Latin squares) on the sampling performance and UQ for noisy matrix completion. Using such insights, we develop an efficient posterior sampler for UQ, which is then used to guide a closed-form sampling scheme for matrix entries. Finally, we illustrate the effectiveness of this integrated sampling / UQ methodology in simulation studies and two applications to collaborative filtering.

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

References in corpus (8)

• Practical Bayesian Optimization of Machine Learning Algorithms
• An overview of low-rank matrix recovery from incomplete observations
• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Learning Active Learning from Data
• Certain Relations between Mutual Information and Fidelity of Statistical Estimation
• Measurement Matrix Design for Phase Retrieval Based on Mutual Information
• Maximum entropy low-rank matrix recovery

Cited by in corpus (2)

• Inference and Uncertainty Quantification for Noisy Matrix Completion
• Matrix Completion with Quantified Uncertainty through Low Rank Gaussian Copula