Source-linked AI summary
Exact Support Recovery for Sparse Spikes Deconvolution
Vincent Duval, Gabriel Peyré
TL;DR
The paper asks how precisely total-variation regularization recovers sparse spike supports from noisy, blurred measurements, especially in continuous and discretized domains. It analyzes minimal-norm dual certificates and proves exact spike-count recovery with convergent locations and amplitudes under a non-degeneracy condition, while characterizing the fine-grid discrete solution.
Problem
The paper studies precise support recovery for sparse spikes deconvolution, including the structure of recovered measures and the relation between continuous and discretized solutions.
Method
The paper analyzes total-variation regularization through a minimal-norm dual certificate and computes that certificate by solving a linear system.
Results
Under the Non Degenerate Source Condition and sufficiently favorable signal-to-noise parameters, recovery has the same number of spikes, with locations and amplitudes converging to the input; fine-grid solutions use adjacent spike pairs.
Takeaways & Limitations
The results give a precise support-level description of continuous recovery and of discretized solutions converging toward the grid-free solution as grid spacing vanishes.
Takeaways & Limitations
The continuous and discrete support results rely on the Non Degenerate Source Condition, and the discrete framework generally cannot stably recover the exact support on a fine grid.
Abstract
from arXiv · showhide
This paper studies sparse spikes deconvolution over the space of measures. We focus our attention to the recovery properties of the support of the measure, i.e. the location of the Dirac masses. For non-degenerate sums of Diracs, we show that, when the signal-to-noise ratio is large enough, total variation regularization (which is the natural extension of the L1 norm of vectors to the setting of measures) recovers the exact same number of Diracs. We also show that both the locations and the heights of these Diracs converge toward those of the input measure when the noise drops to zero. The exact speed of convergence is governed by a specific dual certificate, which can be computed by solving a linear system. We draw connections between the support of the recovered measure on a continuous domain and on a discretized grid. We show that when the signal-to-noise level is large enough, the solution of the discretized problem is supported on pairs of Diracs which are neighbors of the Diracs of the input measure. This gives a precise description of the convergence of the solution of the discretized problem toward the solution of the continuous grid-free problem, as the grid size tends to zero.
1 Introduction
The paper studies sparse spikes deconvolution as a continuous, measure-valued super-resolution problem, focusing on precise support recovery under noise. It develops certificate-based results for continuous and discretized total-variation regularization.
- Problem setting: Sparse spikes deconvolution recovers one-dimensional spike positions and amplitudes from blurry, noisy measurements produced by convolution with a known kernel.The formulation uses a sparsity-enforcing ℓ1-type prior, extended to measures through total variation.
- Problem setting: Continuous-domain analysis enables signal-dependent criteria for stable spike recovery that are difficult to obtain on fixed discrete grids.The paper treats the measure-valued problem as a grid-free counterpart to discrete sparse regularization.
- Research gap: The paper addresses the unresolved structure of recovered measures, including spike count, precise locations, and behavior when spikes are constrained to a finite grid.Earlier stability analyses primarily controlled reconstruction or clustering errors without fully describing recovered supports.
- Contributions: A minimal L2-norm dual certificate governs regularization behavior when λ and ||w||2/λ are small.Its saturation regions are approximately stable, keeping recovered support close to the identifiable input support.
- Contributions: Under the Non Degenerate Source Condition, the recovered measure has the same number of spikes, with locations and amplitudes converging to the originals.The condition requires the minimal-norm certificate’s second derivative not to vanish at saturation points.
- Contributions: The minimal-norm certificate is computable by solving a linear system, yielding errors in locations and amplitudes that decay linearly with noise.On a sufficiently fine discrete grid, each input spike produces at most one adjacent pair surrounding it, describing convergence toward the continuous solution.
2 Preliminaries
The preliminaries formulate measure-valued deconvolution, its primal and dual problems, and the dual certificates used for optimality and convergence analysis. They establish existence, certificate structure, and several separation and convergence facts.
- Measure framework: Radon measures on the torus are treated as the dual of continuous functions, with total variation as the dual norm and weak-* topology as the main setting.The weak-* framework restores the dual pairing with C(T) and provides useful compactness properties.
- Measure framework: The convolution operator Φ maps measures to L2(T), while its adjoint Φ∗ maps L2(T) to continuous functions.These operators connect the primal measure reconstruction problem to its dual formulation.
- Duality and certificates: Dual certificates are continuous functions satisfying the total-variation subgradient conditions at the recovered support and provide a direct optimality test.For discrete measures, certificate values equal the signs of the nonzero masses while their uniform norm is at most one.
- Duality and certificates: The penalized dual problem has a unique solution, whereas existence of a solution to the noiseless dual problem is not always guaranteed.When the noiseless dual solution exists, the penalized dual solution converges to the minimal-norm noiseless solution as λ approaches zero.
- Duality and certificates: The minimal-norm certificate η0 = Φ∗p0 selects the least-norm solution of the noiseless dual problem and is the limit of the penalized certificates uniformly.The underlying dual variables converge strongly in L2(T).
- Dirichlet-kernel consequences: For the Dirichlet-kernel setting, a discrete measure at separation 1/(2fc) can fail to solve the noiseless problem, while opposite-signed recovered spikes must be at least 1/(2fc) apart.A noiseless dual solution exists for every input measure in the stated framework, so the minimal-norm certificate is well defined.
3 Noise Robustness
At sufficiently small regularization and noise, dual-certificate saturation controls the support of recovered measures. Under non-degeneracy and full-rank assumptions, recovery has exactly the original number of spikes, with matching signs and perturbations that vanish linearly with noise.
- Extended signed support: The extended signed support is defined by locations where the minimal-norm certificate equals the corresponding sign.It depends on the measurements through y0 = Φm0, rather than solely on the representing measure.
- Extended signed support: If ΦExt m0 has full rank, the noiseless problem has a unique solution; m0 is optimal exactly when its signed support lies in the extended signed support.
- Local structure: When the extended support consists of isolated points, all recovered mass concentrates in shrinking neighborhoods around them, preserving the sign of the minimal-norm certificate.Weak-* convergence supplies the limiting mass behavior as λ and ||w|| tend to zero.
- Local structure: For isolated certificate saturation points with nonzero second derivative, each neighborhood contains at most one recovered spike, with the certificate-prescribed sign.If m0 is identifiable and has mass in the neighborhood, the neighborhood contains exactly one spike.
- Global noise robustness: Under the Non Degenerate Source Condition and full-rank Γx0, the noisy solution is unique and contains exactly N spikes for sufficiently favorable λ and noise.Each recovered amplitude is nonzero and has the same sign as its corresponding input amplitude.
- Global noise robustness: The recovered locations and amplitudes satisfy |˜xλ,i − x0,i| = O(||w||2) and |˜aλ,i − a0,i| = O(||w||2).
- Extensions: The framework extends to higher dimensions by requiring an invertible certificate Hessian and also applies to non-stationary filtering operators.
4 Vanishing Derivatives Pre-certificate
The vanishing derivative pre-certificate provides a practical route to characterize and compute the minimal-norm certificate, while numerical comparisons examine its behavior against the Fejer pre-certificate and minimal-norm certificate. Its validity and equivalence to the minimal-norm certificate depend on source, rank, and non-degeneracy conditions.
- 4.1 Dual Pre-certificates: The minimal-norm certificate is characterized by prescribed values and vanishing derivatives on the support, so it can be computed by solving a linear system.This avoids directly handling the constraint ||η0||∞⩽1.
- 4.1 Dual Pre-certificates: The vanishing derivative pre-certificate ηV is defined as Φ∗pV and is generally not a certificate because it may violate ||ηV||∞⩽1.When the source condition holds and the norm constraint is satisfied, ηV equals the minimal-norm certificate η0.
- 4.1 Dual Pre-certificates: If Γx0 has full rank, checking the Non Degenerate Source Condition on ηV is equivalent to checking it on η0.Under these conditions, the vanishing derivative and minimal-norm certificates coincide.
- 4.2 Necessity of the Norm Constraint: The norm constraint on ηV is necessary for noiseless exact support recovery along a smooth solution path over an interval [0, λ0).The argument assumes full rank and a C1 path of solutions with the same number of spikes.
- 4.3 Application to the Ideal Low-pass Filter: For three equally spaced masses, ηCF is certified numerically for ∆(m0) ⩾ 1.87/fc, while below 1/fc ηV can remain a certificate after ηCF fails.The experiments report that ηV generally performs at least as well as ηCF, except for many peaks with ∆(m0) ⩽ 1.5/fc.
- 4.3 Application to the Ideal Low-pass Filter: An identifiable measure can lack stable support recovery when ηV is not a certificate, even though the minimal-norm certificate η0 remains valid for the noiseless problem.This occurs in the described case where ||ηV||∞>1 and Supp± m0 ⊊ Ext±(m0).
5 Discrete Sparse Spikes Deconvolution
The discrete formulation applies ℓ1 regularization on a finite grid and characterizes recovery through discrete certificates. Under source and rank conditions, it provides noise-robust recovery and describes how thin-grid solutions relate to neighboring grid points.
- 5.1 Finite Dimensional ℓ1 Regularization: Finite-grid sparse deconvolution is formulated as basis pursuit denoising, equivalently an ℓ1-regularized problem over grid coefficients.The operator need not arise from convolution in the finite-dimensional analysis.
- 5.2 Certificates over a Discrete Grid: The discrete minimal norm certificate is obtained from a finite-dimensional dual problem and determines the extended support relative to the grid.The extended support is defined through points where the certificate reaches unit magnitude.
- 5.3 Noise Robustness: Choosing λ proportional to the noise norm yields a unique discrete solution with reconstruction error O(||w||) under full-rank and identifiability assumptions.The stated choice is λ = ||w||2/α.
- 5.2 Certificates over a Discrete Grid: If the signed certificate is strictly below one off the true support and the restricted operator has full rank, small-noise solutions are unique and recover the exact signed support.This is the discrete exact-support condition stated in Corollary 3.
- 5.4 Structure of the Extended Support for Thin Grids: For thin grids satisfying the Non Degenerate Source Condition, each input spike contributes its grid location and possibly one same-sign immediate neighbor to the extended signed support.Thus discrete support may vary even while reconstructed spikes remain close to the original measure.
- 5.4 Structure of the Extended Support for Thin Grids: Unlike continuous recovery, discretized spikes cannot move, so small noise can create spikes only at immediate neighbors of the original locations.For non-dyadic measures, numerical evidence suggests that a pair of neighboring spikes may surround each original spike.
Conclusion
The paper establishes exact support stability for total variation regularization under a non-degenerate certificate and small-noise conditions, and characterizes the discrete-grid analogue. The framework also extends to non-stationary filtering operators and arbitrary dimensions.
- Conclusion: Under non-degeneracy, total variation regularization recovers the same number of spikes and their locations converge to the originals when λ and ||w||/λ are small enough.The convergence rate is governed by a minimal norm certificate, checked through a closed-form vanishing derivative pre-certificate.
- Conclusion: The continuous result gives exact support stability, unlike prior results based on local averages of the recovered measure.The authors describe the two settings as complementary rather than directly comparable because they use different certificates and noise regimes.
- Conclusion: In the discrete ℓ1 setting, each original spike yields at most one pair of consecutive reconstructed spikes surrounding it at small noise.This behavior describes the stable-grid reconstruction when exact support recovery is generally unavailable for sufficiently small grids.
- Conclusion: The proposed method extends to non-stationary filtering operators and arbitrary dimensions.The higher-dimensional extension replaces the domain T by T^d for d ⩾1.
A Auxiliary results
These auxiliary results establish foundational properties of total variation regularization and the associated primal-dual problems. They characterize the total-variation subdifferential and justify existence and strong duality.
- Auxiliary results: The subdifferential characterization follows by identifying A with the closed L∞(T) unit ball.The inclusion A ⊂ B∞(0,1) is obtained by testing against Dirac masses ±δ_t.
- Auxiliary results: The total-variation functional J(m) is convex, proper, weak-* lower semicontinuous, and positively homogeneous.Its dual characterization uses the L∞ unit ball through the set A of continuous functions bounded by one in dual pairing.
- Auxiliary results: The primal problem (P0(y0)) has a solution, and strong duality holds with (D0(y0)).Conversely, the stated optimality relation makes m⋆ and p⋆ solutions of the primal and dual problems.
- Auxiliary results: Strong duality is proved by applying a convex-duality theorem to the dual formulation using proper lower-semicontinuous functions and continuity at the origin.The proof sets V = L2(T), Y = C(T), Y* = M(T), and Λ = Φ*.
B Proof of Proposition 6
The proof establishes invertibility of a matrix built from evaluations and derivatives by converting a null-vector relation into a rational function with too many roots. This proves the required linear independence.
- Proof of Proposition 6: When N < f_c, the points r_1,…,r_N are completed with distinct points on S^1 to form a square matrix.The enlarged system allows the same invertibility argument to apply.
- Proof of Proposition 6: To prove matrix invertibility, the argument assumes a coefficient vector α satisfies M^T α = 0 and constructs a rational function F.The matrix columns encode evaluation and derivative constraints at points on the unit circle.
- Proof of Proposition 6: The null-vector relation forces F(r_j) = 0 and F′(r_j) = 0 for every interpolation point r_j.Each point therefore contributes a root with multiplicity at least two.
- Proof of Proposition 6: The resulting 2f_c + 1 roots on S^1 force F = 0, hence α = 0 and M is invertible.This contradiction proves that the relevant columns are linearly independent.
C Proof of Proposition 9
The proof analyzes projections onto an increasing sequence of finite-dimensional spaces and shows convergence of the associated projected dual variables. The remaining conclusion follows from the earlier projection proposition.
- Proof of Proposition 9: The spaces C_n increase toward C, enabling approximation through projections onto finite-dimensional subspaces.The proof uses the projection of x ∈ L2(T) onto C_n and the characterization of projections onto convex sets.
- Proof of Proposition 9: The sequence p_λ^n converges weakly to p_λ.The argument first establishes convergence along subsequences and then concludes convergence of the whole sequence.
- Proof of Proposition 9: Lower semicontinuity and the inclusion C ⊂ C_n provide the comparison needed for the convergence argument.The rest of the proposition follows from Proposition 1.