Sparse Blind Deconvolution: What Cannot Be Done

Identifiability is a key concern in ill-posed blind deconvolution problems arising in wireless communications and image processing. The single channel version of the problem is the most challenging and there have been efforts to use sparse models for regularizing the problem. Identifiability of the sparse blind deconvolution problem is analyzed and it is established that a simple sparsity assumption in the canonical basis is insufficient for unique recovery; a surprising negative result. The proof technique involves lifting the deconvolution problem into a rank one matrix recovery problem and analyzing the rank two null-space of the resultant linear operator. A DoF (degrees of freedom) wise tight parametrized subset of this rank two null-space is constructed to establish the results.