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× n matrix of rank r with incoherence parameter μ and condition number κ, the two methods achieve exact recovery with high probability from O(μnrlog nlog(nκ)) and O(μnrlog nlog(2μrκ)) 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.
Related
- Near-Optimal Complexity of Finding Approximate Local Minima of Nonconvex Finite Sums
- Near-Optimal Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimization
- Near-Optimal Parallel M-Matrix Scaling
- Douglas-Rachford splitting method for nonconvex stochastic optimal control
- Matrix Completion Discriminants
BibTeX
@misc{cai2026nearoptimal,
title = {{Near-Optimal Nonconvex Matrix Completion}},
author = {Jian-Feng Cai and Xiliang Lu and Juntao You},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.17048},
eprint = {2609.17048},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.17048},
}
RIS
TY - UNPB
TI - Near-Optimal Nonconvex Matrix Completion
AU - Jian-Feng Cai
AU - Xiliang Lu
AU - Juntao You
PY - 2026
DA - 2026/09/15
PB - arXiv
DO - 10.48550/arxiv.2609.17048
UR - https://arxiv.org/abs/2609.17048
AB - 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 κ, the two methods achieve exact recovery with high probability from O(μnrlog nlog(nκ)) and O(μnrlog nlog(2μrκ)) 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.
ER -