{"id":"arxiv/2611.01542","url":"https://arxiv.org/abs/2611.01542","tags":["math.NA"],"score":0,"title":"Rank-Optimal Sample Complexity of Riemannian Gauss-Newton for Low-Rank Matrix Recovery","domain":"math.NA","source":"arxiv","authors":["Xunmeng Wu","Jian-Feng Cai","Zongben Xu","Zai Yang"],"reviews":0,"subject":"math.NA","summary":"In this paper, we study the recovery of an unknown rank-$r$ matrix $\\boldsymbol{X}_\\star \\in \\mathbb{R}^{n_1\\times n_2}$ from Gaussian linear measurements using the Riemannian Gauss-Newton (RGN) algorithm. Each iteration of RGN solves the RGN equation followed by a fixed-rank retraction. We prove that, with high probability, RGN with spectral initialization converges quadratically to $\\boldsymbol{X}_\\star$ using $\\mathcal{O} ( r(n_1+n_2)κ^2 )$ measurements, where $κ$ is the condition number of $\\boldsymbol{X}_\\star$. This is the first result to simultaneously achieve rank-optimal sample…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-01","reactions":{}}