Nonconvex Sparse Blind Deconvolution: Geometry and Algorithm

Yuqian Zhang (CS, Cornell University)

Blind deconvolution is an ill-posed problem aiming to recover a convolution kernel and an activation signal from their convolution. We focus on the short and sparse variant, where the convolution kernel is short and the activation signal is sparsely and randomly supported. This variant models convolutional signals in several important application scenarios. The observation is invariant up to some mutual scaling and shift of the convolutional pairs. This scaled-shift symmetry is intrinsic to the convolution operator and imposes challenges for reliable algorithm design. We normalize the convolution kernel to have unit Frobenius norm and then cast the blind deconvolution problem as a nonconvex optimization problem over the sphere. We demonstrate that (i) under conditions, every local optimum is close to some shift truncation of the ground truth, and (ii) for a generic filter of length k, when the sparsity of activation signal satisfies θ < k^{2/3} and number of measurements m > poly(k), provable recovery of some shift truncation of the ground truth kernel can be obtained.