Improved bounds on sample size for implicit matrix trace estimators

Abstract

This article is concerned with Monte-Carlo methods for the estimation of the trace of an implicitly given matrix $A$ whose information is only available through matrix-vector products. Such a method approximates the trace by an average of $N$ expressions of the form $\ww^t (A\ww)$, with random vectors $\ww$ drawn from an appropriate distribution. We prove, discuss and experiment with bounds on the number of realizations $N$ required in order to guarantee a probabilistic bound on the relative error of the trace estimation upon employing Rademacher (Hutchinson), Gaussian and uniform unit vector (with and without replacement) probability distributions. In total, one necessary bound and six sufficient bounds are proved, improving upon and extending similar estimates obtained in the seminal work of Avron and Toledo (2011) in several dimensions. We first improve their bound on $N$ for the Hutchinson method, dropping a term that relates to $rank(A)$ and making the bound comparable with that for the Gaussian estimator. We further prove new sufficient bounds for the Hutchinson, Gaussian and the unit vector estimators, as well as a necessary bound for the Gaussian estimator, which depend more specifically on properties of the matrix $A$. As such they may suggest for what type of matrices one distribution or another provides a particularly effective or relatively ineffective stochastic estimation method.

Cited by in corpus (19)

• Accuracy of the finite-temperature Lanczos method compared to simple typicality-based estimates
• Taylor approximation and variance reduction for PDE-constrained optimal control under uncertainty
• Hutchinson Trace Estimation for High-Dimensional and High-Order Physics-Informed Neural Networks
• Stochastic Sampling for Structural Topology Optimization with Many Load Cases: Density-Based and Ground Structure Approaches
• Fast estimation of approximate matrix ranks using spectral densities
• Public Transport Planning: When Transit Network Connectivity Meets Commuting Demand
• Assessing stochastic algorithms for large scale nonlinear least squares problems using extremal probabilities of linear combinations of gamma random variables
• Accuracy of the typicality approach using Chebyshev polynomials
• Sublinear Time Spectral Density Estimation
• Numerical computation of the equilibrium-reduced density matrix for strongly coupled open quantum systems
• A Data-Scalable Randomized Misfit Approach for Solving Large-Scale PDE-Constrained Inverse Problems
• A FEAST SVDsolver based on Chebyshev--Jackson series for computing partial singular triplets of large matrices
• Finite-size scaling of typicality-based estimates
• Schur properties of convolutions of gamma random variables
• Computationally Efficient Approximations for Matrix-based Renyi's Entropy
• A spectrum adaptive kernel polynomial method
• Escaping the Krylov space during finite precision Lanczos
• Going off the Grid: Iterative Model Selection for Biclustered Matrix Completion
• Faster randomized partial trace estimation