Composite optimization for robust blind deconvolution

Understand

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.