Premium
On the Convex Geometry of Blind Deconvolution and Matrix Completion
Author(s) -
Krahmer Felix,
Stöger Dominik
Publication year - 2021
Publication title -
communications on pure and applied mathematics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 3.12
H-Index - 115
eISSN - 1097-0312
pISSN - 0010-3640
DOI - 10.1002/cpa.21957
Subject(s) - matrix completion , blind deconvolution , matrix norm , mathematics , dimension (graph theory) , mathematical optimization , deconvolution , convex optimization , noise (video) , matrix (chemical analysis) , low rank approximation , convex hull , algorithm , regular polygon , computer science , artificial intelligence , pure mathematics , geometry , image (mathematics) , eigenvalues and eigenvectors , physics , materials science , quantum mechanics , composite material , tensor (intrinsic definition) , gaussian
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 into 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. © 2020 The Authors. Communications on Pure and Applied Mathematics published by Wiley Periodicals LLC