Computational Mathematics and Scientific Computing Seminar

---

Optimal Stochastic Trace Estimation

Speaker: Christopher Musco, New York University

Location: Warren Weaver Hall 1302

Date: April 8, 2022, 10 a.m.

Synopsis:

I will discuss algorithms for an important computational primitive in linear algebra: approximately computing the trace of an implicit matrix that can only be accessed through matrix-vector multiplications. Trace approximation finds applications across machine learning and scientific computing, where it is used to compute matrix norms, spectral densities, log-determinants, triangle counts in graphs, and much more. In 1990, Hutchinson introduced an elegant randomized algorithm for the trace approximation problem that has become ubiquitous in practice. I will introduce a simple modified version of this algorithm that provides the same theoretical guarantees, but requires quadratically fewer matrix-vector multiplications, and performs far better in experiments. We pair this result with matching lower bounds based on reductions to communication complexity and hypothesis testing for spiked-covariance matrices. Our lower bounds fall into a broader research agenda of better understanding the computational complexity of basic linear algebra problems in the restricted "matrix-vector query" model of computation, which generalizes common algorithmic frameworks like linear sketching and Krylov subspace methods.