Efficient trace estimation using fewer random bits with controlled variance
Accurate Trace Estimation with Fewer Random Bits via Recursive TensorSketch
Machine LearningData Structures and Algorithms
Summary
Estimating the trace of a large matrix is important but usually requires costly random data and many calculations. The authors improve on a classic method so that it uses far fewer random bits, making it more practical for very large matrices. Their new approach keeps the estimate accurate by carefully combining random data with mathematical techniques, avoiding errors that grow too large. This makes it easier to estimate the trace in situations where using lots of random bits is prohibitive.
What this means in practice
- •For machine learning engineers: Enable efficient estimation of trace-related matrix properties in large models with substantially reduced randomness and computation.
- •For scientific computing teams: Reduce resource requirements when computing traces of large implicit matrices in simulations and data analysis workflows.
Authors
Mohammad Azhar Khan, Rameshwar Pratap, Amit Sharma
Abstract
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 \textit{Hutchinson trace 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)}, \quad \text{where } \ {\mathbf{z}^{(i)}}\in \mathbb{R}^{d^p}$, and $z^{(i)}_j \in {N}(0, 1), j\in [d^p]$, satisfies the following guarantees: (i) $\mathbb{E}[H_{m}(\mathbf{A})]=\operatorname{tr}(\mathbf{A})$, and (ii) $\mathrm{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.~\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\!\big(p (d + m)\log m\big)$ random bits, yields an unbiased estimate of the trace, and simultaneously achieves a variance bound that grows polynomially with $p$.