Stochastic trace estimation for positive trace-class operators
Abstract
Implicit trace estimation aims to approximate the trace of a matrix or linear operator accessible only through matrix-vector or operator-vector products. In the matrix setting, the Girard-Hutchinson estimator typically requires 𝒪(ε−2) products to achieve accuracy ε, while the variance-reduced Hutch++ algorithm reduces this sample complexity to 𝒪(ε−1) for positive semidefinite matrices. We develop infinite-dimensional analogues of these estimators for positive trace-class operators on separable Hilbert spaces. The idealized estimators use Gaussian random elements whose covariance is determined by the target operator, leading to unbiased operator versions of Girard-Hutchinson and Hutch++. We prove high-probability error bounds analogous to the finite-dimensional matrix results; in particular, idealized infHutch++ achieves 𝒪(ε−1) sample complexity. For practical computation, we introduce truncated implementations that restrict the random samples to finite-dimensional subspaces; for fixed sample budget, we show that truncated infHutch++ converges in distribution to its idealized counterpart as the truncation dimension tends to infinity. Numerical experiments with integral operators, density-of-states approximations, and spectral filtering for a radial Dirac operator show that these truncated estimators can achieve accuracy comparable to the ContHutch++ algorithm by Zvonek, Horning & Townsend while using lower-degree function representations and smaller internal discretizations in chebfun.
Related
- Convergence of finite element approximations for the one-dimensional stochastic Burgers equation with additive trace-class noise
- Analytical solutions of one class of Volterra quadratic stochastic operators of a two-sex population with continuous time
- Functions of Sp-almost commuting unitary operators and contractions. An extension of the Carey--Pincus trace formula
- Construction of trace-preserving Fortin operators
- A long time Gutzwiller trace formula for perturbations of Schrödinger operators near Anosov energy levels
BibTeX
@misc{bujanovic2026stochastic,
title = {{Stochastic trace estimation for positive trace-class operators}},
author = {Zvonimir Bujanović and Luka Grubišić and Daniel Kressner and Hrvoje Olić},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.28135},
eprint = {2608.28135},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.28135},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Stochastic trace estimation for positive trace-class operators
AU - Zvonimir Bujanović
AU - Luka Grubišić
AU - Daniel Kressner
AU - Hrvoje Olić
PY - 2026
DA - 2026/08/28
PB - arXiv
DO - 10.48550/arxiv.2608.28135
UR - https://arxiv.org/abs/2608.28135
AB - Implicit trace estimation aims to approximate the trace of a matrix or linear operator accessible only through matrix-vector or operator-vector products. In the matrix setting, the Girard-Hutchinson estimator typically requires 𝒪(ε^−2) products to achieve accuracy ε, while the variance-reduced Hutch++ algorithm reduces this sample complexity to 𝒪(ε^−1) for positive semidefinite matrices. We develop infinite-dimensional analogues of these estimators for positive trace-class operators on separable Hilbert spaces. The idealized estimators use Gaussian random elements whose covariance is determined by the target operator, leading to unbiased operator versions of Girard-Hutchinson and Hutch++. We prove high-probability error bounds analogous to the finite-dimensional matrix results; in particular, idealized infHutch++ achieves 𝒪(ε^−1) sample complexity. For practical computation, we introduce truncated implementations that restrict the random samples to finite-dimensional subspaces; for fixed sample budget, we show that truncated infHutch++ converges in distribution to its idealized counterpart as the truncation dimension tends to infinity. Numerical experiments with integral operators, density-of-states approximations, and spectral filtering for a radial Dirac operator show that these truncated estimators can achieve accuracy comparable to the ContHutch++ algorithm by Zvonek, Horning & Townsend while using lower-degree function representations and smaller internal discretizations in chebfun.
ER -