# How robust is randomized blind deconvolution via nuclear norm minimization against adversarial noise?

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 39 references that are in the map.
- First posted on arXiv 17 Mar 2023.

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

- [Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution](https://mlsanity.com/paper/1711.10467/) (2017)
- [Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization](https://mlsanity.com/paper/1902.07698/) (2019)
- [Scalable Semidefinite Programming](https://mlsanity.com/paper/1912.02949/) (2019)
- [Harmonic Mean Iteratively Reweighted Least Squares for Low-Rank Matrix Recovery](https://mlsanity.com/paper/1703.05038/) (2017)
- [On the convex geometry of blind deconvolution and matrix completion](https://mlsanity.com/paper/1902.11156/) (2019)
- [Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution under Random Designs](https://mlsanity.com/paper/2008.01724/) (2020)
- [Proof methods for robust low-rank matrix recovery](https://mlsanity.com/paper/2106.04382/) (2021)

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

- [Adversarial Purification by Consistency-aware Latent Space Optimization on Data Manifolds](https://mlsanity.com/paper/2412.08394/) (2024)

## Abstract (arXiv)

In this paper, we study the problem of recovering two unknown signals from their convolution, which is commonly referred to as blind deconvolution. Reformulation of blind deconvolution as a low-rank recovery problem has led to multiple theoretical recovery guarantees in the past decade due to the success of the nuclear norm minimization heuristic. In particular, in the absence of noise, exact recovery has been established for sufficiently incoherent signals contained in lower-dimensional subspaces. However, if the convolution is corrupted by additive bounded noise, the stability of the recovery problem remains much less understood. In particular, existing reconstruction bounds involve large dimension factors and therefore fail to explain the empirical evidence for dimension-independent robustness of nuclear norm minimization. Recently, theoretical evidence has emerged for ill-posed behavior of low-rank matrix recovery for sufficiently small noise levels. In this work, we develop improved recovery guarantees for blind deconvolution with adversarial noise which exhibit square-root scaling in the noise level. Hence, our results are consistent with existing counterexamples which speak against linear scaling in the noise level as demonstrated for related low-rank matrix recovery problems.