# Accurate Trace Estimation with Fewer Random Bits via Recursive TensorSketch

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 31 references that are in the map.
- First posted on arXiv 16 Sep 2026.

## Builds on (most cited first, 11 of 11)

- [Hutch++: Optimal Stochastic Trace Estimation](https://mlsanity.com/paper/2010.09649/) (2020)
- [Optimal Sketching for Trace Estimation](https://mlsanity.com/paper/2111.00664/) (2021)
- [Sublinear Time Spectral Density Estimation](https://mlsanity.com/paper/2104.03461/) (2021)
- [Optimal Eigenvalue Approximation via Sketching](https://mlsanity.com/paper/2304.09281/) (2023)
- [Querying a Matrix through Matrix-Vector Products](https://mlsanity.com/paper/1906.05736/) (2019)
- [Low-Rank Approximation with 1/ε1/3 Matrix-Vector Products](https://mlsanity.com/paper/2202.05120/) (2022)
- [Optimal query complexity for estimating the trace of a matrix](https://mlsanity.com/paper/1405.7112/) (2014)
- [Hutchinson's Estimator is Bad at Kronecker-Trace-Estimation](https://mlsanity.com/paper/2309.04952/) (2023)
- [Tensor Sketch: Fast and Scalable Polynomial Kernel Approximation](https://mlsanity.com/paper/2505.08146/) (2025)
- [Multivariate trace estimation using quantum state space linear algebra](https://mlsanity.com/paper/2405.01098/) (2024)
- [Simple Tabulation, Fast Expanders, Double Tabulation, and High Independence](https://mlsanity.com/paper/1311.3121/) (2013)

## Abstract (arXiv)

We consider the problem of estimating the trace of an implicit matrix A ∈ ℝdp× dp that can only be accessed through matrix-vector products queries. The textitHutchinson trace estimator% ~citeGirard1987algorithme, article-hutchinson is a classical sketching method for this problem. Their estimator, Hm(A) = frac1m sumi=1m z(i)T A z(i), quad where   z(i)∈ ℝdp, and z(i)j ∈ N(0, 1), j∈ [dp], satisfies the following guarantees: (i) mathbbE[Hm(A)]=operatornametr(A), and (ii) Var[Hm(A)]=frac2m||A||F2. Generating one query vector z(i) requires O(dp) random bits; thus, m queries require O(mdp) random bits, which can be prohibitive in large-scale applications. Recent work by Meyer et al.~citemeyer2025hutchinsonsestimatorbadkroneckertraceestimation proposes a variant of the Hutchinson trace estimator in which each query vector in ℝdp is constructed as the Kronecker product of p random vectors in ℝd, requiring O(mpd) random bits for m query vectors. The estimator of~citemeyer2025hutchinsonsestimatorbadkroneckertraceestimation is unbiased; however, its variance grows exponentially with p. In this work, we address this limitation by proposing a sketching-based estimator that requires O!big(p (d + m)log mbig) random bits, yields an unbiased estimate of the trace, and simultaneously achieves a variance bound that grows polynomially with p.