Hutch++: Optimal Stochastic Trace Estimation.

We study the problem of estimating the trace of a matrix that can only be accessed through matrix-vector multiplication. We introduce a new randomized algorithm, Hutch++, which computes a (1 ± ) approximation to tr( ) for any positive semidefinite (PSD) using just (1) matrix-vector products. This improves on the ubiquitous , which requires (1 ) matrix-vector products.