Accurate Trace Estimation with Fewer Random Bits via Recursive TensorSketch

We consider the problem of estimating the trace of an implicit matrix $\mathbf{A}\in {\mathbb{R}}^{d^p\times d^p}$ that can only be accessed through matrix-vector products queries. The $\mathit{\text{Hutchinson}}\mathit{\text{trace}}\mathit{\text{estimator}}$% ~\cite{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)},\text{where }{\mathbf{z}}^{(i)}\in {\mathbb{R}}^{d^p}$, and $z_j^{(i)}\in N(0,1),j\in [d^p]$, satisfies the following guarantees: (i) $\mathbb{E}[H_m(\mathbf{A})]=\mathrm{tr}(\mathbf{A})$, and (ii) $\mathrm{V}\mathrm{a}\mathrm{r}[H_m(\mathbf{A})]=\frac{2}{m}\mathrm{\mid }\mathrm{\mid }\mathbf{A}\mathrm{\mid }{\mathrm{\mid }}_F^2$. Generating one query vector ${\mathbf{z}}^{(i)}$ requires $O(d^p)$ random bits; thus, $m$ queries require $O(m{d}^p)$ random bits, which can be prohibitive in large-scale applications. Recent work by Meyer et al.~\cite{meyer2025hutchinsonsestimatorbadkroneckertraceestimation} proposes a variant of the Hutchinson trace estimator in which each query vector in ${\mathbb{R}}^{d^p}$ is constructed as the Kronecker product of $p$ random vectors in ${\mathbb{R}}^d$, requiring $O(mpd)$ random bits for $m$ query vectors. The estimator of~\cite{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\text{\hspace{0.17em}⁣}(p(d+m)\log m)$ random bits, yields an unbiased estimate of the trace, and simultaneously achieves a variance bound that grows polynomially with $p$.