ÍâÍøÌìÌÃ

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).Ìý