Dictionary Learning and Matrix Recovery with Optimal Rate

Let $A$ be an $n \times n$ matrix, $X$ be an $n\times p$ matrix and $Y = AX$. A challenging and important problem in data analysis, motived by dictionary learning, is to recover both $A$ and $X$, given $Y$.
Under normal circumstances, it is clear that the problem is underdetermined. However, as showed by Spielman et. al., one can succeed when $X$ is sufficiently sparse and random.
In this talk, we discuss a solution to a conjecture raised by Spielman et. al. concerning the optimal condition which guarantees efficient recovery. The main technical ingredient of our analysis is a novel way to use the ε-net argument in high dimensions for proving matrix concentration, beating the standard union bound. This part is of independent interest.

Joint work with V. Vu (Yale).