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.

Our contributions We propose a new preconditioned gradient descent method for spectrally sparse signal reconstruction. Our main contributions are as follows.

• We propose a Jacobi-preconditioned gradient descent method for low-rank Hankel matrix completion, with a preconditioner derived from the Jacobi operator of a generator that maps low-dimensional factors to symmetric matrices. The algorithm maintains the low per-iteration cost of first-order methods while achieving linear convergence with a rate independent of the Hankel matrix condition number. Experiments demonstrate improvements in both iteration count and runtime over state-of-the-art methods. Moreover, the preconditioning framework also extends to other structured and general low-rank matrix recovery problems.

• We unify factorization and manifold perspectives by introducing a generator that maps factor-space iterates to their matrix-space counterparts. Under suitable retractions, the generated iterates coincide with those of manifold-based methods. This equivalence enables convergence analysis in matrix space, avoiding the need to define distances in factor space under the complex-symmetric factorization ambiguity X = ZZ = (ZQ)(ZQ) , where Q is complex orthogonal (not unitary), i.e., QQ = I. Moreover, this unification provides a principled route to preconditioning. Viewed in matrix space, it reveals how the SGD preconditioner (Tong et al., 2021) can be strengthened: our method corresponds to an orthogonal projection of the gradient onto tangent space, whereas SGD does not, yielding a new preconditioning strategy.

Notation: Bold lowercase, bold uppercase, and calligraphic letters denote vectors, matrices, and operators. For n s ∈ N, [n s ] := 0, . . . , n s -1. For matrix Z, Z , Z H , and Z denote transpose, conjugate transpose, and entrywise conjugate; its entries/rows/columns are Z i,j , Z (i,:) , and Z (:,j) . We use • , • F , and • ∞ for spectral, Frobenius, and infinity norms, and Z 2,∞ := max i Z (i,:) . Inner products x 1 , x 2 := x H 2 x 1 and Z 1 , Z 2 := trace(Z H 2 Z 1 ).

This section establishes the equivalence between factorspace and matrix-space iterations and then presents our Jacobi-preconditioned gradient descent method.

Let H * denote the adjoint of H. Define the diagonal operator D 2 = H * H and set G := HD -1 . By construction, G is an orthogonalized version of H and satisfies G * G = I. Consequently, GG * is the orthogonal projector onto the Hankel subspace. We consider the following reconstruction