<div dir="ltr"><div style="font-family:Calibri,Arial,Helvetica,sans-serif"><span style="font-family:Arial,Helvetica,sans-serif;font-size:large">******************************</span><span style="font-family:Arial,Helvetica,sans-serif;font-size:large">******************************</span><span style="font-family:Arial,Helvetica,sans-serif;font-size:large">**************************</span><b style="font-family:inherit;font-style:inherit;font-variant-ligatures:inherit;font-variant-caps:inherit;color:rgb(49,49,49);word-spacing:1px"><font size="4"><br></font></b></div><div style="font-family:Calibri,Arial,Helvetica,sans-serif"><b style="font-family:inherit;font-style:inherit;font-variant-ligatures:inherit;font-variant-caps:inherit;color:rgb(49,49,49);word-spacing:1px"><font size="4"><br></font></b></div><div style="font-family:Calibri,Arial,Helvetica,sans-serif"><b style="font-family:inherit;font-style:inherit;font-variant-ligatures:inherit;font-variant-caps:inherit;color:rgb(49,49,49);word-spacing:1px"><font size="4">Date</font></b><b style="font-family:inherit;font-style:inherit;font-variant-ligatures:inherit;font-variant-caps:inherit;font-size:1.13em;color:rgb(49,49,49);word-spacing:1px">:</b><span style="font-size:1.13em;color:rgb(49,49,49);word-spacing:1px"> </span><span style="color:rgb(49,49,49);word-spacing:1px"><font size="4">November 1, 2023</font></span><br></div><div><div style="margin:0px"><div style="margin:0px"><div style="margin:0px"><div style="margin:0px"><div style="margin:0px"><div style="color:rgb(32,31,30);font-family:Calibri,Arial,Helvetica,sans-serif;margin:0px"><div style="font-size:16px;margin:0px;color:rgb(49,49,49);word-spacing:1px"><font style="font-size:1.13em"><b>Time: </b>12:30pm CT</font></div><div style="font-size:16px;margin:0px;color:rgb(49,49,49);word-spacing:1px"><font style="font-size:1.13em"><b>Location: </b>JCL 390</font></div><div dir="auto" style="font-size:16px;margin:0px;color:rgb(49,49,49);word-spacing:1px"><b><font style="font-size:1.13em"><br></font></b></div><div dir="auto" style="margin:0px;color:rgb(49,49,49);word-spacing:1px"><font size="4"><b>Speaker: </b></font><span style="color:rgb(60,64,67);font-family:Roboto,Arial,sans-serif;letter-spacing:0.2px"><font size="4"><a href="https://ram900.hosting.nyu.edu/" target="_blank">Raphael Meyer</a> (New York University)</font></span></div><div dir="auto" style="font-size:16px;margin:0px;color:rgb(49,49,49);word-spacing:1px"><font size="4"><br></font></div></div><div style="margin:0px"><span style="color:rgb(49,49,49);font-family:Calibri,Arial,Helvetica,sans-serif;font-size:16px;word-spacing:1px"><font style="font-size:1.13em"><b>Title: </b></font></span><font size="4"><b>Optimal Trace Estimation, and Sub-optimal Kronecker Trace Estimation</b></font></div><div style="color:rgb(32,31,30);font-family:Calibri,Arial,Helvetica,sans-serif;font-size:15px;margin:0px"><b style="color:rgb(49,49,49);font-size:16px;word-spacing:1px"><font style="font-size:1.13em"><br></font></b></div><div style="color:rgb(32,31,30);font-family:Calibri,Arial,Helvetica,sans-serif;font-size:15px;margin:0px"><span style="margin:0px;font-size:16px;color:rgb(49,49,49);word-spacing:1px"><font style="font-size:1.13em"><b>Zoom: </b>[<a href="https://uchicago.zoom.us/j/91616319229?pwd=dDdXQnFXeGNubFRkZy9hTDQrcWlXdz09" target="_blank">link</a>]</font></span></div><div style="color:rgb(32,31,30);font-family:Calibri,Arial,Helvetica,sans-serif;font-size:15px;margin:0px"><br></div><div style="margin:0px"><div dir="auto" style="margin:0px"><font style="word-spacing:1px"><span style="color:rgb(49,49,49);font-family:Calibri,Arial,Helvetica,sans-serif;font-size:13pt;margin:0px"><b>Abstract:</b></span><span style="color:rgb(32,31,30);font-family:"trebuchet ms",sans-serif;font-size:12pt;margin:0px;word-spacing:0px"> </span></font><font size="4">A fundamental task in linear algebra is that of trace estimation: Suppose we have a PSD matrix A that can be accessed only by matrix-vector products. Then, with as few matrix-vector products as possible, estimate the trace of A to relative error (1+-eps) with high probability. This is an essential subroutine in all sorts of applications, for instance in efficiently estimating the log-determinant of a matrix.</font></div><font size="4"><br>In the first part of the talk, I'll rigorously introduce this problem, the prior state-of-the-art algorithm (the Girard-Hutchinson Estimator), and our improvement upon it (the Hutch++ Estimator), which we show to have asymptotically optimal matrix-vector complexity. In the second part of the talk, I'll introduce a Kronecker-structured variant of this problem with applications for tensorized data, alongside the only known algorithm that solves this problem. However, we'll see that this algorithm converges very slowly, alongside some evidence that a faster algorithm *should* exist. Designing this faster algorithm remains an open problem!<br><br>Joint work with Haim Avron, Cameron Musco, Christopher Musco, David P. Woodruff.</font><div dir="auto" style="margin:0px"><br></div><div dir="auto" style="margin:0px"><font style="word-spacing:1px"><span style="margin:0px;word-spacing:0px"><span style="color:rgb(32,31,30);font-family:Calibri,Arial,Helvetica,sans-serif;font-size:large">[</span><a href="https://urldefense.com/v3/__https://calendar.google.com/calendar/u/0/embed?src=c_osgf1c1qemdras8mu7l7pdhjrs@group.calendar.google.com&ctz=America*Chicago__;Lw!!BpyFHLRN4TMTrA!pwdRh9yLA-IBD6NCNvREJGd9Nj5jtC6_N-AowF6HSwIQeb1FPAmu0L_tAsww4XtIRnQ$" rel="noopener noreferrer" title="https://calendar.google.com/calendar/u/0/embed?src=c_osgf1c1qemdras8mu7l7pdhjrs@group.calendar.google.com&ctz=America/Chicago" style="font-family:Calibri,Arial,Helvetica,sans-serif;font-size:large;margin:0px" target="_blank"><span style="margin:0px"><span style="margin:0px"><span style="margin:0px"><span style="margin:0px"><span style="margin:0px"><span style="margin:0px"><span style="margin:0px">Theory</span></span></span></span></span></span></span><span style="margin:0px"> </span><span style="margin:0px"><span style="margin:0px"><span style="margin:0px"><span style="margin:0px"><span style="margin:0px">Lunch</span></span></span></span></span><span style="margin:0px"> </span>Calendar</a><span style="color:rgb(32,31,30);font-family:Calibri,Arial,Helvetica,sans-serif;font-size:large">]</span></span></font></div><div dir="auto" style="margin:0px"><font style="word-spacing:1px"><span style="margin:0px;word-spacing:0px"><span style="color:rgb(32,31,30);font-family:Calibri,Arial,Helvetica,sans-serif;font-size:large"><br></span></span></font></div><div dir="auto" style="margin:0px"><font style="word-spacing:1px"><span style="margin:0px;word-spacing:0px"><span style="font-size:large">******************************</span><span style="font-size:large">******************************</span><span style="font-size:large">**************************</span></span></font></div></div></div></div></div></div></div></div></div>