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

arXiv: https://arxiv.org/abs/1503.02596 · HTML: https://mlsanity.com/paper/1503.02596/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Mar 2015.

## Built on by (most cited first, 13 of 13)

- [Scalars are universal: Equivariant machine learning, structured like classical physics](https://mlsanity.com/paper/2106.06610/) (2021)
- [Sensing Theorems for Unsupervised Learning in Linear Inverse Problems](https://mlsanity.com/paper/2203.12513/) (2022)
- [Unsupervised Learning From Incomplete Measurements for Inverse Problems](https://mlsanity.com/paper/2201.12151/) (2022)
- [Expressive Sign Equivariant Networks for Spectral Geometric Learning](https://mlsanity.com/paper/2312.02339/) (2023)
- [A Scalable Second Order Method for Ill-Conditioned Matrix Completion from Few Samples](https://mlsanity.com/paper/2106.02119/) (2021)
- [GNMR: A provable one-line algorithm for low rank matrix recovery](https://mlsanity.com/paper/2106.12933/) (2021)
- [Factorization Approach for Low-complexity Matrix Completion Problems: Exponential Number of Spurious Solutions and Failure of Gradient Methods](https://mlsanity.com/paper/2110.10279/) (2021)
- [Symmetric Matrix Completion with ReLU Sampling](https://mlsanity.com/paper/2406.05822/) (2024)
- [Matrix Completion from General Deterministic Sampling Patterns](https://mlsanity.com/paper/2306.02283/) (2023)
- [Tensor Train Completion from Fiberwise Observations Along a Single Mode](https://mlsanity.com/paper/2509.18149/) (2025)
- [Tomography by Design: An Algebraic Approach to Low-Rank Quantum States](https://mlsanity.com/paper/2602.15202/) (2026)
- [A Perturbation Bound on the Subspace Estimator from Canonical Projections](https://mlsanity.com/paper/2206.14278/) (2022)
- [Truncated Matrix Completion - An Empirical Study](https://mlsanity.com/paper/2504.09873/) (2025)

## Abstract (arXiv)

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 × 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(maxr,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.