[Theory] [Theory Lunch] Raphael Meyer, Wednesday 11/1 12:30pm-1:30pm, JCL 390

[Antares Chen]

************************************************************
**************************

*Date**:* November 1, 2023
*Time: *12:30pm CT
*Location: *JCL 390

*Speaker: *Raphael Meyer <https://ram900.hosting.nyu.edu/> (New York
University)

*Title: **Optimal Trace Estimation, and Sub-optimal Kronecker Trace
Estimation*

*Zoom: *[link
<https://uchicago.zoom.us/j/91616319229?pwd=dDdXQnFXeGNubFRkZy9hTDQrcWlXdz09>
]

*Abstract:* 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.

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!

Joint work with Haim Avron, Cameron Musco, Christopher Musco, David P.
Woodruff.

[Theory Lunch Calendar
<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$>
]

************************************************************
**************************
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20231030/48a111c4/attachment.html>