On the convex geometry of blind deconvolution and matrix completion
This work addresses theoretical limitations in recovery guarantees for matrix completion and blind deconvolution, providing insights into noise sensitivity for researchers in signal processing and optimization.
The paper tackled the problem of low-rank matrix recovery in matrix completion and blind deconvolution by analyzing the convex geometry of nuclear norm minimization, revealing that dimension factors in noise bounds are intrinsic but near-optimal error estimates are achievable under realistic noise levels.
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.