Stochastic Trace Estimation for Parameter-Dependent Matrices Applied to Spectral Density Approximation

Abstract.

Stochastic trace estimation is a well-established tool for approximating the trace of a large symmetric matrix [Formula: see text]. Several applications involve a matrix that depends continuously on a parameter [Formula: see text] and require trace estimates of [Formula: see text] for many values of [Formula: see text]. This is, for example, the case when approximating the spectral density of a matrix. Approximating the trace separately for each matrix [Formula: see text] clearly incurs redundancies and a cost that scales linearly with [Formula: see text]. To address this issue, we propose and analyze modifications for three stochastic trace estimators: the Girard–Hutchinson, Nyström, and Nyström++ estimators. Our modification uses fixed randomization across different values of [Formula: see text]; that is, every matrix [Formula: see text] is multiplied with the same set of random vectors. When combined with Chebyshev approximation in [Formula: see text], the use of such constant random matrices allows one to reuse matrix-vector products across different values of [Formula: see text], leading to significant cost reduction. Our analysis shows that the loss of stochastic independence across different [Formula: see text] does not lead to deterioration. In particular, we show that [Formula: see text] random matrix-vector products suffice to ensure an error of [Formula: see text] for Nyström++, independent of low-rank properties of [Formula: see text]. We discuss in detail how the combination of Nyström++ with Chebyshev approximation applies to spectral density estimation and provide an analysis of the resulting method. This improves various aspects of an existing stochastic estimator for spectral density estimation. Several numerical experiments from electronic structure interaction and neural network optimization validate our findings.

Reproducibility of computational results. This paper has been awarded the “SIAM Reproducibility Badge: Code and Data Available” as a recognition that the authors have followed reproducibility principles valued by SISC and the scientific computing community. Code and data that allow readers to reproduce the results in this paper are available at https://github.com/FMatti/parameter-trace and in the supplementary materials ( parameter-trace-main.zip [320KB]), linked from the main article webpage. [Formula: see text]