# Low-rank matrix completion theory via Plucker coordinates

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Apr 2020.

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

- [Polynomial Width is Sufficient for Set Representation with High-dimensional Features](https://mlsanity.com/paper/2307.04001/) (2023)
- [Unlabeled Principal Component Analysis and Matrix Completion](https://mlsanity.com/paper/2101.09446/) (2021)
- [Guaranteed Multidimensional Time Series Prediction via Deterministic Tensor Completion Theory](https://mlsanity.com/paper/2501.15388/) (2025)
- [Provable Guarantees for Sparsity Recovery with Deterministic Missing Data Patterns](https://mlsanity.com/paper/2206.04893/) (2022)

## Abstract (arXiv)

Despite the popularity of low-rank matrix completion, the majority of its theory has been developed under the assumption of random observation patterns, whereas very little is known about the practically relevant case of non-random patterns. Specifically, a fundamental yet largely open question is to describe patterns that allow for unique or finitely many completions. This paper provides two such families of patterns for any rank. A key to achieving this is a novel formulation of low-rank matrix completion in terms of Plucker coordinates, the latter a traditional tool in computer vision. This connection is of potential significance to a wide family of matrix and subspace learning problems with incomplete data.