On the convex geometry of blind deconvolution and matrix completion
  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.
