Structured Local Optima in Sparse Blind Deconvolution

Blind deconvolution is a ubiquitous problem aiming to recover a convolution kernel a(0) is an element of R-k and an activation signal x(0) is an element of R-m from their convolution y is an element of R-m. Unfortunately, this is an ill-posed problem in general. This paper focuses on the short and sparse blind deconvolution problem, where the convolution kernel is short (k << m) and the activation signal is sparsely and randomly supported (parallel to x(0)parallel to(0) << m). This variant captures the structure of the convolutional signals in several important application scenarios. In this paper, we normalize the convolution kernel to have unit Frobenius norm and then cast the blind deconvolution problem as a nonconvex optimization problem over the kernel 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 unit kernel a(0), when the sparsity of activation signal satisfies theta less than or similar to k(-2/3) and number of measurements m greater than or similar to poly (k), the proposed initialization method together with a descent algorithm which escapes strict saddle points recovers some shift truncation of the ground truth kernel.