# On the convex geometry of blind deconvolution and matrix completion

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Feb 2019.

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

- [Robust Matrix Completion with Heavy-tailed Noise](https://mlsanity.com/paper/2206.04276/) (2022)
- [WARPd: A linearly convergent first-order method for inverse problems with approximate sharpness conditions](https://mlsanity.com/paper/2110.12437/) (2021)
- [How robust is randomized blind deconvolution via nuclear norm minimization against adversarial noise?](https://mlsanity.com/paper/2303.10030/) (2023)
- [A Morse-Bott Framework for Blind Inverse Problems: Local Recovery Guarantees and the Failure of the MAP](https://mlsanity.com/paper/2508.02923/) (2025)

## Abstract (arXiv)

Low-rank matrix recovery from structured measurements has been a topic of intense study in the last decade and many important problems like matrix completion and blind deconvolution have been formulated in this framework. An important benchmark method to solve these problems is to minimize the nuclear norm, a convex proxy for the rank. A common approach to establish recovery guarantees for this convex program relies on the construction of a so-called approximate dual certificate. However, this approach provides only limited insight in various respects. Most prominently, the noise bounds exhibit seemingly suboptimal dimension factors. In this paper we take a novel, more geometric viewpoint to analyze both the matrix completion and the blind deconvolution scenario. We find that for both these applications the dimension factors in the noise bounds are not an artifact of the proof, but the problems are intrinsically badly conditioned. We show, however, that bad conditioning only arises for very small noise levels: Under mild assumptions that include many realistic noise levels we derive near-optimal error estimates for blind deconvolution under adversarial noise.