Fast Spectrally Sparse Signal Reconstruction via Jacobi-Preconditioned Gradient Descent

Spectrally sparse signal reconstruction arises in a wide range of applications and can be formulated as a low-rank Hankel matrix completion problem. We develop a Jacobi-preconditioned gradient descent method that preserves the low per-iteration complexity of first-order algorithms while achieving linear convergence at a rate independent of the condition number. By introducing a generator that maps factor-based iterates to matrix space, we establish equivalence with manifold-based methods, enabling direct convergence analysis while avoiding the need to define distances under complex-symmetric factorization ambiguity. Extensive experiments demonstrate that the proposed algorithm outperforms state-of-the-art methods in both iteration count and computational time across a broad range of problem settings.

Recovering signals from incomplete measurements is important in applications such as imaging, sensing, and spectroscopy. In many cases, a signal contains only a few frequency components, giving it a hidden structure that algorithms can exploit. However, existing reconstruction methods can slow down in difficult cases where the problem is unevenly scaled. We develop a faster method for this reconstruction problem. Our approach improves gradient descent, a widely used optimization strategy, by adding a balancing step that helps the algorithm move efficiently while keeping each iteration inexpensive. As a result, the method converges quickly even in challenging settings where existing approaches slow down. We also introduce a mathematical viewpoint that connects our algorithm to a related family of geometric optimization methods. This connection helps us prove why the method works while avoiding technical difficulties that usually arise in this type of analysis. Across many experimental settings, our algorithm recovers signals using fewer iterations and less computation time than leading existing methods.