<div dir="ltr"><span style="color:rgb(51,51,51);font-family:Arial,Verdana,sans-serif;font-size:medium"><font color="#000000" face="Verdana, Arial, Helvetica">Kyle Luh (Yale): </font></span><span style="font-size:13.3333330154419px;color:rgb(0,0,0);font-family:Tahoma"><font size="3">Dictionary Learning and Matrix Recovery with Optimal Rate</font></span><br><div><span style="font-size:13.3333330154419px;color:rgb(0,0,0);font-family:Tahoma"><font size="3">LOM 215</font></span></div><div><span style="font-size:13.3333330154419px;color:rgb(0,0,0);font-family:Tahoma"><font size="3"><br></font></span></div><div><div style="color:rgb(51,51,51);font-family:Arial,Verdana,sans-serif;font-size:13.3333330154419px"><font face="NimbusRomNo9L" style="font-size:medium;color:rgb(0,0,0)"><br class="">Let </font><font face="CMMI10" style="font-size:medium;color:rgb(0,0,0)">A </font><font face="NimbusRomNo9L" style="font-size:medium;color:rgb(0,0,0)">be an </font><font face="CMMI10" style="font-size:medium;color:rgb(0,0,0)">n</font><font face="CMSY10" style="font-size:medium;color:rgb(0,0,0)">×</font><font face="CMMI10" style="font-size:medium;color:rgb(0,0,0)">n </font><font face="NimbusRomNo9L" style="font-size:medium;color:rgb(0,0,0)">matrix, </font><font face="CMMI10" style="font-size:medium;color:rgb(0,0,0)">X </font><font face="NimbusRomNo9L" style="font-size:medium;color:rgb(0,0,0)">be an </font><font face="CMMI10" style="font-size:medium;color:rgb(0,0,0)">n</font><font face="CMSY10" style="font-size:medium;color:rgb(0,0,0)">×</font><font face="CMMI10" style="font-size:medium;color:rgb(0,0,0)">p </font><font face="NimbusRomNo9L" style="font-size:medium;color:rgb(0,0,0)">matrix and </font><font face="CMMI10" style="font-size:medium;color:rgb(0,0,0)">Y </font><font face="CMR10" style="font-size:medium;color:rgb(0,0,0)">= </font><font face="CMMI10" style="font-size:medium;color:rgb(0,0,0)">AX</font><font face="NimbusRomNo9L" style="font-size:medium;color:rgb(0,0,0)">.  A challenging and important problem in data analysis, motived by </font><font face="NimbusRomNo9L" style="font-size:medium;color:rgb(0,0,0)">dictionary learning, is to recover both A and X, given Y.</font></div><div style="color:rgb(51,51,51);font-family:Arial,Verdana,sans-serif;font-size:13.3333330154419px"><div style="color:rgb(0,0,0);font-family:Tahoma"><div style="margin-top:14pt;margin-bottom:14pt"><font size="3"><font face="NimbusRomNo9L">Under normal circumstances, it is clear that the problem is underdetermined. However, as showed by Spielman et. al.,   </font><font face="NimbusRomNo9L">one can succeed when X is sufficiently sparse and random. </font></font></div><div style="margin-top:14pt;margin-bottom:14pt"><font size="3"><font face="NimbusRomNo9L">In this talk, we discuss a solution to a conjecture  raised by Spielman et. al. concerning the optimal condition which guarantees efficient </font><font face="NimbusRomNo9L">recovery. </font><font face="NimbusRomNo9L">The main  technical ingredient of our analysis is a novel way to use the </font><font face="CMMI10">ε</font><font face="NimbusRomNo9L">-net argument in high dimensions for proving  matrix concentration, beating the standard union bound. This part is of independent interest.</font></font></div></div><div style="color:rgb(0,0,0);font-family:Tahoma"><font face="NimbusRomNo9L" size="3">Joint work with V. Vu (Yale).</font></div><div style="color:rgb(0,0,0);font-family:Tahoma"><font face="NimbusRomNo9L" size="3"><br></font></div></div></div></div>