Speaker
Description
Stochastic trace estimators are a family of widely used techniques for approximating traces of large matrices accessible only via matrix-vector products. These methods have been studied extensively when applied to constant matrices $B$. We analyze three standard stochastic trace estimators—the Girard-Hutchinson, Nyström, and Nyström++ estimators—when they are applied to parameter-dependent matrices $B(t)$ that continuously depend on a real parameter $t \in [a, b]$. Our key observation is that a single set of random vectors can be reused to form the estimators for all values of $t$, yielding estimates whose $L^1$-error bounds match those of the constant-matrix case. Traces of parameter-dependent matrices arise naturally in important applications, including spectral density estimation and partition function estimation. Building on our analysis, we develop algorithms that combine Chebyshev interpolation with parameter-dependent stochastic trace estimation to obtain efficient methods with provable accuracy guarantees for these problems.