Spectrally sparse signals recovered faster using new algorithm
Superfast Spectral Compressed Sensing with Quadratic Convergence
Information Theory
Summary
Recovering signals that contain only a few main frequencies can be tricky when you have limited data. The authors study this problem and create a new method that uses the hidden pattern of the signal to speed up recovery. Their algorithm runs very quickly and gets more accurate over time. It works well even with noisy or incomplete measurements, and uses less memory and computing power than before.
What this means in practice
- •For wireless communication engineers: Recover signals efficiently from limited transmission data to improve channel estimation and spectrum sensing.
- •For medical imaging developers: Reconstruct high-quality medical images from fewer scans using fast spectral compressed sensing methods to reduce patient exposure and scanning time.
Authors
Xunmeng Wu, Jian-Feng Cai, Zongben Xu, Zai Yang
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.