Accurate Trace Estimation with Fewer Random Bits via Recursive TensorSketch

We consider the problem of estimating the trace of an implicit matrix A in R d p times d p that can only be accessed through matrix-vector products queries. The Hutchinson trace estimator% is a classical sketching method for this problem. Their estimator, H m(A) = 1 over m sum i=1 m z(i) T A z(i), where z(i) in R d p, and z(i) j in N (0, 1), j in [d p], satisfies the following guarantees: (i) E[H m(A)]= tr(A), and (ii) Var[H m(A)]= 2 over m A F squared. Generating one query vector z(i) requires O(d p) random bits; thus, m queries require O(md p) random bits, which can be prohibitive in large-scale applications. Recent work by Meyer et al. proposes a variant of the Hutchinson trace estimator in which each query vector in R d p is constructed as the Kronecker product of p random vectors in R d, requiring O(mpd) random bits for m query vectors. The estimator of 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! (p (d + m) m) random bits, yields an unbiased estimate of the trace, and simultaneously achieves a variance bound that grows polynomially with p.