Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: 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.

14
The categories of this paper are: math-ph
4
The categories of this paper are: cond-mat
32
The categories of this paper are: atom-ph
0
The categories of this paper are: hep-ph
13
The categories of this paper are: quant-ph
6
The categories of this paper are: astro-ph
9
The categories of this paper are: nlin
11
The categories of this paper are: hep-lat
19
The categories of this paper are: eess
23
The categories of this paper are: solv-int
33
The categories of this paper are: plasm-ph
29
The categories of this paper are: funct-an
5
The categories of this paper are: gr-qc
27
The categories of this paper are: comp-gas
37
The categories of this paper are: supr-con
24
The categories of this paper are: dg-ga