VarProSD: New theoretical guarantees for spike deconvolution optimization

The paper tackles multi-snapshot spike deconvolution, where the goal is to recover sparse impulse locations from noisy convolutions with a known point spread function (PSF) across multiple measurements. The authors propose VarProSD, a variable-projection formulation that eliminates amplitude variables in closed form, reducing the problem to a nonconvex least-squares optimization over spike locations alone. This clever transformation shrinks the search space but introduces a challenging nonconvex landscape. The key contribution is an explicit characterization of the basin of convexity—a region where the objective becomes locally convex—in terms of PSF properties such as power spectral density and smoothness. This reveals how sampling bandwidth and minimum spike separation directly influence the local geometry, providing actionable insights for practitioners.

Within this convex basin, the authors establish strong theoretical guarantees: the estimator is consistent (converges to true locations) as the number of snapshots grows under stochastic noise, and they provide sharp error bounds for adversarial noise using local Lipschitz properties. Gradient descent initialized inside the basin is proven to converge linearly to the global optimum. A central technical tool is Beurling-Selberg extremal approximations, which yield PSF-agnostic bounds on the conditioning of structured matrices in the optimization landscape. Numerical experiments confirm the theory, showing that a modified ESPRIT initialization followed by gradient-based refinement reliably lands in the convex basin. This work bridges a gap between applied optimization and theoretical signal recovery, offering a principled framework for high-resolution spike deconvolution in applications like microscopy, radar, and neuroscience.