Composite optimization for robust blind deconvolution
This work addresses robust signal recovery in blind deconvolution, which is important for applications like image processing and communications, but it appears incremental as it builds on existing nonsmooth formulations and algorithms.
The paper tackles the blind deconvolution problem by analyzing a nonsmooth formulation, showing that under standard assumptions, key properties like weak convexity and sharpness are dimension-independent even with up to half of measurements corrupted by noise, leading to rapid convergence of standard algorithms when properly initialized. It also introduces a provably efficient and robust initialization strategy, validated through numerical experiments on simulated and real data.
The blind deconvolution problem seeks to recover a pair of vectors from a set of rank one bilinear measurements. We consider a natural nonsmooth formulation of the problem and show that under standard statistical assumptions, its moduli of weak convexity, sharpness, and Lipschitz continuity are all dimension independent. This phenomenon persists even when up to half of the measurements are corrupted by noise. Consequently, standard algorithms, such as the subgradient and prox-linear methods, converge at a rapid dimension-independent rate when initialized within constant relative error of the solution. We then complete the paper with a new initialization strategy, complementing the local search algorithms. The initialization procedure is both provably efficient and robust to outlying measurements. Numerical experiments, on both simulated and real data, illustrate the developed theory and methods.