Rank-Optimal Sample Complexity of Riemannian Gauss-Newton for Low-Rank Matrix Recovery
Abstract
In this paper, we study the recovery of an unknown rank-r matrix X⋆ ∈ ℝn1× n2 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 X⋆ using 𝒪 ( r(n1+n2)κ2 ) measurements, where κ is the condition number of X⋆. 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.
Related
- Near-Optimal Sample Complexity for Recursive Entropic Risk Reinforcement Learning with a Generative Model
- Sparse Dictionary Learning for Measure-Valued Data via Linearized Optimal Transport: Efficient Algorithms and Sample Complexity
- Differentially Private Learning of Markov Chains: Near-Optimal Sample Complexity for Item and User Level Privacy
- Lifted Restricted Isometry Property and Fast Algorithm for Spectral Compressed Sensing With Near-Optimal Sample Complexity
- On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularization
BibTeX
@misc{wu2026rankoptimal,
title = {{Rank-Optimal Sample Complexity of Riemannian Gauss-Newton for Low-Rank Matrix Recovery}},
author = {Xunmeng Wu and Jian-Feng Cai and Zongben Xu and Zai Yang},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.01542},
eprint = {2611.01542},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.01542},
}
RIS
TY - UNPB
TI - Rank-Optimal Sample Complexity of Riemannian Gauss-Newton for Low-Rank Matrix Recovery
AU - Xunmeng Wu
AU - Jian-Feng Cai
AU - Zongben Xu
AU - Zai Yang
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.01542
UR - https://arxiv.org/abs/2611.01542
AB - In this paper, we study the recovery of an unknown rank-r matrix X_⋆ ∈ ℝ^n_1× 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 X_⋆ using 𝒪 ( r(n_1+n_2)κ^2 ) measurements, where κ is the condition number of X_⋆. 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.
ER -