A Combinatorial Algebraic Approach for the Identifiability of Low-Rank Matrix Completion

Abstract

In this paper, we review the problem of matrix completion and expose its intimate relations with algebraic geometry, combinatorics and graph theory. We present the first necessary and sufficient combinatorial conditions for matrices of arbitrary rank to be identifiable from a set of matrix entries, yielding theoretical constraints and new algorithms for the problem of matrix completion. We conclude by algorithmically evaluating the tightness of the given conditions and algorithms for practically relevant matrix sizes, showing that the algebraic-combinatoric approach can lead to improvements over state-of-the-art matrix completion methods.

Appears in Proceedings of the 29th International Conference on Machine Learning (ICML 2012)

References in corpus (5)

• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Collaborative Filtering in a Non-Uniform World: Learning with the Weighted Trace Norm
• Concentration-Based Guarantees for Low-Rank Matrix Reconstruction
• A Combinatorial Algebraic Approach for the Identifiability of Low-Rank Matrix Completion
• Regression for sets of polynomial equations

Cited by in corpus (8)

• A Characterization of Deterministic Sampling Patterns for Low-Rank Matrix Completion
• Universal Matrix Completion
• A Combinatorial Algebraic Approach for the Identifiability of Low-Rank Matrix Completion
• Lifting for Blind Deconvolution in Random Mask Imaging: Identifiability and Convex Relaxation
• Matrix Completion with Deterministic Sampling: Theories and Methods
• Practical Matrix Completion and Corruption Recovery using Proximal Alternating Robust Subspace Minimization
• Stable rank one matrix completion is solved by two rounds of semidefinite programming relaxation
• Rank one tensor completion problem