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 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. We will show this is a result of this Kronecker-structured computational model, which elicits strange computational properties. We will see that good design decisions in the non-Kronecker case can cause catastrophic failure in the Kronecker case, that using complex random variables leads to exponential speedups over reals, and that subgaussianity does not suffice to understand the performance of randomized algorithms here.

Joint work with Haim Avron, David Woodruff, and William Swartworth.