Exact Support Recovery for Sparse Spikes Deconvolution

Vincent Duval, Gabriel PeyréFound. Comput. Math 2015 · DOI

Abstract

This paper establishes a rigorous theoretical framework for the "super-resolution" problem, specifically the recovery of sparse spikes from blurred and noisy measurements in a continuous-space setting. By introducing the Non-Degenerate Source Condition (NDSC), the authors demonstrate that Total Variation (TV) regularization—specifically the Beurling LASSO—is robust to noise. The findings provide a mathematical guarantee that recovered spikes converge precisely to the ground truth in both location and amplitude as noise vanishes, bridging the gap between continuous theory and discrete implementation.

Introduction

In imaging and signal processing, the objective is often to recover fine-scale details—such as stars in astronomical data or molecules in fluorescence microscopy—from data that has been blurred by a point spread function and corrupted by noise. This task, known as sparse spikes deconvolution, was traditionally solved using fixed pixel grids. However, grid-based models suffer from "basis mismatch" when a spike falls between pixels.

To address this, recent research has shifted toward a grid-free setting, treating signals as collections of Dirac masses in continuous space. While mathematically elegant, this shift raised critical questions regarding stability: does noise cause the algorithm to produce "parasitic" artifacts, or can it reliably identify the correct number of spikes? This paper provides the stability analysis necessary to answer these questions.

Methods and Theoretical Framework

The Beurling LASSO

The authors analyze the Beurling LASSO, the continuous-space analog of the $\ell_1$ (Lasso) regularization used for vectors. This method seeks to minimize the Total Variation norm of a measure, which promotes sparsity in the continuous domain.

Dual Certificates and the NDSC

The core of the stability proof involves "Dual Certificates"—mathematical functions that prove a specific set of spikes is the optimal solution. The authors focus on the minimal $L^2$-norm certificate and introduce two key concepts to ensure its reliability:

  1. Non-Degenerate Source Condition (NDSC): A geometric requirement on the dual certificate that ensures the optimization problem is not "on the edge" of failure. It guarantees that the solution is unique and stable under perturbation.
  2. Vanishing Derivative Pre-certificate: Since the NDSC can be difficult to check directly, the authors propose a "proxy" function. This pre-certificate is computed by solving a simple linear system. If this proxy stays within a value of 1 and maintains non-zero second derivatives at spike locations, the NDSC is satisfied.

Key Insights

The Stability Bridge

The paper explains why discrete solvers often exhibit "flickering" spikes between adjacent pixels. It proves that as a grid becomes finer, the discrete solution's support concentrates on the two grid points surrounding the true continuous location. This provides a theoretical link between the discrete and continuous worlds.

Linear Error Scaling

Under the NDSC, the authors demonstrate that errors in both the locations and the amplitudes of the recovered spikes decay linearly with the noise level ($O(\|w\|_2)$). This provides a clear quality guarantee for practitioners: the precision of the recovery is directly proportional to the signal-to-noise ratio.

Results

Theorem 2: Noise Robustness

The primary result of the paper is Theorem 2, which proves that if the signal-to-noise ratio is sufficiently high and the NDSC is satisfied, the recovered measure will have exactly the same number of spikes as the original signal. This "exact support recovery" is the gold standard for super-resolution.

Convergence and Grid Behavior

The authors provide a precise description of how the solution of a discretized problem (like the standard Lasso) converges to the grid-free solution as the grid size tends to zero. This validates the use of continuous-space theory to predict the behavior of practical, grid-based algorithms.

Discussion and Limitations

While the paper provides a robust foundation for super-resolution, it focuses on the "high SNR regime." The proofs rely on noise being small enough that it does not overwhelm the separation between spikes; the specific threshold for this noise depends on the proximity of the spikes to one another.

Furthermore, while the theory extends to higher dimensions (2D and 3D), the numerical illustrations provided focus on the 1D case with an ideal low-pass filter (the Dirichlet kernel). Future research may explore more complex, non-stationary blur kernels and the computational challenges of solving grid-free optimization in large-scale 3D applications.

Summary updated

BibTeX
@article{duval2015exact,
  author = {Vincent Duval and Gabriel Peyré},
  title = {{Exact Support Recovery for Sparse Spikes Deconvolution}},
  journal = {Found. Comput. Math.},
  year = {2015},
  doi = {10.1007/s10208-014-9228-6},
}
Figure