Short-and-Sparse Deconvolution -- A Geometric Approach
  Short-and-sparse deconvolution (SaSD) is the problem of extracting localized,
recurring motifs in signals with spatial or temporal structure. Variants of
this problem arise in applications such as image deblurring, microscopy, neural
spike sorting, and more. The problem is challenging in both theory and
practice, as natural optimization formulations are nonconvex. Moreover,
practical deconvolution problems involve smooth motifs (kernels) whose spectra
decay rapidly, resulting in poor conditioning and numerical challenges. This
paper is motivated by recent theoretical advances, which characterize the
optimization landscape of a particular nonconvex formulation of SaSD. This is
used to derive a $provable$ algorithm which exactly solves certain
non-practical instances of the SaSD problem. We leverage the key ideas from
this theory (sphere constraints, data-driven initialization) to develop a
$practical$ algorithm, which performs well on data arising from a range of
application areas. We highlight key additional challenges posed by the
ill-conditioning of real SaSD problems, and suggest heuristics (acceleration,
continuation, reweighting) to mitigate them. Experiments demonstrate both the
performance and generality of the proposed method.
