Title: Structured Local Optima in Sparse Blind Deconvolution,
Abstract: Blind deconvolution is a ubiquitous problem of recovering two unknown signals
from their convolution. Unfortunately, this is an ill-posed problem in general.
This paper focuses on the {\em short and sparse} blind deconvolution problem,
where the one unknown signal is short and the other one is sparsely and
randomly supported. This variant captures the structure of the unknown signals
in several important applications. We assume the short signal to have unit
$\ell^2$ norm and cast the blind deconvolution problem as a nonconvex
optimization problem over the sphere. We demonstrate that (i) in a certain
region of the sphere, every local optimum is close to some shift truncation of
the ground truth, and (ii) for a generic short signal of length $k$, when the
sparsity of activation signal $\theta\lesssim k^{-2/3}$ and number of
measurements $m\gtrsim poly(k)$, a simple initialization method together with a
descent algorithm which escapes strict saddle points recovers a near shift
truncation of the ground truth kernel.