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 O(1/ε) matrix-vector products. This improves on the ubiquitous Hutchinson's estimator, which requires O(1/ε ²) matrix-vector products. Our approach is based on a simple technique for reducing the variance of Hutchinson's estimator using a low-rank approximation step, and is easy to implement and analyze. Moreover, we prove that, up to a logarithmic factor, the complexity of Hutch++ is optimal amongst all matrix-vector query algorithms, even when queries can be chosen adaptively. We show that it significantly outperforms Hutchinson's method in experiments. While our theory requires to be positive semidefinite, empirical gains extend to applications involving non-PSD matrices, such as triangle estimation in networks.