# New Hardness Results for Low-Rank Matrix Completion

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 39 references that are in the map.
- First posted on arXiv 23 Jun 2025.

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

- [Computational Limits for Matrix Completion](https://mlsanity.com/paper/1402.2331/) (2014)
- [Algebraic approach to promise constraint satisfaction](https://mlsanity.com/paper/1811.00970/) (2018)
- [Approximating the Orthogonality Dimension of Graphs and Hypergraphs](https://mlsanity.com/paper/1906.05005/) (2019)
- [Topology and adjunction in promise constraint satisfaction](https://mlsanity.com/paper/2003.11351/) (2020)

## Abstract (arXiv)

The low-rank matrix completion problem asks whether a given real matrix with missing values can be completed so that the resulting matrix has low rank or is close to a low-rank matrix. The completed matrix is often required to satisfy additional structural constraints, such as positive semi-definiteness or a bounded infinity norm. The problem arises in various research fields, including machine learning, statistics, and theoretical computer science, and has broad real-world applications. This paper presents new mathsfNP -hardness results for low-rank matrix completion problems. We show that for every sufficiently large integer d and any real number varepsilon ∈ [ 2-O(d),frac17], given a partial matrix A with exposed values of magnitude at most 1 that admits a positive semi-definite completion of rank d, it is mathsfNP-hard to find a positive semi-definite matrix that agrees with each given value of A up to an additive error of at most varepsilon, even when the rank is allowed to exceed d by a multiplicative factor of O (frac1varepsilon 2 · log(1/varepsilon) ). This strengthens a result of Hardt, Meka, Raghavendra, and Weitz (COLT, 2014), which applies to multiplicative factors smaller than 2 and to varepsilon  that decays polynomially in d. We establish similar mathsfNP-hardness results for the case where the completed matrix is constrained to have a bounded infinity norm (rather than be positive semi-definite), for which all previous hardness results rely on complexity assumptions related to the Unique Games Conjecture. Our proofs involve a novel notion of nearly orthonormal representations of graphs, the concept of line digraphs, and bounds on the rank of perturbed identity matrices.