Metraipolis › archive › dc_2bc1fd728e5f
Rank-Optimal Sample Complexity of Riemannian Gauss-Newton for Low-Rank Matrix Recovery — arXiv:2611.01542
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.01542
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T11:35:40.396Z
- SHA-256 of the archived text
a5519ee2e0f063eceae3a65ba407582e3fd961cd265e49ad5a05f2fc56b9e0ce- Stable URL of this page
https://metraipolis.com/documento/dc_2bc1fd728e5f
How to cite
Rank-Optimal Sample Complexity of Riemannian Gauss-Newton for Low-Rank Matrix Recovery — arXiv:2611.01542 — arXiv (en), https://arxiv.org/abs/2611.01542 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_2bc1fd728e5f (Metraipolis archive dc_2bc1fd728e5f, sha256 a5519ee2e0f063eceae3a65ba407582e3fd961cd265e49ad5a05f2fc56b9e0ce)
BibTeX
@misc{dc2bc1fd728e5f,
title = {Rank-Optimal Sample Complexity of Riemannian Gauss-Newton for Low-Rank Matrix Recovery — arXiv:2611.01542},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.01542},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_2bc1fd728e5f; sha256 a5519ee2e0f063eceae3a65ba407582e3fd961cd265e49ad5a05f2fc56b9e0ce},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.01542. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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)\kappa^2 )$ measurements, where $\kappa$ is the condition number of $\boldsymbol{X}_\star$. This is the first result to simultaneously achieve rank-optimal sample complexity and quadratic convergence for Gaussian low-rank matrix sensing. The key to the proof is a sharp spectral-norm analysis of the iterates, which requires controlling the inverse operator arising from the RGN equation. Our analysis develops an exact finite Neumann expansion of this inverse operator and combines it with a virtual-sequence decoupling argument and the restricted isometry property. Extensive numerical experiments support our theoretical findings and demonstrate the advantages of RGN.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.NA, nuovi lavori del giorno).
Categorie arXiv: Numerical Analysis (math.NA).
Pagina del lavoro: https://arxiv.org/abs/2611.01542 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T11:05:07.209Z dalla pagina https://arxiv.org/list/math.NA/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).