Structured Local Optima in Sparse Blind Deconvolution
This work addresses a fundamental problem in signal processing with applications in imaging and communications, but it is incremental as it builds on existing nonconvex optimization methods for structured signals.
The paper tackles the ill-posed problem of sparse blind deconvolution by analyzing local optima in a nonconvex optimization framework, showing that under conditions like sparsity θ ≲ k^{-2/3} and measurements m ≳ poly(k), a descent algorithm recovers a near shift truncation of the ground truth kernel.
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 $θ\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.