Timezone: »

Geometry and Symmetry in Short-and-Sparse Deconvolution
Han-Wen Kuo · Yenson Lau · Yuqian Zhang · John Wright

Thu Jun 13 05:15 PM -- 05:20 PM (PDT) @ Room 104

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.

Author Information

Henry Kuo (Columbia University)
Yenson Lau (Columbia University)
Yuqian Zhang (Columbia University)
John Wright (Columbia University, USA)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors