[Combprob] this Thursday: Kyle Luh (Yale): Dictionary Learning and Matrix Recovery with Optimal Rate

[Daniel Spielman]

Thursday, March 5 at 4:00PM.
LOM 215

Kyle Luh (Yale): Dictionary Learning and Matrix Recovery with Optimal Rate

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 V. Vu (Yale).