SOURCE-LINKED INTELLIGENCE

Near-Optimal Nonconvex Matrix Completion

arXiv · AI, language, vision and robotics · article · Sep 15, 2026 · UTC

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\times n$ matrix of rank $r$ with incoherence parameter $μ$ and condition number $κ$, the two methods achieve exact recovery with h

Read original source ↗ Open in workspace

recordType

paper

region

Global