Source-linked AI summary
Spike detection from inaccurate samplings
Jean-Marc Azais, Yohann De Castro, Fabrice Gamboa
TL;DR
The paper addresses support detection for discrete measures from few noisy observations, where measure-space ℓ1 regularization must localize recovered spikes despite limited-resolution measurements. It analyzes BLASSO and derives quantitative guarantees: large recovered spikes are close to target spikes, while off-support recovered mass is small, with explicit Fourier-case separation conditions.
Problem
The paper asks how accurately unconstrained measure-space ℓ1 minimization recovers spike locations and how localization depends on noise and spike amplitudes.
Method
The paper analyzes BLASSO, a total-variation-regularized reconstruction of a discrete measure from noisy observations such as Fourier or moment samples.
Results
Large recovered spikes are close to target spikes and recovered mass far from the original support is small; in the Fourier case, spikes separated by at least 2.5/f_c permit detection with known precision via convex optimization.
Takeaways & Limitations
The results provide explicit quantitative localization guarantees for support detection from noisy Fourier and moment observations using a tractable procedure.
Takeaways & Limitations
The Fourier separation constant 2.5 is not optimal: it can be lowered to 2, but the resulting constants become larger, including 218 exceeding 103 in (3.2).
Abstract
from arXiv · showhide
This article investigates the support detection problem using the LASSO estimator in the space of measures. More precisely, we study the recovery of a discrete measure (spike train) from few noisy observations (Fourier samples, moments...) using an $\ell_{1}$-regularization procedure. In particular, we provide an explicit quantitative localization of the spikes.
1. INTRODUCTION
The paper studies quantitative support localization for discrete measures recovered from noisy, limited observations using measure-space ℓ1 regularization. It develops tractable BLASSO-based guarantees showing how recovered spikes relate to target spikes, with Fourier and moment sampling as key examples.
- 1.1. Super-resolution.: Quantitative localization is needed because limited-resolution imaging can obscure fine details, although discrete sources may remain recoverable beyond the physical resolution limit.The motivation includes source separation and applications in astronomy, medical imaging, and 3D microscopy.
- 1.1. Super-resolution.: The paper proves quantitative detection guarantees from noisy Fourier and moment observations and makes the estimates computable with the tractable BLASSO algorithm.The approach extends measure-space LASSO regularization and can use semidefinite programming in Fourier or moment settings.
- 1.2. Previous works.: The work extends prior measure-space regularization analyses by providing quantitative localization of recovered spikes for an unconstrained ℓ1-minimization problem under a general sampling scheme.Earlier work addressed related recovery, stability, and prediction questions, but the paper identifies localization under this general unconstrained setting as new.
- 1.4. Unconstrained minimization.: The central problem is to determine how close the recovered spike train is to the target and how localization accuracy depends on noise and recovered or original spike amplitudes.The paper presents these as open questions for unconstrained measure-space ℓ1 minimization and claims quantitative guarantees from output amplitudes.
- 1.5. Contribution.: The main contribution is that large recovered spikes lie close to target spikes, while the total mass of recovered spikes far from the original support is small.For Fourier and moment measurements, mild support assumptions yield concentration around recovered spikes above the noise level and error bounds involving recovered and original measures.
2. QUANTITATIVE LOCALIZATION IN THE GENERAL FRAME
The paper strengthens dual-certificate analysis to obtain quantitative localization guarantees for BLASSO under noisy observations. It establishes support-detection results under quadratic isolation and Bernstein-type conditions, and shows applicability to several measurement families.
- 2.1. Zero-noise problem.: A dual certificate requires phase interpolation at support points and an ℓ∞ norm at most one, and its existence characterizes exact ℓ1 recovery in the zero-noise problem.Without such a certificate, the paper states that ℓ1-minimization cannot recover the target measure.
- 2.2. Quantitative localization guarantees from the output amplitudes.: BLASSO quantitatively localizes recovered spikes from noisy observations, with large recovered weights near true support points and small weights far away.The localization error is bounded in terms of recovered amplitudes, yielding confidence sets that improve as recovered amplitude increases.
- 2.3. Quantitative localization guarantees from the input amplitudes.: Theorem 2.2 converts localization bounds into input-amplitude terms by combining quadratic isolation with the Bernstein Isolation Property.The BIP controls the second derivative of dual certificates near each support point and supports extension beyond Fourier measurements.
- 2.4. Examples of families satisfying BIP.: The Bernstein Isolation Property holds for broad measurement families, including Fourier, moment, Laplace-transform, and Müntz-polynomial systems.The paper characterizes BIP through Bernstein-type derivative inequalities and describes it as mild in practical cases.
3. SUPPORT DETECTION FROM NOISY FOURIER/MOMENT SAMPLES
The section applies BLASSO to noisy Fourier and moment samples, showing that sufficiently separated spikes can be quantitatively localized without knowing their total number. The localization error is expressed through recovered or original amplitudes under stated sampling and separation conditions.
- 3.1. Detection from noisy Fourier samples.: Sufficiently separated spikes can be detected with known precision by solving BLASSO on noisy Fourier samples.The Fourier setting requires separation of at least 2.5/f_c apart.
- 3.1. Detection from noisy Fourier samples.: BLASSO quantitatively estimates spike locations in terms of recovered or input amplitudes.Large recovered weights lie close to true support points, while small mass remains far from the original support.
- 3.1. Detection from noisy Fourier samples.: The procedure does not require prior knowledge of the total spike count; only the minimum pairwise atom distance matters.This property is stated for BLASSO under the section’s support conditions.
- 3.1. Detection from noisy Fourier samples.: The minimum-separation constant 2.5 is acknowledged as non-optimal because lowering it would make the corollary constants larger.The paper retains 2.5 to avoid excessively large constants.
- 3.2. Detection from noisy moment samples.: For noisy moment measurements, BLASSO likewise studies super-resolution under endpoint separation and QIC conditions.The moment setting uses Chebyshev polynomials and assumes the support is separated from the interval endpoints.
4. RICE METHOD
The Rice method controls the supremum of a Gaussian process associated with the sampling family. The construction specializes this process to Chebyshev-based moment measurements and tracks its covariance and variance.
- 4. RICE METHOD: The Rice method is used to upper-bound the supremum of a random polynomial on a compact set.This provides the probabilistic control needed in the moment-sampling analysis.
- 4. RICE METHOD: The analysis defines a Gaussian process as a linear combination of the sampling functions with independent standard-normal coefficients.For the Chebyshev family, the process is indexed by t in [-1,1].
- 4. RICE METHOD: The process covariance is determined by pairwise products of the sampling functions, while its maximal variance is attained at 1.The variance expression depends on the sampling order m.
- 4. RICE METHOD: The Fourier analogue uses trigonometric functions exp(i2πkx) over frequencies from -f_c to f_c with independent standard-normal errors.These functions define the Fourier sampling frame used in the noisy-sample setting.
APPENDIX A. PROOF OF THEOREM 2.1
The proof of Theorem 2.1 combines a dual certificate with BLASSO optimality and norm inequalities. This yields the theorem’s two support-localization conclusions.
- APPENDIX A. PROOF OF THEOREM 2.1: A dual certificate satisfying the QIC condition supplies the polynomial used in the proof.The certificate is tied to the phases of the measure’s weights.
- APPENDIX A. PROOF OF THEOREM 2.1: The proof interprets the key quantity as a nonnegative Bregman divergence of the TV norm between the recovered and target measures.Nonnegativity follows because the certificate is a sub-gradient of the TV norm at the target measure.
- APPENDIX A. PROOF OF THEOREM 2.1: The triangle inequality and Parseval’s identity convert the BLASSO relations into the inequalities establishing results (1) and (2).The localization estimate follows from the resulting inequality.
APPENDIX B. PROOF OF THEOREM 2.2
The proof of Theorem 2.2 starts from BLASSO optimality conditions and constructs interpolating generalized polynomials using BIP and QIC. These ingredients yield the theorem’s support-detection conclusions.
- APPENDIX B. PROOF OF THEOREM 2.2: BLASSO solutions satisfy dual feasibility and a residual–solution identity used throughout the proof.The conditions bound the dual pairing by λ and equate a residual pairing with λ times the recovered TV norm.
- APPENDIX B. PROOF OF THEOREM 2.2: The BIP and QIC properties produce generalized polynomials that interpolate support indicators and remain controlled away from their designated spikes.Each Q_j equals one at its designated support point, vanishes at the others, and obeys local bounds.
- APPENDIX B. PROOF OF THEOREM 2.2: Applying the interpolating polynomials to the proof inequalities yields the intermediate estimates needed for support detection.The final part of the theorem follows by combining these estimates with Theorem 2.1’s results (1) and (2).
APPENDIX C. PROOFS OF THE AUXILIARY LEMMAS
The appendix characterizes minimizers of the total-variation regularized objective through a subgradient optimality condition.
- The estimator ˆ∆ minimizes the objective only if the subgradient condition 0 ∈ ∂f(ˆ∆) holds.
- The condition is expressed as an inequality that must hold for every measure ν.
C.1. Proof of Lemma B.1.
The proof establishes equivalent optimality conditions for ˆ∆ by combining the subgradient characterization with a constraint on the dual polynomial.
- Condition (C.1) is necessary and sufficient for ˆ∆ to minimize f(ν).
- The resulting expression is finite when ∥⟨z, Φ⟩∥∞ ≤ 1 and infinite otherwise.
- Thus, ˆ∆ is a minimizer if and only if conditions (1) and (2) hold.
- The proof introduces coefficients of a polynomial P as part of the auxiliary optimality argument.
C.2. Proof of Lemma B.2.
The proof controls approximation terms using Parseval’s identity, Hölder’s inequality, interpolation polynomials, and explicit local Taylor bounds.
- Parseval’s identity and Hölder’s inequality are used to bound the relevant error expression through a trigonometric polynomial E.
- The two terms in the bound are controlled separately by λ and λ0.
- QIC constructs polynomials P and ˜P with prescribed values on support points and bounded magnitude on the complement.
- Averaging P and ˜P yields Q1, which isolates T1, remains strictly below one away from T1, and is bounded on the complement.
- The proof concludes by using vanishing derivatives, Taylor’s theorem with explicit remainder, and BIP.
APPENDIX D. PROOF OF COROLLARY 1
The corollary proof invokes a dual-polynomial construction under a support-separation condition, then applies QIC and BIP to obtain the stated result.
- The proof begins from a key auxiliary result for constructing a polynomial over the target support.
- If the support separation satisfies ℓ(S) ≥ 2.5/fc, there exists P in Span(F) with prescribed values at every support point.
- The construction also provides Taylor-expansion and complement bounds for the polynomial.
- The support satisfies QIC(0.0838, 0.0092) and BIP(1, π2), enabling application of Theorems 2.1 and 2.2.
APPENDIX E. PROOF OF COROLLARY 2
The appendix proves Corollary 2 by combining earlier theorems with probabilistic bounds derived through Gaussian-process covariance relations and the Rice method.
- Theorem 2.1 and Theorem 2.2 together yield the stated result with the probability specified in Corollary 2.
- The auxiliary processes are analyzed through stationary Gaussian structure, shared autocovariance, regression formulas, and Dirichlet-kernel identities.
- The proof bounds Gaussian-process level crossings using the Rice method and tail estimates for the standard normal distribution.