Fast proximal gradient methods for spectral compressed sensing via multi-block Hankel matrices

Abstract

This thesis investigates the recovery of a spectrally sparse signal (SSS) from partially observed, noisy data. Traditional compressed sensing methods encounter a basis mismatch issue due to the finite discrete dictionary. To address this, recent literature introduces grid-free approaches that exploit frequency sparsity in a continuous manner. Among these, the enhanced Hankel matrix method stands out for its improved resolution. Moreover, the algorithm involves the Hankel matrix as a whole, ensuring efficient storage and computational processes. Despite these advancements, the method shares a common drawback with Cadzow's method: reconstruction accuracy is compromised by the repeated elements in the Hankel structure. This issue is critical in scenarios where precise signal reconstruction is essential. Additionally, these methods face challenges in convergence speed, particularly when first-order methods are employed, as they tend to converge slowly in cases of low sampling ratios or significant noise.

To address these issues in spectral compressed sensing, this thesis introduces a new nonconvex optimization framework. This framework measures reconstruction error in the signal space rather than in the lifted Hankel space and incorporates an adjustable Hankel constraint parameter tailored to noise levels. To improve the slow convergence and recovery ability of standard proximal gradient (PG) methods, three advanced PG-based algorithms are proposed: low-rank projected proximal, Hankel projected proximal, and Hessian proximal gradient. These algorithms are meticulously designed to utilize the intrinsic low-rank and Hankel structures of the problem, enhancing computational efficiency. This efficiency is supported by a Julia package, available at https://github.com/xiyao65/multiblockHankelMatrices.jl. Numerical simulations demonstrate a significant improvement in both efficiency and recovery accuracy. This enhancement is particularly notable in scenarios with substantial noise or low sampling ratios, underscoring the methods' robustness and applicability for large-scale SSS recovery tasks.