# Convex Sparse Blind Deconvolution

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 18 references that are in the map.
- First posted on arXiv 13 Jun 2021.

## Builds on (most cited first, 7 of 7)

- [A note on the sample complexity of the Er-SpUD algorithm by Spielman, Wang and Wright for exact recovery of sparsely used dictionaries](https://mlsanity.com/paper/1601.02049/) (2016)
- [Complete Dictionary Recovery over the Sphere](https://mlsanity.com/paper/1504.06785/) (2015)
- [Subgradient Descent Learns Orthogonal Dictionaries](https://mlsanity.com/paper/1810.10702/) (2018)
- [Structured Local Optima in Sparse Blind Deconvolution](https://mlsanity.com/paper/1806.00338/) (2018)
- [Geometry and Symmetry in Short-and-Sparse Deconvolution](https://mlsanity.com/paper/1901.00256/) (2019)
- [Short-and-Sparse Deconvolution -- A Geometric Approach](https://mlsanity.com/paper/1908.10959/) (2019)
- [On the Global Geometry of Sphere-Constrained Sparse Blind Deconvolution](https://mlsanity.com/paper/1901.01913/) (2019)

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

- [Blind Image Deblurring with Unknown Kernel Size and Substantial Noise](https://mlsanity.com/paper/2208.09483/) (2022)
- [PENDANTSS: PEnalized Norm-ratios Disentangling Additive Noise, Trend and Sparse Spikes](https://mlsanity.com/paper/2301.01514/) (2023)

## Abstract (arXiv)

In the blind deconvolution problem, we observe the convolution of an unknown filter and unknown signal and attempt to reconstruct the filter and signal. The problem seems impossible in general, since there are seemingly many more unknowns than knowns . Nevertheless, this problem arises in many application fields; and empirically, some of these fields have had success using heuristic methods -- even economically very important ones, in wireless communications and oil exploration. Today's fashionable heuristic formulations pose non-convex optimization problems which are then attacked heuristically as well. The fact that blind deconvolution can be solved under some repeatable and naturally-occurring circumstances poses a theoretical puzzle. To bridge the gulf between reported successes and theory's limited understanding, we exhibit a convex optimization problem that -- assuming signal sparsity -- can convert a crude approximation to the true filter into a high-accuracy recovery of the true filter. Our proposed formulation is based on L1 minimization of inverse filter outputs. We give sharp guarantees on performance of the minimizer assuming sparsity of signal, showing that our proposal precisely recovers the true inverse filter, up to shift and rescaling. There is a sparsity/initial accuracy tradeoff: the less accurate the initial approximation, the greater we rely on sparsity to enable exact recovery. To our knowledge this is the first reported tradeoff of this kind. We consider it surprising that this tradeoff is independent of dimension. We also develop finite-N guarantees, for highly accurate reconstruction under N≥ O(k log(k) ) with high probability. We further show stable approximation when the true inverse filter is infinitely long and extend our guarantees to the case where the observations are contaminated by stochastic or adversarial noise.