Accurate Trace Estimation with Fewer Random Bits via Recursive TensorSketch

arXiv:2609.18577v1 Announce Type: new Abstract: We consider the problem of estimating the trace of an implicit matrix mathbf{A} in R^{d^pimes d^p} that can only be accessed through matrix-vector products queries. The extit{Hutchinson trace estimator}% ~ite{Girard1987algorithme, article-hutchinson} is a classical sketching method for this problem. Their estimator, H_{m}(mathbf{A}) = frac{1}{m} sum_{i=1}^{m} {mathbf{z}^{(i)}}^T mathbf{A} mathbf{z}^{(i)}, quad ext{where } {mathbf{z}^{(i)}}in R^{d^p}, and z^{(i)}j in {N}(0, 1), jin [d^p], satisfies the following guarantees: (i) E[H{m}(mathbf{A})]=operatorname{tr}(mathbf{A}), and (ii) Var[H_{m}(mathbf{A})]=frac{2}{m}||mathbf{A}||_F^2. Generating one query vector mathbf{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.ite{meyer2025hutchinsonsestimatorbadkroneckertraceestimation} 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 ofite{meyer2025hutchinsonsestimatorbadkroneckertraceestimation} 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!ig(p (d + m)log mig) random bits, yields an unbiased estimate of the trace, and simultaneously achieves a variance bound that grows polynomially with p.

Source: arXiv cs.LG | 2026-09-17