Short-and-Sparse Deconvolution -- A Geometric Approach

Abstract

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.

*YL and QQ contributed equally to this work; 30 figures, 45 pages; This version: added an experiment comparing with other methods, corrected typos and added references

References in corpus (18)

• How to detect fluctuating order in the high-temperature superconductors
• Topological Surface States Protected From Backscattering by Chiral Spin Texture
• Fast Online Deconvolution of Calcium Imaging Data
• Fast non-negative deconvolution for spike train inference from population calcium imaging
• Global rates of convergence for nonconvex optimization on manifolds
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Self-Calibration and Biconvex Compressive Sensing
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• Convolutional Dictionary Learning: A Comparative Review and New Algorithms
• Inertial Proximal Alternating Linearized Minimization (iPALM) for Nonconvex and Nonsmooth Problems
• Guaranteed Blind Sparse Spikes Deconvolution via Lifting and Convex Optimization
• Convolutional Dictionary Learning: Acceleration and Convergence
• Forward-backward quasi-Newton methods for nonsmooth optimization problems
• Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
• When Are Nonconvex Problems Not Scary?
• Revisiting Bayesian Blind Deconvolution
• First and Second Order Methods for Online Convolutional Dictionary Learning
• Spike Sorting by Convolutional Dictionary Learning

Cited by in corpus (1)

• Analysis of the Optimization Landscapes for Overcomplete Representation Learning