Sparse blind deconvolution via thresholded Wirtinger flow

Blind deconvolution is a classical problem arising in many signal processing and machine learning applications, where one aims to recover an unknown kernel and an unknown signal from their convolution. Since both the kernel and the signal are unknown, the problem is intrinsically ill-posed, and meaningful recovery is possible only under suitable structural assumptions. In this paper, we study sparse blind deconvolution, where the kernel is $s_h$-sparse and the signal admits an $s_x$-sparse representation in a known dictionary. Although sparsity is a natural and practically relevant prior, its interaction with the bilinear observation model creates substantial challenges for both computation and analysis. To address these challenges, we propose Thresholded Wirtinger Flow (ThWF), a simple and scalable iterative algorithm equipped with a sparse spectral initialization. For noiseless observations, we prove that the proposed initialization achieves exact support recovery with sample complexity $M \gtrsim s_h^2+s_x^2$, up to logarithmic factors. Building on this initialization, we establish what is, to the best of our knowledge, the first algorithmic convergence guarantee for sparse blind deconvolution: ThWF converges linearly to the ground truth, up to the inherent scaling ambiguity, provided that $M \gtrsim s_h+s_x$ up to logarithmic factors. Our analysis further extends to noisy measurements, showing that ThWF is robust and contracts linearly up to a statistical error under a bounded noise level. Experiments on synthetic data and real-world image deblurring tasks corroborate the predicted linear convergence and phase transition behavior, and demonstrate the restoration performance of the proposed method.