Lifted Restricted Isometry Property and Fast Algorithm for Spectral Compressed Sensing With Near-Optimal Sample Complexity
Abstract
This paper studies the spectral compressed sensing problem, which aims to recover an r-spectrally-sparse signal of length N from linear compressive measurements. We reformulate the problem as the recovery of a low-rank Hankel matrix. Motivated by this formulation, we propose a Lifted Restricted Isometry Property (LRIP) for the measurement matrix and show that Gaussian measurement matrices satisfy LRIP under certain conditions. Unlike classical RIP, LRIP imposes a rank constraint in the lifted matrix domain while taking measurements in the signal domain through the adjoint Hankel operator. To solve the resulting nonconvex problem efficiently, we introduce a Fast Iterative Hard Thresholding (FIHT) algorithm. Based on LRIP, we show that FIHT converges linearly to the true signal with high probability using 𝒪(r ln r ln2 N) scaled Gaussian measurements, which is near-optimal up to log factors and improves the state-of-the-art order of r2 for nonconvex Hankel methods. Extensive numerical results demonstrate the superiority of FIHT as compared to state-of-the-art convex methods in terms of phase transitions, computational time, and robustness to noise.
Related
- Sharp Restricted Isometry Thresholds for Global Minima of Rank-Restricted Matrix LASSO
- Rank-one Factored Gradient Descent without Restricted Isometry: Application to Quantum Pure State Tomography on Multi-Qubits
- The Haagerup property is not invariant under quasi‐isometry
- Isometry Groups of Right Invariant Metrics in Geometric Quantum Complexity
- Fourier Ratio and Restricted Isometry via Entropic Descent
BibTeX
@misc{wu2026lifted,
title = {{Lifted Restricted Isometry Property and Fast Algorithm for Spectral Compressed Sensing With Near-Optimal Sample Complexity}},
author = {Xunmeng Wu and Jian-Feng Cai and Zongben Xu and Zai Yang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.18032},
eprint = {2610.18032},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.18032},
}
RIS
TY - UNPB
TI - Lifted Restricted Isometry Property and Fast Algorithm for Spectral Compressed Sensing With Near-Optimal Sample Complexity
AU - Xunmeng Wu
AU - Jian-Feng Cai
AU - Zongben Xu
AU - Zai Yang
PY - 2026
DA - 2026/10/13
PB - arXiv
DO - 10.48550/arxiv.2610.18032
UR - https://arxiv.org/abs/2610.18032
AB - This paper studies the spectral compressed sensing problem, which aims to recover an r-spectrally-sparse signal of length N from linear compressive measurements. We reformulate the problem as the recovery of a low-rank Hankel matrix. Motivated by this formulation, we propose a Lifted Restricted Isometry Property (LRIP) for the measurement matrix and show that Gaussian measurement matrices satisfy LRIP under certain conditions. Unlike classical RIP, LRIP imposes a rank constraint in the lifted matrix domain while taking measurements in the signal domain through the adjoint Hankel operator. To solve the resulting nonconvex problem efficiently, we introduce a Fast Iterative Hard Thresholding (FIHT) algorithm. Based on LRIP, we show that FIHT converges linearly to the true signal with high probability using 𝒪(r ln r ln^2 N) scaled Gaussian measurements, which is near-optimal up to log factors and improves the state-of-the-art order of r^2 for nonconvex Hankel methods. Extensive numerical results demonstrate the superiority of FIHT as compared to state-of-the-art convex methods in terms of phase transitions, computational time, and robustness to noise.
ER -