# Incoherence-Optimal Matrix Completion

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Oct 2013.

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

- [Flat minima generalize for low-rank matrix recovery](https://mlsanity.com/paper/2203.03756/) (2022)
- [Exact Decomposition of Joint Low Rankness and Local Smoothness Plus Sparse Matrices](https://mlsanity.com/paper/2201.12592/) (2022)
- [HALO: Hadamard-Assisted Lower-Precision Optimization for LLMs](https://mlsanity.com/paper/2501.02625/) (2025)
- [A Scalable Second Order Method for Ill-Conditioned Matrix Completion from Few Samples](https://mlsanity.com/paper/2106.02119/) (2021)
- [Matrix Completion with Cross-Concentrated Sampling: Bridging Uniform Sampling and CUR Sampling](https://mlsanity.com/paper/2208.09723/) (2022)
- [Time Series Forecasting via Learning Convolutionally Low-Rank Models](https://mlsanity.com/paper/2104.11510/) (2021)
- [Multi-source Learning via Completion of Block-wise Overlapping Noisy Matrices](https://mlsanity.com/paper/2105.10360/) (2021)
- [GNMR: A provable one-line algorithm for low rank matrix recovery](https://mlsanity.com/paper/2106.12933/) (2021)
- [Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled Gradient Descent, Even with Overparameterization](https://mlsanity.com/paper/2310.06159/) (2023)
- [Robust Matrix Completion with Heavy-tailed Noise](https://mlsanity.com/paper/2206.04276/) (2022)
- [Localization from structured distance matrices via low-rank matrix recovery](https://mlsanity.com/paper/2311.18076/) (2023)
- [Informative core identification in complex networks](https://mlsanity.com/paper/2101.06388/) (2021)
- [Sample-Efficient Geometry Reconstruction from Euclidean Distances using Non-Convex Optimization](https://mlsanity.com/paper/2410.16982/) (2024)
- [Multi-Tensor Network Representation for High-Order Tensor Completion](https://mlsanity.com/paper/2109.04022/) (2021)
- [Generalization Bounds for Inductive Matrix Completion in Low-noise Settings](https://mlsanity.com/paper/2212.08339/) (2022)
- [Can Learning Be Explained By Local Optimality In Robust Low-rank Matrix Recovery?](https://mlsanity.com/paper/2302.10963/) (2023)
- [Spectal Harmonics: Bridging Spectral Embedding and Matrix Completion in Self-Supervised Learning](https://mlsanity.com/paper/2305.19818/) (2023)
- [Learning Transition Operators From Sparse Space-Time Samples](https://mlsanity.com/paper/2212.00746/) (2022)
- [Matrix Estimation for Individual Fairness](https://mlsanity.com/paper/2302.02096/) (2023)
- [Leave-One-Out Analysis for Nonconvex Robust Matrix Completion with General Thresholding Functions](https://mlsanity.com/paper/2407.19446/) (2024)
- [Euclidean Distance Matrix Completion via Asymmetric Projected Gradient Descent](https://mlsanity.com/paper/2504.19530/) (2025)
- [Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan](https://mlsanity.com/paper/2408.05431/) (2024)
- [Matrix Completion with Graph Information: A Provable Nonconvex Optimization Approach](https://mlsanity.com/paper/2502.08536/) (2025)
- [Fast Tensor Completion via Approximate Richardson Iteration](https://mlsanity.com/paper/2502.09534/) (2025)
- [Beyond Low-rankness: Guaranteed Matrix Recovery via Modified Nuclear Norm](https://mlsanity.com/paper/2507.18327/) (2025)
- [One-Sided Matrix Completion from Ultra-Sparse Samples](https://mlsanity.com/paper/2601.12213/) (2026)
- [Sample-efficient inductive matrix completion with noise and inexact side-information](https://mlsanity.com/paper/2605.17189/) (2026)

## Abstract (arXiv)

This paper considers the matrix completion problem. We show that it is not necessary to assume joint incoherence, which is a standard but unintuitive and restrictive condition that is imposed by previous studies. This leads to a sample complexity bound that is order-wise optimal with respect to the incoherence parameter (as well as to the rank r and the matrix dimension n up to a log factor). As a consequence, we improve the sample complexity of recovering a semidefinite matrix from O(nr2log2n) to O(nrlog2n), and the highest allowable rank from Theta(√n/log n) to Theta(n/log2n). The key step in proof is to obtain new bounds on the ℓ∞,2-norm, defined as the maximum of the row and column norms of a matrix. To illustrate the applicability of our techniques, we discuss extensions to SVD projection, structured matrix completion and semi-supervised clustering, for which we provide order-wise improvements over existing results. Finally, we turn to the closely-related problem of low-rank-plus-sparse matrix decomposition. We show that the joint incoherence condition is unavoidable here for polynomial-time algorithms conditioned on the Planted Clique conjecture. This means it is intractable in general to separate a rank-ω(√n) positive semidefinite matrix and a sparse matrix. Interestingly, our results show that the standard and joint incoherence conditions are associated respectively with the information (statistical) and computational aspects of the matrix decomposition problem.