Characterization of the basin of convexity for multi-snapshot spike deconvolution via variable projection

Meghna Kalra, Maxime Ferreira Da Costa, Kiryung Lee

We study the problem of multi-snapshot spike deconvolution, where the goal is to recover the locations of sparse impulses from their noisy convolution with a known point spread function (PSF) across multiple snapshots. We adopt a variable-projection formulation that eliminates the amplitudes in closed form, reducing the task to a nonconvex least-squares problem over the spike locations alone, which we refer to as the variable-projection formulation of spike deconvolution (VarProSD). We provide an explicit characterization of the basin of convexity of the VarProSD objective in terms of key PSF properties, including its power spectral density and smoothness, revealing how sampling bandwidth and spike separation influence the local geometry. Within this basin, we establish that the estimator is consistent in the number of snapshots under stochastic noise, and provide a complementary, sharper error bound under adversarial noise via the local Lipschitz property of the inverse map. We further show local convergence guarantees for gradient descent when initialized within the basin. A central ingredient throughout is the use of Beurling--Selberg extremal approximations, which enable sharp, PSF-agnostic bounds on the conditioning of the structured matrices arising in the optimization landscape. Numerical experiments validate our theoretical findings and demonstrate the effectiveness of modified ESPRIT initialization followed by gradient-based refinement.