# Hutch++: Optimal Stochastic Trace Estimation

arXiv: https://arxiv.org/abs/2010.09649 · HTML: https://mlsanity.com/paper/2010.09649/

## Key facts

- Cited by 63 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Oct 2020.

## Built on by (most cited first, 30 of 63)

- [Stabilizing Equilibrium Models by Jacobian Regularization](https://mlsanity.com/paper/2106.14342/) (2021)
- [Optimizing Functionals on the Space of Probabilities with Input Convex Neural Networks](https://mlsanity.com/paper/2106.00774/) (2021)
- [Preconditioning for Scalable Gaussian Process Hyperparameter Optimization](https://mlsanity.com/paper/2107.00243/) (2021)
- [Hutchinson Trace Estimation for High-Dimensional and High-Order Physics-Informed Neural Networks](https://mlsanity.com/paper/2312.14499/) (2023)
- [Query lower bounds for log-concave sampling](https://mlsanity.com/paper/2304.02599/) (2023)
- [Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learning](https://mlsanity.com/paper/2406.11151/) (2024)
- [Revisiting Energy Based Models as Policies: Ranking Noise Contrastive Estimation and Interpolating Energy Models](https://mlsanity.com/paper/2309.05803/) (2023)
- [Position: Curvature Matrices Should Be Democratized via Linear Operators](https://mlsanity.com/paper/2501.19183/) (2025)
- [Scalable Multi-Objective and Meta Reinforcement Learning via Gradient Estimation](https://mlsanity.com/paper/2511.12779/) (2025)
- [Low-Rank Approximation with 1/ε1/3 Matrix-Vector Products](https://mlsanity.com/paper/2202.05120/) (2022)
- [Efficient Natural Gradient Descent Methods for Large-Scale PDE-Based Optimization Problems](https://mlsanity.com/paper/2202.06236/) (2022)
- [Optimal Randomized Approximations for Matrix based Renyi's Entropy](https://mlsanity.com/paper/2205.07426/) (2022)
- [Scale-invariant Bayesian Neural Networks with Connectivity Tangent Kernel](https://mlsanity.com/paper/2209.15208/) (2022)
- [Optimal Query Complexities for Dynamic Trace Estimation](https://mlsanity.com/paper/2209.15219/) (2022)
- [Improving Linear System Solvers for Hyperparameter Optimisation in Iterative Gaussian Processes](https://mlsanity.com/paper/2405.18457/) (2024)
- [JPmHC Dynamical Isometry via Orthogonal Hyper-Connections](https://mlsanity.com/paper/2602.18308/) (2026)
- [When can Regression-Adjusted Control Variates Help? Rare Events, Sobolev Embedding and Minimax Optimality](https://mlsanity.com/paper/2305.16527/) (2023)
- [Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning](https://mlsanity.com/paper/2405.05865/) (2024)
- [PRISM: Distribution-free Adaptive Computation of Matrix Functions for Accelerating Neural Network Training](https://mlsanity.com/paper/2601.22137/) (2026)
- [Sharper Bounds for Chebyshev Moment Matching, with Applications](https://mlsanity.com/paper/2408.12385/) (2024)
- [Fast Generalized Neural Tangent Kernel Statistics via Trace Estimation](https://mlsanity.com/paper/2511.10796/) (2025)
- [Mitigating the Contractivity Trap in Diffusion ODEs via Stein Stabilization](https://mlsanity.com/paper/2606.07835/) (2026)
- [Krylov Methods are (nearly) Optimal for Low-Rank Approximation](https://mlsanity.com/paper/2304.03191/) (2023)
- [Moments, Random Walks, and Limits for Spectrum Approximation](https://mlsanity.com/paper/2307.00474/) (2023)
- [Data-Driven Model Selections of Second-Order Particle Dynamics via Integrating Gaussian Processes with Low-Dimensional Interacting Structures](https://mlsanity.com/paper/2311.00902/) (2023)
- [Multivariate trace estimation using quantum state space linear algebra](https://mlsanity.com/paper/2405.01098/) (2024)
- [Faster Spectral Density Estimation and Sparsification in the Nuclear Norm](https://mlsanity.com/paper/2406.07521/) (2024)
- [Optimal Stochastic Trace Estimation in Generative Modeling](https://mlsanity.com/paper/2502.18808/) (2025)
- [Learning-Augmented Frequent Directions](https://mlsanity.com/paper/2503.00937/) (2025)
- [HiGP: A high-performance Python package for Gaussian Process](https://mlsanity.com/paper/2503.02259/) (2025)

## Abstract (arXiv)

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 ± ε) 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.