# Stochastic trace estimation with tensor train random vectors

arXiv: https://arxiv.org/abs/2606.15679 · HTML: https://mlsanity.com/paper/2606.15679/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 28 references that are in the map.
- First posted on arXiv 14 Jun 2026.

## Builds on (most cited first, 6 of 6)

- [Hutch++: Optimal Stochastic Trace Estimation](https://mlsanity.com/paper/2010.09649/) (2020)
- [Tensorized Random Projections](https://mlsanity.com/paper/2003.05101/) (2020)
- [Approximately Counting Triangles in Sublinear Time](https://mlsanity.com/paper/1504.00954/) (2015)
- [Hutchinson's Estimator is Bad at Kronecker-Trace-Estimation](https://mlsanity.com/paper/2309.04952/) (2023)
- [Faster Linear Algebra Algorithms with Structured Random Matrices](https://mlsanity.com/paper/2508.21189/) (2025)
- [Linear-Scaling Tensor Train Sketching](https://mlsanity.com/paper/2603.11009/) (2026)

## Abstract (arXiv)

Stochastic trace estimation is a standard tool for approximating the trace of a large-scale matrix available only through matrix-vector products. However, in tensor-structured settings, unstructured Gaussian or Rademacher test vectors may be prohibitively expensive to store and compute with, while cheaper rank-one tensor-product vectors can require sample complexities that grow exponentially with the tensor order. This work studies Gaussian random tensor train vectors as a structured alternative for stochastic trace estimation. We show that, with a suitable choice of the tensor train rank, random tensor train vectors recover dimension-independent guarantees for the Girard--Hutchinson estimator. In particular, a median-of-means variant with tensor train rank r ≥ d-1 achieves the same dependence on the accuracy varepsilon and failure probability δ as the classical estimator based on unstructured Gaussian vectors. We further prove an oblivious subspace injection result for sketches formed from independent Gaussian random tensor train vectors: tensor train rank r≥ d-1 and O(varepsilon-2(k+log(1/δ))) samples suffice for a k-dimensional target subspace. Finally, we investigate the use of such sketches within the Nystr"om++ framework. We show that the resulting estimator can achieve the desired O(varepsilon-1) sample complexity under an additional spectral-tail condition. These results provide clarififcation on both the potential and the limitations of random tensor train vectors in stochastic trace estimation.