Source-linked AI summary
Superfast Spectral Compressed Sensing with Quadratic Convergence
Xunmeng Wu, Jian-Feng Cai, Zongben Xu, Zai Yang
TL;DR
Spectral compressed sensing seeks to recover spectrally sparse signals from linear measurements, while prior FIHT has only linear convergence and unclear noisy-setting guarantees. The paper formulates a fixed-rank Hankel-regularized problem and proposes SIHT; it reports quadratic convergence, exact noiseless and stable noisy recovery, and near-optimal sample complexity under Gaussian measurements.
Problem
Recovering a spectrally sparse signal from linear measurements remains challenging because the sparsity constraint is implicit, and FIHT has only linear convergence with unclear noisy-setting guarantees.
Source: §1 · pp. 1–2Method
SIHT optimizes a Hankel-regularized fixed-rank model using tangent-space least-squares updates followed by fixed-rank hard-thresholding projections.
Source: §1 · p. 2Results
SIHT has provable quadratic convergence and achieves exact noiseless recovery and stable noisy recovery with near-optimal sample complexity under Gaussian measurements.
Source: §1 · p. 2, §8 · p. 15Takeaways & Limitations
SIHT combines near-optimal sample complexity with state-of-the-art computational and memory efficiency for spectral compressed sensing.
Source: §8 · p. 15The simple initialization scheme generally has suboptimal sample complexity that scales quadratically with rank r; resampling is used for near-optimal scaling.
Source: §3.2 · p. 6
Abstract
from arXiv · showhide
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.
1. Introduction.
Spectral compressed sensing reconstructs spectrally sparse signals from linear measurements, but the sparsity constraint is difficult to handle directly. SIHT uses a fixed-rank Hankel formulation and is presented as a quadratically convergent method with improved iteration complexity over FIHT.
1. Introduction.
- The signal is a superposition of complex exponentials, and its spectral sparsity is characterized by low-rank Hankel structure.The paper notes that the spectral-sparsity constraint is implicitly defined and difficult to handle in the signal domain.Source: §1 · p. 1
- Earlier convex Hankel NNM and atomic norm methods are typically solved as semidefinite programs, with computational complexity O(N^3).FIHT has nearly linear per-iteration cost, but its convergence is only linear and its noisy-setting guarantees remain unclear.Source: §1 · p. 2
- SIHT is the first nonconvex algorithm reported with provable quadratic convergence for spectral compressed sensing.Its model incorporates the Hankel constraint through regularization on a fixed-rank manifold.Source: §1 · p. 2
- Each SIHT iteration solves a tangent-space least-squares subproblem and then projects by fixed-rank hard thresholding.A parameterized conjugate-gradient method and low-rank tangent-space structure enable nearly linear-in-N cost and memory scaling.Source: §1 · pp. 2–3
- Compared with FIHT, SIHT improves iteration complexity from log to double-log while retaining the same sample complexity and memory scaling.Table 1 compares representative methods under noiseless Gaussian measurements.Source: §1 · p. 3, Table 1 · p. 3
2. Optimization Model and Performance.
The section recasts spectral recovery as a fixed-rank optimization with a quadratic Hankel regularizer, then establishes recovery-error guarantees for the original and relaxed models.
2.1. Optimization Model.
- The model separates the fixed-rank and Hankel constraints, then relaxes the Hankel constraint with a quadratic regularization term.Scaling the Hankel operator yields an isometry, and the transformed variables express the measurement and Hankel structure in the lifted formulation.Source: §2.1 · pp. 3–4, §2 · p. 3
2.2. Model Performance.
- The original and relaxed models have recovery-error bounds that are tight up to constant factors, and the relaxed model has the same recovery guarantee as the original.The theorem assumes the sensing operator satisfies LRIP of rank 2r.Source: §2.2 · pp. 4–5
- For Gaussian sensing matrices, the stated LRIP result holds with sufficient sample count scaling with r and logarithmic factors in N.The LRIP condition is introduced as a theoretical tool for analyzing low-rank Hankel recovery.Source: §2.2 · p. 4
- The recovery bounds’ linear dependence on noise norm is optimal in the deterministic worst case.The paper establishes this using a deterministic lower bound alongside the model guarantees.Source: §2.2 · p. 5
3. Algorithm.
SIHT solves a tangent-space least-squares problem before projecting back to rank r, and its convergence is quadratic rather than FIHT’s linear rate. Initialization affects the recovery guarantee: resampling supports near-optimal sample complexity, while one-step hard thresholding generally has a rank-quadratic guarantee.
3.1. SIHT Algorithm.
- SIHT alternates a tangent-space-constrained least-squares update with projection onto the rank-r matrix manifold.The projection uses the best rank-r approximation obtained by truncated SVD.Source: §3.1 · p. 5
- SIHT solves the least-squares subproblem exactly and achieves quadratic convergence, whereas FIHT performs one Riemannian gradient step and converges linearly.Source: §3.1 · p. 6
3.2. Initialization.
- One-step hard-thresholding initialization is simple, but its recovery guarantee generally requires sample complexity scaling quadratically with rank r.Source: §3.2 · p. 6
- Resampling initialization uses a resampled FIHT output and makes each iterate independent of the fresh measurements used next, supporting near-optimal sample complexity linear in r up to log factors.Source: §3.2 · p. 6
4. Recovery Guarantee.
Under the stated Gaussian measurement and noise assumptions, SIHT provides recovery guarantees for both initializations. The results include quadratic convergence without noise, stable recovery with noise, and near-optimal sample complexity in the low-noise regime for resampling initialization.
Recovery guarantees
- The guarantees assume i.i.d. complex Gaussian sensing entries and, for noisy measurements, i.i.d. complex Gaussian noise.Source: §4 · p. 6
- In the noiseless setting, SIHT achieves quadratic convergence, improving on FIHT’s linear convergence.The theorem’s convergence statement gives an iteration bound for an ε-accurate solution.Source: §4 · p. 7
- With Gaussian noise, SIHT achieves stable recovery, with the error rapidly bounded by a constant multiple of the noise level σ.The first term in the recovery bound decays doubly exponentially with iterations.Source: §4 · p. 7
- In the low-noise regime, resampling initialization yields sample complexity near-optimal up to conditioning and logarithmic factors, scaling linearly with r.Source: §4 · pp. 6–7
5. Efficient Implementation.
SIHT’s implementation solves its tangent-space least-squares subproblem with parameterized conjugate gradients and computes the rank-r projection from low-rank factors. These steps yield per-iteration cost and memory scaling that are nearly linear in signal dimension N.
5.1. Step 1: Parameterized Conjugate Gradient (CG) Algorithm for solving (3.1).
- CG solves the tangent-space linear system without explicitly forming or inverting its high-dimensional operator; bounded conditioning gives dimension-independent linear convergence.Each CG iteration costs O(mN + rN log N) flops using FFT-based operations.Source: §5.1 · pp. 7, 9
- Parameterized CG represents tangent-space variables using pairs (q, σ), reducing storage to 2N + r real degrees of freedom and avoiding full-matrix storage.It also eliminates the need for a truncated SVD of the full intermediate matrix.Source: §5.1 · p. 8
5.2. Step 2: Efficient SVD via Low-Rank Structure.
- The rank-r projection is computed from a low-rank factorization of the intermediate matrix by taking the SVD of a 2r × 2r matrix and retaining its leading r singular components.Source: §5.2 · p. 10
5.3. Complexity of SIHT.
- With a fixed maximum number of CG iterations, SIHT costs O(mN + rN log N + r^2N + r^3) per outer iteration and uses O(mN + rN) memory.Source: §5.3 · p. 10
6. Numerical Experiments.
The experiments evaluate SIHT against FIHT and convex methods, finding quadratic convergence and strong recovery accuracy alongside lower computational time. The reported comparisons cover convergence, noiseless phase transitions, and robustness to noise.
6. Numerical Experiments.
- The evaluation compares SIHT with FIHT, Hankel-NNM, and ANM, measuring recovery accuracy by relative RMSE.SIHT uses one-step hard-thresholding initialization; FIHT uses the same initialization and stopping criteria.Source: §6 · p. 10
6.1. Convergence Performance.
- SIHT achieves quadratic convergence to machine precision without noise and to a noise-determined error floor with noise; FIHT converges linearly.SIHT also requires substantially less runtime than FIHT to reach the same RMSE.Source: §6.1 · p. 11, Figure 1 · p. 11
6.2. Phase Transition.
- SIHT achieves slightly better noiseless recovery than FIHT and Hankel-NNM, and substantially outperforms ANM.Success is defined as relative RMSE below 10^-3; phase-transition success rates are estimated over 20 trials per (m, r) pair.Source: §6.2 · p. 11, Figure 2 · p. 12
6.3. Robustness to Noise.
- SIHT and FIHT achieve nearly identical accuracy across SNRs, while SIHT uses the least computational time among the compared methods.The comparison uses m = 80 and r = 5, with SNR from 5 dB to 30 dB.Source: §6.3 · pp. 11–12, Figure 3 · p. 12
7. Proof of Theorem 4.1.
The proof establishes local quadratic convergence under a restricted isometry condition, then controls initialization error to place the iterate within that convergence neighborhood. It treats one-step and resampling initializations.
7. Proof of Theorem 4.1.
- The proof separates into local quadratic convergence near the ground truth and a demonstration that initialization lies within that neighborhood.The local result is then combined with the initialization bounds to prove the main theorem.Source: §7 · pp. 12–13
7.1. Local Quadratic Convergence.
- Under the 3r-LRIP with δ3r < 1, Theorem 7.2 establishes local quadratic convergence.The tangent-space restricted isometry result supplies uniqueness for the least-squares subproblem under the stated rank-2r LRIP condition.Source: §7.1 · p. 13, §7 · p. 13
7.2. Initialization Error.
- The initialization analysis includes Gaussian-noise concentration and upper bounds for one-step and resampling initialization errors.The resampling bound extends the corresponding FIHT result to the noisy setting.Source: §7.2 · pp. 13–14
7.3. Proof of Theorem 4.1.
- For one-step initialization, the proof controls two error terms and combines their measurement conditions with the local theorem; for resampling, it uses the resampling bound and the resampling budget.The proof relates signal-space error to lifted-matrix Frobenius error using zt = G*Xt and G*G = I.Source: §7.3 · p. 14
8. Conclusion.
The paper concludes that SIHT is the first nonconvex algorithm for spectral compressed sensing with provable quadratic convergence, and reports near-optimal sample complexity with computational and memory efficiency.
8. Conclusion.
- SIHT is presented as the first nonconvex algorithm for spectral compressed sensing with provable quadratic convergence.The conclusion identifies second-order fast algorithms for low-rank Hankel matrix completion as a future direction.Source: §8 · p. 15
- SIHT achieves near-optimal sample complexity together with state-of-the-art computational and memory efficiency.The conclusion also reports that numerical experiments demonstrated SIHT's superiority.Source: §8 · p. 15
- Developing second-order fast algorithms for low-rank Hankel matrix completion is identified as future work.Source: §8 · p. 15
Appendix A. Proof of Theorem 2.3.
The appendix bounds the initial recovery error using measurement and noise inequalities, and constructs indistinguishable models to establish a lower-bound argument. It also characterizes the tangent-space operator through its spectrum.
Appendix A. Proof of Theorem 2.3.
- The proof uses measurement-error inequalities to derive an upper bound on the initial signal error under the LRIP.The argument starts from optimality and feasibility, then combines the resulting measurement bound with a second inequality.Source: Appendix A · p. 15
Appendix B. Proof of Theorem 2.4.
- Two models with equal observations, rank-r signals, and noise norms ε provide the indistinguishability construction.The argument notes that the signal and noise supports are disjoint when r < min{n1, n2}.Source: Appendix B · p. 15
- For the tangent-space operator, the proof reduces the restricted-isometry claim to showing its spectrum lies in [1 − δ2r, 1 + δ2r].Source: Appendix B · p. 15
Appendix C. Proof of Lemma 7.1.
The appendix establishes invertibility of the tangent-space operator and supplies proof bounds for convergence, concentration, and initialization. These arguments use the low-rank structure and Gaussian measurement assumptions where stated.
Appendix C. Proof of Lemma 7.1.
- δ2r < 1 makes M positive definite on T, so M is invertible there.The proof then uses this invertibility to solve for an arbitrary X ∈ T.Source: Appendix C · p. 16
Appendix D. Proof of Theorem 7.2.
- The Theorem 7.2 proof uses tangent-space optimality and best rank-r approximation to bound the iterate error.The approximation step applies because Xt+1 is the best rank-r approximation to Wt+1 and both Xt+1 and Gz⋆ have rank r.Source: Appendix D · pp. 16–17
Appendix E. Proof of Lemma 7.3.
- Gaussian concentration and integration yield the bound in Lemma 7.3 under the stated sample-size condition.The derivation conditions on ξ and uses m ≥ (cs + log N) log N ≥ log 2.Source: Appendix E · pp. 17–18
Appendix F. Proof of Lemma 7.4.
- The argument uses Q spanning the column subspaces of X0 and Gz⋆; its projection PQ has rank at most 2r, and applying [24, Lemma 12] yields (7.2).Source: Appendix F · p. 18
Appendix G. Resampled FIHT Algorithm and Proof of Lemma 7.5.
Appendix G describes resampled FIHT initialization and its proof. The proof partitions measurements across iterations and bounds initialization and iteration errors with high probability.
Resampled FIHT setup
- The measurements are split into T + 1 disjoint batches, each containing ˜m samples, for resampled FIHT.The algorithm uses the tangent space at ˜Xt for its iteration update.Source: Appendix G · pp. 18–19
Proof of Lemma 7.5
- In Algorithm G.1, the initialization error can be bounded from yt = Btz⋆ + ξt.Entries of Bt and ξt are i.i.d. CN(0, 1/˜m) and CN(0, σ2/˜m), respectively.Source: Appendix G · p. 19
- The iteration bound holds with probability at least 1 − 2N −(cs+log N), completing the proof of Lemma 7.5.The passage attributes the bound to [24, Proof of Lemma 8] and Lemma 7.3.Source: Appendix G · p. 19