Accurate Trace Estimation with Fewer Random Bits via Recursive TensorSketch

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.