Near-Optimal Nonconvex Matrix Completion

arXiv:2609.17048v1 Announce Type: cross Abstract: 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 nimes n matrix of rank r with incoherence parameter mu and condition number kappa, the two methods achieve exact recovery with high probability from O(mu nrlog nlog(nkappa)) and O(mu nrlog nlog(2mu 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.

Source: arXiv cs.LG | 2026-09-16