{"id":"arxiv/2609.17048","url":"https://arxiv.org/abs/2609.17048","tags":["math.NA","cs.LG"],"score":0,"title":"Near-Optimal Nonconvex Matrix Completion","domain":"math.NA","source":"arxiv","authors":["Jian-Feng Cai","Xiliang Lu","Juntao You"],"reviews":0,"subject":"math.NA","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-15","reactions":{}}