# Universal Matrix Completion

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Feb 2014.

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

- [Optimal Algorithms for Latent Bandits with Cluster Structure](https://mlsanity.com/paper/2301.07040/) (2023)
- [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)
- [Matrix Completion from General Deterministic Sampling Patterns](https://mlsanity.com/paper/2306.02283/) (2023)
- [Spectral gap-based deterministic tensor completion](https://mlsanity.com/paper/2306.06262/) (2023)
- [Entry-Specific Bounds for Low-Rank Matrix Completion under Highly Non-Uniform Sampling](https://mlsanity.com/paper/2403.00184/) (2024)
- [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)
- [Support Recovery in Sparse PCA with Non-Random Missing Data](https://mlsanity.com/paper/2302.01535/) (2023)
- [Online Matrix Completion: A Collaborative Approach with Hott Items](https://mlsanity.com/paper/2408.05843/) (2024)
- [Matrix Completion in Group Testing: Bounds and Simulations](https://mlsanity.com/paper/2501.13780/) (2025)
- [Fast exact recovery of noisy matrix from few entries: the infinity norm approach](https://mlsanity.com/paper/2501.19224/) (2025)

## Abstract (arXiv)

The problem of low-rank matrix completion has recently generated a lot of interest leading to several results that offer exact solutions to the problem. However, in order to do so, these methods make assumptions that can be quite restrictive in practice. More specifically, the methods assume that: a) the observed indices are sampled uniformly at random, and b) for every new matrix, the observed indices are sampled afresh. In this work, we address these issues by providing a universal recovery guarantee for matrix completion that works for a variety of sampling schemes. In particular, we show that if the set of sampled indices come from the edges of a bipartite graph with large spectral gap (i.e. gap between the first and the second singular value), then the nuclear norm minimization based method exactly recovers all low-rank matrices that satisfy certain incoherence properties. Moreover, we also show that under certain stricter incoherence conditions, O(nr2) uniformly sampled entries are enough to recover any rank-r n× n matrix, in contrast to the O(nrlog n) sample complexity required by other matrix completion algorithms as well as existing analyses of the nuclear norm method.