[Combprob] talk today at 4:00: Kyle Luh (Yale): Dictionary Learning and Matrix Recovery with Optimal Rate

[Daniel Spielman]

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


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).
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.yale.edu/pipermail/combprob/attachments/20150305/09ef6c42/attachment.html