Hutch++: Optimal Stochastic Trace Estimation
This provides a more efficient solution for trace estimation in large-scale numerical linear algebra, with applications in machine learning and scientific computing, representing a significant improvement over the standard method.
The paper tackles the problem of estimating the trace of a matrix accessed via matrix-vector multiplication by introducing Hutch++, a randomized algorithm that computes a (1 ± ε) approximation for positive semidefinite matrices using O(1/ε) matrix-vector products, improving on Hutchinson's estimator which requires O(1/ε²) products.
We study the problem of estimating the trace of a matrix $A$ that can only be accessed through matrix-vector multiplication. We introduce a new randomized algorithm, Hutch++, which computes a $(1 \pm ε)$ approximation to $tr(A)$ for any positive semidefinite (PSD) $A$ using just $O(1/ε)$ matrix-vector products. This improves on the ubiquitous Hutchinson's estimator, which requires $O(1/ε^2)$ 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 mainly requires $A$ to be positive semidefinite, we provide generalized guarantees for general square matrices, and show empirical gains in such applications.