A Multilevel Approach to Stochastic Trace Estimation

DOI10.1016/J.LAA.2021.12.010MaRDI QIDQ6363209arXivFDO

Authors Eric Hallman, Devon Troester

Publication date 18 March 2021

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.LAA.2021.12.010

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Numerical computation of matrix exponential and similar matrix functions (65F60)

arXiv classification

cs.NAmath.NA

Abstract: This article presents a randomized matrix-free method for approximating the trace of $$, where $$ is a large symmetric matrix and $f$ is a function analytic in a closed interval containing the eigenvalues of $$. Our method uses a combination of stochastic trace estimation (i.e., Hutchinson's method), Chebyshev approximation, and multilevel Monte Carlo techniques. We establish general bounds on the approximation error of this method by extending an existing error bound for Hutchinson's method to multilevel trace estimators. Numerical experiments are conducted for common applications such as estimating the log-determinant, nuclear norm, and Estrada index, and triangle counting in graphs. We find that using multilevel techniques can substantially reduce the variance of existing single-level estimators.

This page was built for publication: A Multilevel Approach to Stochastic Trace Estimation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6363209)