Skip to yearly menu bar Skip to main content


Geometry and Symmetry in Short-and-Sparse Deconvolution

Han-Wen Kuo · Yenson Lau · Yuqian Zhang · John Wright

Pacific Ballroom #120

Keywords: [ Unsupervised Learning ] [ Sparsity and Compressed Sensing ] [ Non-convex Optimization ] [ Neuroscience and Cognitive Science ] [ Computer Vision ]


We study the Short-and-Sparse (SaS) deconvolution problem of recovering a short signal a0 and a sparse signal 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 regional analysis, which characterizes this landscape geometrically, on a union of subspaces. Our geometric characterization holds when the length-p0 short signal a0 has shift coherence µ, and x0 follows a random sparsity model with sparsity rate θ ∈ [c1/p0, c2/(p0\sqrt{\mu}+\sqrt{p0})] / (log^2(p0)) . Based on this geometry, we give a provable method that successfully solves SaS deconvolution with high probability.

Live content is unavailable. Log in and register to view live content