# Composite optimization for robust blind deconvolution

arXiv: https://arxiv.org/abs/1901.01624 · HTML: https://mlsanity.com/paper/1901.01624/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Jan 2019.

## Built on by (most cited first, 3 of 3)

- [Robust Low-rank Tensor Train Recovery](https://mlsanity.com/paper/2410.15224/) (2024)
- [A New Inexact Proximal Linear Algorithm with Adaptive Stopping Criteria for Robust Phase Retrieval](https://mlsanity.com/paper/2304.12522/) (2023)
- [An inexact LPA for DC composite optimization and application to matrix completions with outliers](https://mlsanity.com/paper/2303.16822/) (2023)

## Abstract (arXiv)

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.