PaperlayerView exact revision on arXiv

Source-linked AI summary

Cadzow Projected Gradient Descent for Generalized Finite Rate of Innovation: A Quantitative Local Convergence Theory

Adrien Besson

arXiv:2609.02921v1eess.SP

TL;DR

GenFRI reconstructs finite-rate-of-innovation signals from noisy linear measurements, but existing approaches have limited convergence guarantees. The paper reformulates recovery through Cadzow-denoiser fixed points and proves localized linear convergence for GCPGD with a noise-proportional error floor.

  • Problem

    GenFRI methods address linear distortions, but the original algorithms rely on non-convex heuristics, multiple random initializations, and sensitive tuning, without formal convergence guarantees.

    Source: §I · p. 1

  • Method

    The paper recasts GenFRI recovery through the Cadzow denoiser’s fixed-point set and equips GCPGD with Γ-metric preconditioning.

    Source: §V · pp. 9–10

  • Results

    GCPGD converges linearly from any initialization within an explicit basin of attraction to an asymptotic reconstruction error floor proportional to noise.

    Source: §I · p. 2, §V · p. 10

  • Takeaways & Limitations

    The authors characterize this localized result as the first quantitative convergence guarantee in the GenFRI setting.

    Source: §V · p. 10

    The explicit basin condition depends on a radius r0 that is non-computable and whose required lower bound is not verifiable for a given instance.

    Source: §III · p. 7

Abstract

from arXiv · show

The generalized finite rate of innovation~(GenFRI) framework aims at reconstructing finite-rate-of-innovation~(FRI) signals measured through a noisy linear measurement model. GenFRI has been recently recast as a structured low-rank optimization problem and the Cadzow projected gradient descent~(CPGD) algorithm has been suggested to solve it. While CPGD works well in practice, only qualitative local convergence guarantees have been established. We revisit GenFRI in the light of the regularization by denoising framework, recasting it as an optimization problem whose solutions lie in the fixed-point set of the Cadzow denoiser. We show that no algorithm in this family can enjoy global guarantees, and establish instead that the Cadzow denoiser is quasi-nonexpansive on an explicit neighborhood of the FRI model set, whose radius is governed by the conditioning of the underlying Dirac stream. Building on these results, we propose the generalized CPGD~(GCPGD) algorithm and prove its convergence from any initialization within an explicit basin of attraction, together with a reconstruction error bound proportional to the noise level. Numerical experiments validate the predicted contraction rates, recovery thresholds, and run-time certificates, and show that a single run of GCPGD outperforms state-of-the-art GenFRI algorithms.

I. INTRODUCTION · II. ON QUASI-NONEXPANSIVENESS OF CADZOW DENOISING · A. Preliminaries

The paper develops quantitative local convergence guarantees for GenFRI by analyzing Cadzow denoising near the FRI model set and introducing preconditioned GCPGD. Its preliminaries define the weighted geometry and spectral tube used to state those guarantees.

I. INTRODUCTION

  • GenFRI recovers Fourier coefficients and Dirac parameters from noisy linear measurements, addressing distortions that can destroy the Toeplitz or Hankel structure required by classical subspace methods.The model is y = Gx + ϵ, and recovery is posed as structured low-rank approximation with a non-convex rank-K constraint.Source: §I · p. 1
  • Earlier GenFRI methods rely on non-convex heuristics with random restarts and sensitive tuning, while CPGD has only qualitative, difficult-to-verify local fixed-point guarantees,.The paper presents its theory as a quantitative local alternative to those guarantees.Source: §I · pp. 1–2
  • Global regularity assumptions used by classical fixed-point and RED frameworks fail structurally because Cadzow rank projection is discontinuous and its fixed-point set is non-convex.The paper recasts GenFRI reconstruction as optimization over the Cadzow denoiser’s fixed-point set [19],.Source: §I · p. 2

II. ON QUASI-NONEXPANSIVENESS OF CADZOW DENOISING

  • Cadzow denoising is locally quasi-nonexpansive in an explicit spectral tube around the FRI model set, with a singular-value-gap-ratio certificate for localization.The tube formalizes the no-subspace-swap region associated with breakdown of subspace-based FRI estimation.Source: §I · p. 2, A. Preliminaries · p. 2

I. INTRODUCTION

  • GCPGD converges linearly from any initialization in an explicit basin to a reconstruction error floor proportional to noise, with Γ-metric preconditioning.The analysis also derives computable SNR thresholds from minimum Dirac separation and amplitude dynamic range.Source: §I · p. 2

A. Preliminaries

  • The preliminaries equip coefficient vectors with a Γ-weighted norm that makes Toeplitzification an isometry, with convergence statements transferable to the usual Euclidean norm.Γ weights each coefficient by the number of times it appears in the Toeplitz lift; the induced and Euclidean norms are equivalent.Source: A. Preliminaries · p. 2
  • The preliminaries distinguish the FRI model set from the larger rank-K Toeplitz variety and define a gap-ratio-based tube around the model set for local analysis.Leaving the tube corresponds to a subspace-swap event, the breakdown mechanism identified for subspace-based FRI estimation.Source: A. Preliminaries · p. 2

B. On Quasi-Nonexpansiveness of Cadzow Denoising

Cadzow denoising has no global regularity because its rank projection is discontinuous at spectral ties, but it admits quantitative local convergence guarantees near nontangential FRI model points. The local basin depends on Dirac-stream conditioning, and an online certificate can verify an error-drift bound during execution.

B. On Quasi-Nonexpansiveness of Cadzow Denoising

  • For matrices with σ_K+1 < σ_K, projection onto the rank-K set exists and is unique, despite the projection’s nonconvexity and possible nonuniqueness elsewhere.The analysis therefore confines global claims to a tube where the spectral gap is bounded away from zero.Source: B. On Quasi-Nonexpansiveness of Cadzow… · p. 3
  • No global Lipschitz constant exists for the rank projection or Cadzow denoiser, because the projection jumps across matrices with σ_K = σ_K+1.The rank projection is uniquely determined on either side of the tie set, so tie-breaking cannot remove the discontinuity.Source: B. On Quasi-Nonexpansiveness of Cadzow… · p. 3
  • At nontangential model points, the Toeplitz and rank constraints intersect in excess dimension, so standard transversal constraint qualifications are unavailable.Nontangentiality is verifiable for an instance, and its angle constant remains bounded away from 1 as Diracs collide; σ_K, rather than that constant, governs the basin.Source: B. On Quasi-Nonexpansiveness of Cadzow… · pp. 3–4
  • Within an explicit spectral tube around a rank-K nontangential model point, Cadzow is approximately quasi-nonexpansive and contracts distance to the model variety at a linear per-cycle rate.The theorem applies to inputs within a radius bounded by the spectral-tube and local-convergence radii; approximate quasi-nonexpansiveness becomes exact as ε→0.Source: B. On Quasi-Nonexpansiveness of Cadzow… · p. 4
  • As Diracs collide, the convergence basin closes because σ_K vanishes, while the nontangential radius and angle constant remain bounded.The effective basin radius scales with σ_K; nontangentiality does not degrade in the collision limit.Source: B. On Quasi-Nonexpansiveness of Cadzow… · p. 4
  • An a posteriori certificate validates the theorem’s drift bound at zero additional cost by checking a quantity computed from singular values already available during Cadzow iterations.The certificate uses the gap ratios ρ(M_k) and validates the drift bound when ε̂(x) ≤ ε; weighted Γ-distance also avoids the denoiser scaling used in.Source: B. On Quasi-Nonexpansiveness of Cadzow… · p. 4

III. GENERALIZED CADZOW-PROJECTED GRADIENT DESCENT

The section develops GCPGD for GenFRI and establishes local convergence and noise robustness, while showing why global fixed-point convergence guarantees do not apply. It also gives explicit conditions tied to Dirac-stream conditioning and specializes the theory to vanilla FRI denoising.

Fixed-point formulation and limitation

  • The Cadzow fixed-point set is non-convex, so its denoiser cannot be globally demicontractive and the global RED-PRO convergence hypotheses of fail.Averaging two generic K-Dirac streams produces a Toeplitz matrix of rank 2K; the analysis therefore localizes around the FRI model set.Source: §III · pp. 4–5

Generalized CPGD

  • GCPGD uses a Γ-weighted, preconditioned gradient step that avoids metric mismatch, while relaxation damps denoiser drift at the cost of weaker limit-point model consistency.With Γ = I and α = 1, the method recovers CPGD; the metric, explicit step size, and relaxation drift damping drive GCPGD's provable improvement over CPGD.Source: §III · pp. 5, 7

Local convergence and stability

  • Under nontangentiality, positive restricted injectivity, and sufficiently small initialization error and noise, GCPGD stays in its local basin and converges linearly to a noise floor.The basin and admissible noise level scale with the smallest nonzero singular value σ_K of the underlying Dirac stream, and the limit-point reconstruction error is linear in the noise level.Source: §III · pp. 5–6

Explicit convergence conditions

  • The explicit convergence conditions require Rayleigh-type Dirac separation, nontangentiality, and full-column-rank measurements, with a noise threshold linked to amplitudes and oversampling.The threshold is expressed through physical signal parameters, but its certificate still requires an uncomputable local radius; in the compressive regime, full-ball injectivity vanishes and the Fourier secant-constant guarantee remains open.Source: §III · pp. 6–7

Vanilla FRI denoising

  • For vanilla FRI denoising, GCPGD reaches tolerance tol in O(P ln (1/tol)) iterations, and choosing P = M maximizes noise tolerance at an O(M) rate.The stopping criterion estimates when further iterations begin overfitting noise, and singular values of the lifted noisy signal enable adaptive model-order selection.Source: §III · p. 7

IV. EXPERIMENTS

The experiments test theoretical predictions and compare GCPGD with CPGD and GenFRI. Except in Section IV-D, each experiment overlays a theoretically predicted quantity with its empirical measurement.

IV. EXPERIMENTS

  • Experiments assess theoretical predictions and compare GCPGD against CPGD and GenFRI; all but Section IV-D overlay a predicted quantity with its empirical measurement.Each figure caption names the corresponding theoretical statement.Source: §IV · p. 7
  • The experiments use irregular time sampling with θ_l drawn uniformly from [0, 1), and Gaussian noise with standard deviation σ_n = max_k|x_k| exp(−PSNR/10).Source: §IV · p. 7
  • GCPGD uses a least-squares warm start x0 = G†y with L = 2N measurements, P = M, n = 4 inner Cadzow cycles, relaxation α = 1/2, and a constant step size.Exact recovery is declared when ||x̂ − x★||_Γ ≤ 0.1σ_K; predicted thresholds are evaluated at δ = 0.05.Source: §IV · p. 8

A. Geometry of the Model Set

The experiments show that model-set conditioning deteriorates as Diracs collide, while nontangentiality remains bounded; they also validate the a posteriori drift certificate throughout the tested configurations.

A. Geometry of the Model Set

  • When one Dirac pair merges, σ_K collapses while the angle constant c stays bounded away from one, and exactly 2K principal angles vanish in all 300 instances.The collision sweep tested 12 logarithmically spaced gaps down to 5 × 10^-4, with 25 trials per gap.Source: Figure 1 · p. 8, A. Geometry of the Model Set · p. 8
  • Lemma 4’s bound lower-bounds measured σ_K in every valid instance and tightens as separation grows, up to its Rayleigh-type validity edge.The bound holds in all valid instances tested across 100 random streams per separation.Source: A. Geometry of the Model Set · p. 8, Figure 1 · p. 8
  • The certified factor 1+ε̂ dominates measured drift in 100% of runs, with ε̂ between 0.20 and 0.30 and below one at the theorem’s radius.Every inner iterate remained in G_δ across six tested (K, M) configurations.Source: A. Geometry of the Model Set · p. 8

B. Empirical Convergence of Alternating Projections

Lemma 2 predicts the per-cycle contraction rate of inner alternating projections from a single singular value decomposition. Across tested configurations, measured rates align with that prediction, with a slight downward bias from faster-decaying transients.

B. Empirical Convergence of Alternating Projections

  • Lemma 2 predicts that inner alternating projections contract error toward their limit at per-cycle rate c2, computable beforehand from one singular value decomposition.Source: B. Empirical Convergence of… · p. 8
  • Three-decimal-place steady-state agreement was observed between measured per-cycle rates and Lemma 2’s prediction, with a slight downward bias from faster-decaying transients.Measurements used 20 trials per configuration across K∈{3, 5, 7, 9}, M∈{8, 10, 12, 18}, and five separation distances Δ.Source: Figure 2 · p. 8, B. Empirical Convergence of… · p. 8

C. Convergence of GCPGD

Figure 3 supports Theorem 2’s geometric noiseless convergence and noise-proportional error floor, while Figure 4 tests predicted recovery thresholds under collision-driven collapse of σ_K.

C. Convergence of GCPGD

  • 0.986 measured geometric contraction is below the predicted q̃≈0.996 in the noiseless regime, confirming that the outer rate is governed by μ_T.The reported evaluation uses K=5, M=12, and Δ=0.10 over 20 trials.Source: Figure 3 · p. 8, C. Convergence of GCPGD · p. 8
  • Unit log-log slope confirms a noise-proportional limiting error floor; the empirical prefactor ≈0.21 is below the bound 2/μ_T≈2.36.The global weighted singular value σ_min is numerically zero in this setting, making the tangent-restricted μ_T necessary.Source: Figure 3 · p. 8, C. Convergence of GCPGD · pp. 8–9
  • Theorem 2’s threshold tracks the empirical transition across its 40 dB rise, with the slope attributed to σ_K as μ_T stays essentially constant.A one-constant calibration brings the predicted curve onto the transition with an offset of approximately 5 dB.Source: Figure 4 · p. 9, C. Convergence of GCPGD · p. 9
  • The fully explicit Corollary 2 curve certifies the well-separated region but expires before collapse, limited by the Vandermonde bound of Lemma 4.Figure 4 evaluates the collision ensemble in which one pair of Diracs merges and σ_K collapses.Source: Figure 4 · p. 9, C. Convergence of GCPGD · p. 9

D. Reconstruction Accuracy of GCPGD

GCPGD achieves the lowest reconstruction error in nearly every tested configuration, while the observed oversampling gap and PSNR endpoints reflect the paper’s conditioning and convergence theory.

D. Reconstruction Accuracy of GCPGD

  • The comparison used K=9 Diracs, L=19 noisy samples, and model sizes M∈{K, 2K, 3K}, with five inner Cadzow iterations for CPGD and GCPGD.Figure 5 reports median and interquartile reconstruction error across PSNR levels.Source: D. Reconstruction Accuracy of GCPGD · p. 9
  • GCPGD had the lowest error in nearly every configuration and tighter bands; one least-squares warm start reached the noise floor, while GenFRI stagnated at M=27 after 15 restarts.These findings are reported within Theorem 2’s basin; GenFRI used 15 random initializations to avoid local minima.Source: D. Reconstruction Accuracy of GCPGD · p. 9
  • The GCPGD–CPGD gap widened with oversampling: they nearly coincided at high PSNR for M=2K, but CPGD plateaued above GCPGD throughout the PSNR range at M=3K.The paper attributes this to CPGD’s unweighted gradient paying a conditioning factor cond(P+1), which grows with M, unlike the Γ-preconditioned step.Source: D. Reconstruction Accuracy of GCPGD · p. 9
  • Low-PSNR degradation matched the admissible-noise threshold proportional to σ_K, while high-PSNR saturation reflected stopping and iteration limits rather than a statistical limit; near-Rayleigh, admissible noise vanishes and learning-based methods such as become the method of choice.The low-PSNR behavior agrees with the subspace-swap analysis of; within the basin, the predicted error is linear in ||ε||_2.Source: D. Reconstruction Accuracy of GCPGD · p. 9

V. CONCLUSION

The conclusion reframes GenFRI reconstruction through the Cadzow denoiser’s fixed-point set and replaces unattainable global guarantees with a quantitative local theory. It connects GCPGD’s convergence conditions to observed reconstruction behavior.

V. CONCLUSION

  • Structural obstructions rule out global guarantees, while GCPGD with Γ-metric preconditioning converges linearly from an explicit basin to a noise-proportional error floor.The authors describe this as the first quantitative convergence guarantee in the GenFRI setting.Source: §V · p. 10
  • The Cadzow denoiser is quasi-nonexpansive on an explicit spectral tube whose radius scales with the conditioning σ_K of the Dirac stream.Source: §V · p. 10
  • The denoiser confines iterates to the rank variety, while the data term selects a model point; all hypotheses except one localization radius are computable per instance.The computable quantities are the nontangentiality certificate and the a posteriori drift factor ˆε.Source: §V · p. 10
  • Recovery thresholds predicted from measured σ_K and μ_T match observed rates, error floors, and phase transitions; Corollary 2’s explicit threshold admits the subspace-swap condition of as its average-case counterpart.Source: §V · p. 10
  • Because CPGD is a limiting parameter choice of GCPGD, the theory explains its empirical reliability: one run suffices within the basin, without random restarts.Source: §V · p. 10
  • Future work will explore faster Cadzow implementations and systematic comparisons with learning-based reconstruction,.Source: §V · p. 10

S.I. PROOF OF PROPOSITION 1 (PROJECTION ONTO THE SUBSET OF RANK-K MATRICES) · S.II. PROOF OF LEMMA 1 (ONE-STEP ESTIMATE) · S.III. PROOF OF LEMMA 2 (LOCAL CONVERGENCE OF THE INNER ALTERNATING PROJECTIONS)

These proofs establish when the rank-K projection is unique, derive a one-step estimate from an explicit exterior-sphere inequality, and show local convergence and quasi-optimality of the inner alternating projections. They also explain how the convergence results transfer from Hankel to Toeplitz lifts.

S.I. PROOF OF PROPOSITION 1 (PROJECTION ONTO THE SUBSET OF RANK-K MATRICES)

  • For rank greater than K, truncating the singular value decomposition gives a nearest rank-K matrix, unique when σ_K(X) > σ_K+1(X) [21, 31].For rank at most K, the projection is X itself.Source: S.I. PROOF OF PROPOSITION 1… · p. 11

S.II. PROOF OF LEMMA 1 (ONE-STEP ESTIMATE)

  • The one-step proof establishes uniqueness on G_δ when ρ(X) < 1 and derives an explicit exterior-sphere inequality using nearest-point expansion and tail scaling.The admissible scaling range is governed by σ_K(X)/σ_K+1(X), and the derivation makes the prox-regularity modulus explicit.Source: S.II. PROOF OF LEMMA 1 (ONE-STEP… · p. 11
  • The one-step estimate combines the exterior-sphere inequality at M★ with firm nonexpansiveness of the orthogonal projection onto T_P.The proof sets Y = M★ in the polarization identity and uses M★ ∈ T_P.Source: S.II. PROOF OF LEMMA 1 (ONE-STEP… · p. 11

S.III. PROOF OF LEMMA 2 (LOCAL CONVERGENCE OF THE INNER ALTERNATING PROJECTIONS)

  • Under nontangentiality, the inner alternating projections converge locally at a linear rate, with quasi-optimality of the limit and distance bound dist(M_k, T_P∩H_K) ≤ c̄^k u.The proof takes c̄ in [c^2, 1) and bounds the limit’s distance from the nearest point in E by ε1u.Source: S.III. PROOF OF LEMMA 2 (LOCAL… · p. 11
  • Local convergence also yields a quasi-optimal limit and bounds the change in its nearest-point projection by 2ε1u, after shrinking the admissible neighborhood.The proof applies quasi-optimality to the tail of the same sequence, which has the same limit.Source: S.III. PROOF OF LEMMA 2 (LOCAL… · p. 11
  • Curvature controls the local norm estimate through ε2 = O(κr0 + ε1), and row reversal transfers the Hankel alternating-projection results to Toeplitz lifts while preserving geometry and constants.Choosing ε1 and r0 sufficiently small gives the stated estimate; row reversal preserves ranks, Frobenius geometry, and nontangentiality.Source: S.III. PROOF OF LEMMA 2 (LOCAL… · p. 11

S.IV. PROOF OF THEOREM 1 (LOCAL REGULARITY OF CADZOW DENOISING) · S.V. PROOF OF LEMMA 3 (CONFINEMENT)

The proof shows that sufficiently small perturbations keep Cadzow iterates in the local regularity region. The confinement argument bounds each update by a contraction plus a noise term, then uses the denoiser and a scalar recursion to control the iterates.

S.IV. PROOF OF THEOREM 1 (LOCAL REGULARITY OF CADZOW DENOISING)

S.V. PROOF OF LEMMA 3 (CONFINEMENT)

S.VI. PROOF OF THEOREM 2 (CONVERGENCE OF GCPGD)  … S.IX. PROOF OF COROLLARY 3 (VANILLA FRI DENOISING)

These proof sections establish local convergence and noise control for GCPGD, derive conditioning bounds for the Dirac stream, and specialize explicit conditions to vanilla FRI denoising. They do so by linking local iterate behavior to Vandermonde conditioning and the vanilla model’s weights.

S.VI. PROOF OF THEOREM 2 (CONVERGENCE OF GCPGD) 

  • GCPGD’s iterates remain in the local neighborhood, with the inner Cadzow iterates in Gδ, under the stated conditions.The proof applies Lemma 3’s condition (23) to keep x_k and v_{k+1} in Bδ(x★).Source: S.VI. PROOF OF THEOREM 2 (CONVERGENCE… · p. 12
  • The final reconstruction error is controlled by restricted injectivity: ∥G(x̄−x★)∥₂ ≤ 2∥ε∥₂, yielding the claimed bound.The proof also gives a limsup bound proportional to the noise level.Source: S.VI. PROOF OF THEOREM 2 (CONVERGENCE… · p. 12

S.VII. PROOF OF LEMMA 4 (CONDITIONING OF THE DIRAC STREAM)

  • The Fourier coefficients of the Dirac stream form the entries of T_P(x★), which the proof factors using Vandermonde matrices.The matrices have unit-modulus nodes with identical wrap-around separation Δ and sizes (N−P)×K and (P+1)×K.Source: S.VII. PROOF OF LEMMA 4 (CONDITIONING… · p. 12
  • For an m×K unit-modulus Vandermonde matrix with m > 1 + 1/Δ, σ_K(V)^2 ≥ m−1/Δ−1 supplies the conditioning bound.The proof applies this bound to both Vandermonde factors, together with the minimum Dirac amplitude.Source: S.VII. PROOF OF LEMMA 4 (CONDITIONING… · p. 12

S.VIII. PROOF OF COROLLARY 2 (EXPLICIT CONDITIONS)

  • When r₀ ≥ rδ/2 and ε ≤ 1, the Theorem 1 radius obeys r ≥ rδ/2, enabling the explicit conditions via Corollary 1’s signal-to-noise condition.The proof inserts (32) into that condition.Source: S.VIII. PROOF OF COROLLARY 2 (EXPLICIT… · p. 12

S.IX. PROOF OF COROLLARY 3 (VANILLA FRI DENOISING)

Loading 2609.02921v1…