A Characterization of Deterministic Sampling Patterns for Low-Rank Matrix Completion

Abstract

Low-rank matrix completion (LRMC) problems arise in a wide variety of applications. Previous theory mainly provides conditions for completion under missing-at-random samplings. This paper studies deterministic conditions for completion. An incomplete $d\times N$ matrix is finitely rank-$r$ completable if there are at most finitely many rank-$r$ matrices that agree with all its observed entries. Finite completability is the tipping point in LRMC, as a few additional samples of a finitely completable matrix guarantee its unique completability. The main contribution of this paper is a deterministic sampling condition for finite completability. We use this to also derive deterministic sampling conditions for unique completability that can be efficiently verified. We also show that under uniform random sampling schemes, these conditions are satisfied with high probability if $O(\max \{r,\log d\})$ entries per column are observed. These findings have several implications on LRMC regarding lower bounds, sample and computational complexity, the role of coherence, adaptive settings and the validation of any completion algorithm. We complement our theoretical results with experiments that support our findings and motivate future analysis of uncharted sampling regimes.

This update corrects an error in version 2 of this paper, where we erroneously assumed that columns with more than r+1 observed entries would yield multiple independent constraints

References in corpus (1)

• Universal Matrix Completion

Cited by in corpus (24)

• Spectrum Cartography via Coupled Block-Term Tensor Decomposition
• Propagation Map Reconstruction via Interpolation Assisted Matrix Completion
• Matrix completion with deterministic pattern - a geometric perspective
• Matrix Completion with Deterministic Sampling: Theories and Methods
• On Deterministic Sampling Patterns for Robust Low-Rank Matrix Completion
• The condition number of Riemannian approximation problems
• Worst-case vs Average-case Design for Estimation from Fixed Pairwise Comparisons
• Rank $2r$ iterative least squares: efficient recovery of ill-conditioned low rank matrices from few entries
• Matrix Completion from $O(n)$ Samples in Linear Time
• On the Identifiability of Phylogenetic Networks under a Pseudolikelihood model
• Mixed Membership Graph Clustering via Systematic Edge Query
• Escaping Saddle Points in Ill-Conditioned Matrix Completion with a Scalable Second Order Method
• Fundamental Conditions for Low-CP-Rank Tensor Completion
• Characterization of Deterministic and Probabilistic Sampling Patterns for Finite Completability of Low Tensor-Train Rank Tensor
• Goodness-of-fit tests on manifolds
• Deterministic and Probabilistic Conditions for Finite Completability of Low-rank Multi-View Data
• Scaled Nuclear Norm Minimization for Low-Rank Tensor Completion
• Stable rank one matrix completion is solved by two rounds of semidefinite programming relaxation
• Deterministic and Probabilistic Conditions for Finite Completability of Low-Tucker-Rank Tensor
• On Robust Mean Estimation under Coordinate-level Corruption
• Factorization Approach for Low-complexity Matrix Completion Problems: Exponential Number of Spurious Solutions and Failure of Gradient Methods
• Truncated Matrix Completion - An Empirical Study
• Sequential Matrix Completion
• HOSVD-Based Algorithm for Weighted Tensor Completion