Sparse Spikes Deconvolution on Thin Grids

Vincent Duval, Gabriel PeyréarXiv 2015 · arXiv

Abstract

Grid-based sparse recovery methods, such as the Lasso and Continuous Basis Pursuit (C-BP), are standard tools for deconvolving point sources in signal processing. However, these methods exhibit a fundamental instability when applied to increasingly fine grids. This paper characterizes this instability through the lens of "extended support," demonstrating that even under infinitesimal noise, these algorithms consistently split a single true spike into a pair of neighboring spikes. We provide a rigorous mathematical framework to predict this behavior and compare the performance of standard Lasso against C-BP.

Introduction

The recovery of "sparse spikes"—discrete point sources of information—from blurred and noisy observations is a cornerstone of modern sensing. Applications range from identifying stars in astronomical imaging to locating fluorescent molecules in super-resolution microscopy and interpreting seismic reflections in geophysics. Mathematically, this is framed as an inverse problem seeking to reconstruct a set of Dirac masses.

Because the underlying space of potential locations is continuous and thus infinite-dimensional, practitioners typically discretize the domain using a grid. They then apply sparse regularization, most commonly the Lasso (or Basis Pursuit). While it is intuitive to assume that a finer grid leads to higher precision, this research reveals a counter-intuitive "discretization error" that persists even as the grid spacing approaches zero.

The "Double Spike" Phenomenon

The central finding of this work is that for a sufficiently thin grid, the support of the Lasso solution is almost never the true support. Instead of identifying the single correct grid point, the algorithm "splits" the signal. For every real spike in the ground truth, the reconstruction typically produces two spikes at the nearest grid neighbors.

This instability is not merely a numerical artifact but a structural property of the optimization problem. The authors introduce the concept of Extended Support to analyze this. In classical recovery theory, stability is often tied to "Fuchs' condition." However, on thin grids, this condition is systematically violated. The extended support is defined as the set of indices where the minimal-norm dual certificate—a mathematical tool used to certify the optimality of a sparse solution—reaches its maximum. This framework allows for the precise prediction of which grid points will be activated in the presence of noise.

Algorithmic Consequences: Lasso vs. C-BP

The paper evaluates two primary algorithmic approaches:

  1. The Lasso: Standard $\ell_1$-regularized least squares on a fixed grid. The analysis shows that the error in estimated location and amplitude is proportional to the noise level and the regularization parameter, scaled by the grid size $h$ (specifically $O(w/h, \lambda/h)$).
  2. Continuous Basis Pursuit (C-BP): A more sophisticated approach that utilizes a first-order Taylor expansion of the blur kernel at each grid point. This allows spikes to "lean" toward off-grid locations.

While C-BP is designed to mitigate off-grid errors, it still falls into the "double-spike" trap. However, its sensitivity is different: while Lasso's stability is governed by the grid size $h$, C-BP's stability regime is much more refined, depending on $h^3$. In the low-noise regime, C-BP also recovers pairs of spikes, but they follow a specific "shifted" pattern where one spike is off-grid and the other is pinned to a half-grid point.

The Natural Shift

A key theoretical contribution is the derivation of the natural shift ($\rho$). This value is intrinsic to the signal and the kernel. It determines the direction and magnitude of the splitting, predicting which side of the true location the "extra" spikes will appear on. This shift explains why the reconstructed support "drifts" even when the true spike is perfectly aligned with a grid point.

Numerical Evidence and Phase Transitions

The theory is validated through synthetic deconvolution simulations using ideal low-pass filters (Sinc-like kernels) on a 1D torus. Furthermore, the authors apply the extended support theory to compressed sensing scenarios using Gaussian random matrices. By doing so, they numerically characterize the phase transition between stable recovery and the "unstable" splitting regime, providing a more granular view of the algorithm's behavior when the number of measurements is near the theoretical limit.

Conclusion and Future Directions

This research highlights a critical limitation in how we discretize continuous sparse recovery problems. The "double spike" trap suggests that simply increasing grid resolution does not lead to a cleaner reconstruction; rather, it changes the nature of the error.

Current limitations include the focus on 1D signals and positive measures. Extending the C-BP analysis to signed or complex-valued measures presents significant challenges due to the resulting non-convexity of the optimization. Future work will explore higher-dimensional splitting patterns in 2D and 3D imaging and investigate alternative interpolation schemes, such as "polar" interpolation, which may offer a path toward more stable off-grid recovery.

Summary updated

Abstract

This article analyzes the recovery performance of two popular finite dimensional approximations of the sparse spikes deconvolution problem over Radon measures. We examine in a unified framework both the L1 regularization (often referred to as Lasso or Basis-Pursuit) and the Continuous Basis-Pursuit (C-BP) methods. The Lasso is the de-facto standard for the sparse regularization of inverse problems in imaging. It performs a nearest neighbor interpolation of the spikes locations on the sampling grid. The C-BP method, introduced by Ekanadham, Tranchina and Simoncelli, uses a linear interpolation of the locations to perform a better approximation of the infinite-dimensional optimization problem, for positive measures. We show that, in the small noise regime, both methods estimate twice the number of spikes as the number of original spikes. Indeed, we show that they both detect two neighboring spikes around the locations of an original spikes. These results for deconvolution problems are based on an abstract analysis of the so-called extended support of the solutions of L1-type problems (including as special cases the Lasso and C-BP for deconvolution), which are of an independent interest. They precisely characterize the support of the solutions when the noise is small and the regularization parameter is selected accordingly. We illustrate these findings to analyze for the first time the support instability of compressed sensing recovery when the number of measurements is below the critical limit (well documented in the literature) where the support is provably stable.
BibTeX
@misc{duval2015sparse,
  author = {Vincent Duval and Gabriel Peyré},
  title = {{Sparse Spikes Deconvolution on Thin Grids}},
  year = {2015},
  eprint = {1503.08577},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1503.08577},
}
Figure