Near-Optimal Nonconvex Matrix Completion

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 $n\times 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 nr\log n\log(n\kappa))$ and $O(\mu nr\log n\log(2\mu r\kappa))$ 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.

Numerical Analysis (math.NA); Machine Learning (cs.LG)

arXiv:2609.17048 [math.NA]

(or arXiv:2609.17048v1 [math.NA] for this version)

https://doi.org/10.48550/arXiv.2609.17048 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.