Title: Dictionary Learning and Matrix Recovery with Optimal Rate

Abstract:

Let A be an nxn matrix, X be an nxp matrix and Y = AX.  A challenging and important problem in data analysis, motived by  dictionary learning and other practical problems, 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, Wang and Wright (2012), 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 an economical  way to use the \epsilon-net argument in high dimensions for proving  matrix concentration, beating the standard union bound. This part is of independent interest.