Geometry and Symmetry in Short-and-Sparse Deconvolution

We study the textitShort-and-Sparse (SaS) deconvolution problem of recovering a short signal mathbf a0 and a sparse signal mathbf x0 from their convolution. We propose a method based on nonconvex optimization, which under certain conditions recovers the target short and sparse signals, up to a signed shift symmetry which is intrinsic to this model. This symmetry plays a central role in shaping the optimization landscape for deconvolution. We give a textitregional analysis, which characterizes this landscape geometrically, on a union of subspaces. Our geometric characterization holds when the length-p0 short signal mathbf a0 has shift coherence μ, and mathbf x0 follows a random sparsity model with sparsity rate θ ∈ Bigl[fracc1p0, fracc2p0√μ + √p0Bigr]·frac1log2p0. Based on this geometry, we give a provable method that successfully solves SaS deconvolution with high probability.