Optimization Online


Composite optimization for robust blind deconvolution

Vasileios Charisopoulos (vc333***at***cornell.edu)
Damek Davis (dsd95***at***cornell.edu)
Mateo Diaz (md825***at***cornell.edu)
Dmitriy Drusvyatskiy (ddrusv***at***uw.edu)

Abstract: 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.

Keywords: blind deconvolution, Gauss-Newton, subgradient method, weak convexity, composite optimization, spectral

Category 1: Convex and Nonsmooth Optimization


Download: [PDF]

Entry Submitted: 01/06/2019
Entry Accepted: 01/06/2019
Entry Last Modified: 01/18/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society