Robustness and Convergence of Mirror Descent for Blind Deconvolution

We revisit the Blind Deconvolution problem with a focus on understanding its robustness/convergence properties. Interest in provable robustness to noise and other perturbations is growing -- from obtaining immunity to adversarial attacks to assessing and describing failure modes of algorithms in mission critical applications. Further, many blind deconvolution methods based on deep architectures internally make use of or optimize the basic formulation, so a clearer understanding of how this sub-module behaves and when it can be solved is a first order requirement. We derive new theoretical insights for the core blind deconvolution problem. The algorithm that emerges has nice convergence guarantees and is provably robust in a sense we formalize in the paper. Proof of concept implementations play out well across standard datasets.