Superfast Spectral Compressed Sensing with Quadratic Convergence
Abstract
In this paper, we study the spectral compressed sensing problem of recovering a spectrally sparse signal from linear compressive measurements. Exploiting the low-rank Hankel structure associated with the signal, we formulate a nonconvex fixed-rank optimization problem with a Hankel regularization. We propose a Superfast Iterative Hard Thresholding (SIHT) algorithm, where each iteration consists of a tangent-space least-squares update followed by a fixed-rank hard thresholding projection. SIHT is the first nonconvex algorithm with provable quadratic convergence for spectral compressed sensing. For random Gaussian measurements, it achieves exact recovery in the noiseless case and stable recovery in the noisy case with near-optimal sample complexity. To efficiently implement SIHT, we develop a parameterized conjugate gradient method for solving the least-squares subproblem, endowing SIHT with state-of-the-art computational and memory efficiency. Numerical experiments are provided to validate our results.
Related
- Lifted Restricted Isometry Property and Fast Algorithm for Spectral Compressed Sensing With Near-Optimal Sample Complexity
- Spectral convergence associated with Weil's quadratic form
- Global and Unconditional R-Linear Convergence of Rank-Compressed Weighted LMSD Sweeps for Strictly Convex Quadratics
- Recovery Guarantees for Posterior Sampling of One-Bit Compressed Sensing
- Phase Transition in Binary Compressed Sensing via Annealing with Adaptive Regularization
BibTeX
@misc{wu2026superfast,
title = {{Superfast Spectral Compressed Sensing with Quadratic Convergence}},
author = {Xunmeng Wu and Jian-Feng Cai and Zongben Xu and Zai Yang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.21068},
eprint = {2610.21068},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.21068},
}
RIS
TY - UNPB
TI - Superfast Spectral Compressed Sensing with Quadratic Convergence
AU - Xunmeng Wu
AU - Jian-Feng Cai
AU - Zongben Xu
AU - Zai Yang
PY - 2026
DA - 2026/10/15
PB - arXiv
DO - 10.48550/arxiv.2610.21068
UR - https://arxiv.org/abs/2610.21068
AB - In this paper, we study the spectral compressed sensing problem of recovering a spectrally sparse signal from linear compressive measurements. Exploiting the low-rank Hankel structure associated with the signal, we formulate a nonconvex fixed-rank optimization problem with a Hankel regularization. We propose a Superfast Iterative Hard Thresholding (SIHT) algorithm, where each iteration consists of a tangent-space least-squares update followed by a fixed-rank hard thresholding projection. SIHT is the first nonconvex algorithm with provable quadratic convergence for spectral compressed sensing. For random Gaussian measurements, it achieves exact recovery in the noiseless case and stable recovery in the noisy case with near-optimal sample complexity. To efficiently implement SIHT, we develop a parameterized conjugate gradient method for solving the least-squares subproblem, endowing SIHT with state-of-the-art computational and memory efficiency. Numerical experiments are provided to validate our results.
ER -