Optimal Stochastic Trace Estimation

Christopher Musco
New York University

Wednesday, Oct 28, 2020
4:30 - 5:30 PM



Abstract:

I will discuss algorithms for an important computational primitive in linear algebra: approximately computing the trace of an implicit matrix A 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.

Joint work with Raphael A. Meyer, Cameron Musco, and David P. Woodruff. Paper is available at: https://arxiv.org/abs/2010.09649

---

Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html