Lifted Restricted Isometry Property and Fast Algorithm for Spectral Compressed Sensing With Near-Optimal Sample Complexity

1 Introduction

• Recovering an r-spectrally-sparse signal from linear compressive measurements is reformulated as fixed-rank Hankel matrix recovery.The paper motivates the lift by the low rank of the Hankel matrix of a spectrally sparse signal.Source: §1 · p. 2
• LRIP constrains rank in the lifted matrix domain while measuring vectors obtained through the adjoint Hankel operator; Gaussian measurements satisfy it with O(r ln^2 N) samples.This differs from classical and matrix RIP formulations.Source: §1 · p. 2
• FIHT is introduced with two initialization schemes: one-step hard thresholding and resampling-based FIHT.Source: §1 · p. 2
• Resampling-based FIHT converges linearly with high probability using O(r ln r ln^2 N) measurements, improving the prior nonconvex Hankel methods’ order of r^2.The one-step hard-thresholding initialization instead requires O(r^2 ln^2 N) measurements.Source: §1 · p. 2
• The introduction states that numerical results in Section 5 demonstrate FIHT’s efficiency.Source: §1 · p. 2

1.1 Related Work

• Unlike atomic norm minimization, the stated FIHT recovery guarantee does not require frequency separation; unlike prior Hankel completion methods, it does not require incoherence conditions.The comparison concerns spectral recovery from linear compressive measurements.Source: §1.1 · p. 3

2 Problem Formulation and LRIP

• The Hankel operator is not an isometry because signal entries occur with different multiplicities, producing non-uniform signal-energy scaling.Source: §2 · p. 3
• Diagonal scaling yields an operator G for which G*G = I, so the scaled Hankel lift preserves the signal’s ℓ2 norm as its matrix Frobenius norm.With z = Dx and B = AD^-1, the measurements remain Bz = Ax while Gz = Hx.Source: §2 · p. 3
• A fixed-dictionary D-RIP does not directly provide a universal guarantee here because the effective dictionary varies with the unknown continuous frequencies.Source: §2 · p. 4
• LRIP imposes a rank constraint on lifted matrices while measuring their signal-domain images through G*, accounting separately for components orthogonal to the Hankel subspace.The framework uses a broader class of low-rank matrices than only exactly Hankel matrices for stability and convergence analysis.Source: §2 · p. 4
• Gaussian measurement matrices satisfy LRIP with high probability when the measurement count meets the theorem’s stated conditions.The theorem specifies conditions involving rank, matrix dimensions, and the desired probability parameters.Source: §2 · p. 5

3 Algorithm

• Because the rank constraint makes problem (5) nonconvex, the section develops a tailored FIHT algorithm for efficient recovery.The algorithm is motivated by IHT for compressed sensing and Riemannian methods for low-rank recovery.Source: §3.1 · p. 5, §3 · p. 5

3.1 FIHT Algorithm

• FIHT updates the estimate along a negative gradient, lifts it to Hankel space, projects onto the rank-r tangent space, truncates to rank r, then maps back to signal space.The algorithm uses a smaller-matrix SVD instead of an SVD of the full Hankel matrix.Source: §3.1 · p. 5

3.2 Initialization

• FIHT performance depends on initialization, and the section presents two schemes to address that dependence.They are one-step hard thresholding and resampled FIHT.Source: §3.2 · p. 6, §3.2.1 · p. 6, §3.2.2 · p. 6

3.2.1 Initialization via One-Step Hard Thresholding

• One-step hard thresholding initializes by truncating the Hankel matrix formed from B^H y; it is easy to implement but yields quadratic sample-complexity dependence on r.Source: §3.2.1 · p. 6

3.2.2 Initialization via Resampling

• Resampled initialization partitions measurements into disjoint batches and uses fresh measurements for each refinement, removing dependence between the current iterate and its update measurements.The resampling-based initialization is the output of Algorithm 2.Source: §3.2.2 · p. 6
• Resampling targets reducing the sample-complexity dependence on r^2 to r, unlike, where it removes a dependence on √N that does not arise here.Fresh measurements break the dependence between the current iterate and the measurements used in an update, enabling a sharper spectral concentration bound.Source: §3.2.2 · p. 6

• For r ≥ 2, the resampling theorem sets T = ⌈ln r⌉−1 and initializes FIHT with L0 = eLT.Source: §4 · p. 7
• For r = 1, the resampling theorem gives the same convergence and probability bounds with T = 0 when m ≥ Cκ^2 max{cs, ln N} ln N.Source: §4 · p. 7
• O(r ln r) rather than O(r^2) dependence on r: resampled FIHT improves sparsity scaling while retaining exact recovery and linear convergence, near-optimal up to logarithmic factors.Source: §4 · p. 7

5 Numerical Results

• The numerical evaluation compares FIHT with Hankel-NNM and ANM, using an iterative stopping rule or a 1000-iteration cap for FIHT.The stopping rule is relative iterate change at most 10^-8; the convex methods use SDPT3 within CVX.Source: §5 · p. 8

5.1 Phase Transition

• FIHT achieves phase-transition performance comparable to Hankel-NNM under both initialization schemes while significantly outperforming ANM.The comparison is shown in Figure 1; the paper notes that ANM requires a minimum frequency-separation condition.Source: Figure 1 · p. 8, §5.1 · p. 9

5.2 Computational Time

• FIHT is significantly faster than Hankel-NNM and ANM across the tested signal lengths and sparsity levels.Figure 2 reports average computational time over 50 trials in which all compared methods successfully recover the signal.Source: §5.2 · p. 9, Figure 2 · p. 9

5.3 Robustness to Noise

• FIHT achieves the lowest estimation error as SNR varies in the noisy-recovery experiments.Figure 3 reports mean RMSE over 50 trials for m = 80 and m = 100.Source: Figure 3 · p. 9, §5.3 · p. 10

6.1 Proof of Theorem 1

• The LRIP proof controls a quadratic Gaussian chaos process through Talagrand’s γ2 functional and a sharp Gaussian-width bound for a structured set.The width bound relies on a spectral-norm estimate for random rectangular Hankel matrices; for square Hankel matrices, the stated sample condition is m ≥ Cδ^-2r ln^2 N at the specified probability.Source: §6.1 · pp. 10, 11, 13

6.2 Proof of Theorem 2

• When the initial estimate lies within the basin of attraction and the rank-4r LRIP constant is below 1/8, FIHT converges linearly to the true signal.The proof also bounds the initial estimate’s Frobenius error relative to the true Hankel matrix.Source: §6.2 · p. 13

6.3 Proof of Theorem 3

• The resampling proof bounds the spectral-norm error of the initializer and of the output of Algorithm 2 under per-batch sample requirements.The bounds in Lemmas 7 and 8 use a per-batch requirement involving κ^2r max{c_s, ln N} ln N; the theorem argument combines these events with LRIP to obtain its recovery guarantee.Source: §6.3 · pp. 13–14

7 Conclusion

• The conclusion presents LRIP as a theoretical tool for Gaussian-measurement Hankel recovery and FIHT as an exact-recovery method with sample complexity of order r ln r, improving on the order r^2 of previous nonconvex Hankel methods.Numerical experiments show competitive phase transitions and significantly greater computational efficiency than existing convex optimization methods.Source: §7 · p. 14

A Proof of Lemma 4

• The proof writes the random Hankel matrix as a matrix Gaussian series, bounds its matrix variance statistic, and applies a norm bound involving ln(n1 + n2).The variance calculation uses the diagonal structure obtained from the Hankel-series representation.Source: A Proof of Lemma 4 · pp. 14–15

B Implementation of FIHT

• The rank-r iterate is stored by its reduced SVD, with factors U_t and V_t in the stated matrix dimensions.The tangent space at the iterate is also specified, and W_t is stored using a decomposition.Source: B Implementation of FIHT · p. 16
• O(rN log N) flops suffice for the Hankel matrix-matrix multiplications, computed via FFT without explicitly forming the Hankel matrix.The passage also notes additional matrix multiplications and a 2r × 2r SVD, but their costs are incomplete.Source: B Implementation of FIHT · p. 16
• The stepsize term P_Tt G g_t can be stored and computed in the same manner as in (25).The implementation details are described as following those in.Source: B Implementation of FIHT · p. 16

C Proof of Lemma 5

• When δ4r ≤ 1/8, the error recurrence has factor v = 2δ4r + 1/2 < 1, yielding the claimed bound by induction.The proof uses the best rank-r approximation property and Lemmas 10 and 11 in deriving the recurrence.Source: C Proof of Lemma 5 · p. 17

D Proof of Lemma 6

• For Lemma 6, the proof projects onto the span of the column spaces of L0 and Gz⋆, whose basis has 2r columns.It invokes the best rank-r approximation property and Lemma 12 to bound the comparison.Source: D Proof of Lemma 6 · p. 18

G.3 Proof of Lemma 14

• For isotropic complex Gaussian g, the projections onto a fixed vector's span and its orthogonal complement are independent.The proof reduces to the first coordinate by rotational invariance, then uses zero cross-covariance.Source: E Proof of Lemma 7 · p. 18, §G.3 · p. 21

E Proof of Lemma 7

• Lemma 7 relies on a non-uniform spectral-norm bound for a fixed rank-r matrix independent of the measurement matrix.The bound is identified as key to the proofs of Lemmas 7 and 8.Source: E Proof of Lemma 7 · p. 19

F Proof of Lemma 8

• The Lemma 8 proof applies the fixed-matrix bound to an iterate error independent of fresh Gaussian measurements, under its stated sample-size condition.It combines Lemma 7 with intermediate bounds to conclude (21).Source: F Proof of Lemma 8 · pp. 19–20

G.1 Proof of Lemma 10

• The proof of Lemma 10 uses the polarization identity in establishing its projection bound.The passage defines α = ∥X∥F and β = ∥P_Tt Z∥F for the argument.Source: §G.1 · p. 20

G.2 Proof of Lemma 12

• Lemma 12 applies LRIP using the condition rank(P_S Z) ≤ 2r for the subspace projection.The proof invokes this rank condition in its first inequality.Source: §G.2 · p. 21

G.4 Proof of Lemma 15

• m ≥ 64Cc^-2r(cs + ln N) ln N suffices for the stated bound, with probability at least 1 − N^-(cs+ln N).The proof conditions on X and separates the component along G*X from its orthogonal component before applying Gaussian concentration.Source: §G.4 · pp. 21, 23