Rank-Optimal Sample Complexity of Riemannian Gauss-Newton for Low-Rank Matrix Recovery

Xunmeng Wu; Jian-Feng Cai; Zongben Xu; Zai Yang

Rank-Optimal Sample Complexity of Riemannian Gauss-Newton for Low-Rank Matrix Recovery

Xunmeng Wu, Jian-Feng Cai, Zongben Xu, Zai Yang

arXivarxiv/2611.01542Nov 1, 2026math.NAscore 0

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…

Source JSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2611.01542
curl -X POST /api/v1/records/arxiv/2611.01542/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.01542/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'