Dictionary Learning and Matrix Recovery with Optimal Rate

-
Van Vu, Yale University
Fine Hall 214

Let A be an n×n matrix, X be an n×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 K. Luh (Yale).