# Matrix Completion from General Deterministic Sampling Patterns

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 22 references that are in the map.
- First posted on arXiv 4 Jun 2023.

## Builds on (most cited first, 4 of 4)

- [Geometric Matrix Completion with Recurrent Multi-Graph Neural Networks](https://mlsanity.com/paper/1704.06803/) (2017)
- [A Characterization of Deterministic Sampling Patterns for Low-Rank Matrix Completion](https://mlsanity.com/paper/1503.02596/) (2015)
- [Universal Matrix Completion](https://mlsanity.com/paper/1402.2324/) (2014)
- [Matrix completion with deterministic pattern - a geometric perspective](https://mlsanity.com/paper/1802.00047/) (2018)

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

- [Symmetric Matrix Completion with ReLU Sampling](https://mlsanity.com/paper/2406.05822/) (2024)
- [Global Optimization on Graph-Structured Data via Gaussian Processes with Spectral Representations](https://mlsanity.com/paper/2511.07734/) (2025)

## Abstract (arXiv)

Most of the existing works on provable guarantees for low-rank matrix completion algorithms rely on some unrealistic assumptions such that matrix entries are sampled randomly or the sampling pattern has a specific structure. In this work, we establish theoretical guarantee for the exact and approximate low-rank matrix completion problems which can be applied to any deterministic sampling schemes. For this, we introduce a graph having observed entries as its edge set, and investigate its graph properties involving the performance of the standard constrained nuclear norm minimization algorithm. We theoretically and experimentally show that the algorithm can be successful as the observation graph is well-connected and has similar node degrees. Our result can be viewed as an extension of the works by Bhojanapalli and Jain [2014] and Burnwal and Vidyasagar [2020], in which the node degrees of the observation graph were assumed to be the same. In particular, our theory significantly improves their results when the underlying matrix is symmetric.