# Near-Optimal Nonconvex Matrix Completion

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- First posted on arXiv 15 Sep 2026.

## Abstract (arXiv)

We study nonconvex methods for matrix completion, the problem of recovering a low-rank matrix from a subset of its entries. Convex methods achieve sample complexity linear in the matrix dimension and the rank, up to logarithmic factors, whereas global guarantees for commonly used nonconvex methods require a higher polynomial dependence on the rank. We close this gap by analyzing Riemannian gradient descent (RGD) and Riemannian Gauss--Newton (RGN) methods. For an n× n matrix of rank r with incoherence parameter μ and condition number kappa, the two methods achieve exact recovery with high probability from O(μ nrlog nlog(nkappa)) and O(μ nrlog nlog(2μ rkappa)) observations, respectively. The methods use a multiscale residual initialization, while the analysis simultaneously controls the spectral error and incoherence. The resulting RGD iterates converge linearly, whereas RGN eventually converges Q-quadratically.