# Optimal Sketching for Trace Estimation

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Nov 2021.

## Built on by (most cited first, 11 of 11)

- [Solving Attention Kernel Regression Problem via Pre-conditioner](https://mlsanity.com/paper/2308.14304/) (2023)
- [Efficient SGD Neural Network Training via Sublinear Activated Neuron Identification](https://mlsanity.com/paper/2307.06565/) (2023)
- [Optimal Query Complexities for Dynamic Trace Estimation](https://mlsanity.com/paper/2209.15219/) (2022)
- [Sharper Bounds for Chebyshev Moment Matching, with Applications](https://mlsanity.com/paper/2408.12385/) (2024)
- [BOLT: Block-Orthonormal Lanczos for Trace estimation of matrix functions](https://mlsanity.com/paper/2505.12289/) (2025)
- [Matrix-Free Two-to-Infinity and One-to-Two Norms Estimation](https://mlsanity.com/paper/2508.04444/) (2025)
- [Online Adaptive Mahalanobis Distance Estimation](https://mlsanity.com/paper/2309.01030/) (2023)
- [Fast Heavy Inner Product Identification Between Weights and Inputs in Neural Network Training](https://mlsanity.com/paper/2311.11429/) (2023)
- [Query Efficient Structured Matrix Learning](https://mlsanity.com/paper/2507.19290/) (2025)
- [StAD: Stein Amortized Divergence for Fast Likelihoods with Diffusion and Flow](https://mlsanity.com/paper/2605.16486/) (2026)
- [Accurate Trace Estimation with Fewer Random Bits via Recursive TensorSketch](https://mlsanity.com/paper/2609.18577/) (2026)

## Abstract (arXiv)

Matrix trace estimation is ubiquitous in machine learning applications and has traditionally relied on Hutchinson's method, which requires O(log(1/δ)/ε2) matrix-vector product queries to achieve a (1 ± ε)-multiplicative approximation to tr(A) with failure probability δ on positive-semidefinite input matrices A. Recently, the Hutch++ algorithm was proposed, which reduces the number of matrix-vector queries from O(1/ε2) to the optimal O(1/ε), and the algorithm succeeds with constant probability. However, in the high probability setting, the non-adaptive Hutch++ algorithm suffers an extra O(√log(1/δ)) multiplicative factor in its query complexity. Non-adaptive methods are important, as they correspond to sketching algorithms, which are mergeable, highly parallelizable, and provide low-memory streaming algorithms as well as low-communication distributed protocols. In this work, we close the gap between non-adaptive and adaptive algorithms, showing that even non-adaptive algorithms can achieve O(√log(1/δ)/ε + log(1/δ)) matrix-vector products. In addition, we prove matching lower bounds demonstrating that, up to a log log(1/δ) factor, no further improvement in the dependence on δ or ε is possible by any non-adaptive algorithm. Finally, our experiments demonstrate the superior performance of our sketch over the adaptive Hutch++ algorithm, which is less parallelizable, as well as over the non-adaptive Hutchinson's method.