# Matrix completion with deterministic pattern - a geometric perspective

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Jan 2018.

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

- [Robust Matrix Completion with Heavy-tailed Noise](https://mlsanity.com/paper/2206.04276/) (2022)
- [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)
- [Guaranteed Multidimensional Time Series Prediction via Deterministic Tensor Completion Theory](https://mlsanity.com/paper/2501.15388/) (2025)
- [Euclidean Distance Matrix Completion via Asymmetric Projected Gradient Descent](https://mlsanity.com/paper/2504.19530/) (2025)
- [Provable Guarantees for Sparsity Recovery with Deterministic Missing Data Patterns](https://mlsanity.com/paper/2206.04893/) (2022)
- [Truncated Matrix Completion - An Empirical Study](https://mlsanity.com/paper/2504.09873/) (2025)

## Abstract (arXiv)

We consider the matrix completion problem with a deterministic pattern of observed entries. In this setting, we aim to answer the question: under what condition there will be (at least locally) unique solution to the matrix completion problem, i.e., the underlying true matrix is identifiable. We answer the question from a certain point of view and outline a geometric perspective. We give an algebraically verifiable sufficient condition, which we call the well-posedness condition, for the local uniqueness of MRMC solutions. We argue that this condition is necessary for local stability of MRMC solutions, and we show that the condition is generic using the characteristic rank. We also argue that the low-rank approximation approaches are more stable than MRMC and further propose a sequential statistical testing procedure to determine the "true" rank from observed entries. Finally, we provide numerical examples aimed at verifying validity of the presented theory.