Improved bounds on sample size for implicit matrix trace estimators

DOI10.1007/S10208-014-9220-1MaRDI QIDQ887152zbMATH OpenOpenAlexFDO

Authors Farbod Roosta-Khorasani, Uri M. Ascher

Publication date 28 October 2015

Published in Foundations of Computational Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1308.2475

zbMATH Keywords

Monte Carlo methodsrandomized algorithmstrace estimationimplicit linear operators

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Randomized algorithms (68W20)

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 $w{w}^t(Aww)$, 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.

Recommendations

• Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix
• How accurately should I compute implicit matrix-vector products when applying the Hutchinson trace estimator?
• Optimal query complexity for estimating the trace of a matrix
• Improved Variants of the Hutch++ Algorithm for Trace Estimation
• Randomized matrix-free trace and log-determinant estimators

Cites work

• scientific article; zbMATH DE number 3436435 (Why is no real title available?)
• scientific article; zbMATH DE number 3273551 (Why is no real title available?)
• A stochastic estimator of the trace of the influence matrix for laplacian smoothing splines
• Adaptive and stochastic algorithms for electrical impedance tomography and DC resistivity problems with piecewise constant solutions and many measurements
• An Application of Random Projection to Parameter Estimation in Partial Differential Equations
• An effective method for parameter estimation with PDE constraints with multiple right-hand sides
• An estimator for the diagonal of a matrix
• Column subset selection, matrix factorization, and eigenvalue optimization
• Extremal probabilities for Gaussian quadratic forms
• Generalized Cross-Validation as a Method for Choosing a Good Ridge Parameter
• Lectures on Stochastic Programming
• Probability inequalities for the sum in sampling without replacement
• Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix
• Some large-scale matrix computation problems
• Stochastic algorithms for inverse problems involving PDEs and many measurements

Cited in

(38)

• Error bounds for computed least squares estimators
• Taylor approximation and variance reduction for PDE-constrained optimal control under uncertainty
• Randomized approaches to accelerate MCMC algorithms for Bayesian inverse problems
• scientific article; zbMATH DE number 7049740 (Why is no real title available?)
• A Multilevel Approach to Variance Reduction in the Stochastic Estimation of the Trace of a Matrix
• Fast Estimation of Approximate Matrix Ranks Using Spectral Densities
• Stochastic sampling for deterministic structural topology optimization with many load cases: density-based and ground structure approaches
• Algorithms that satisfy a stopping criterion, probably
• Full Waveform Inversion Using Extended and Simultaneous Sources
• A general scheme for log-determinant computation of matrices via stochastic polynomial approximation
• scientific article; zbMATH DE number 7415079 (Why is no real title available?)
• Approximating spectral sums of large-scale matrices using stochastic Chebyshev approximations
• Randomized matrix-free trace and log-determinant estimators
• Improved bounds for small-sample estimation
• Monte Carlo Methods for Estimating the Diagonal of a Real Symmetric Matrix
• Schur properties of convolutions of gamma random variables
• A Fast and Scalable Method for A-Optimal Design of Experiments for Infinite-dimensional Bayesian Nonlinear Inverse Problems
• Hypercontractivity via tensor calculus
• On randomized trace estimates for indefinite matrices with an application to determinants
• Optimal query complexity for estimating the trace of a matrix
• Scalable Gaussian Process Computations Using Hierarchical Matrices
• Improved Variants of the Hutch++ Algorithm for Trace Estimation
• Randomized block Krylov subspace methods for trace and log-determinant estimators
• Efficient estimation of eigenvalue counts in an interval.
• A FEAST SVDsolver based on Chebyshev-Jackson series for computing partial singular triplets of large matrices
• Randomized Low-Rank Approximation of Monotone Matrix Functions
• Faster randomized partial trace estimation
• Norm and trace estimation with random rank-one vectors
• Monte Carlo estimators for the Schatten \(p\)-norm of symmetric positive semidefinite matrices
• Analysis of stochastic probing methods for estimating the trace of functions of sparse symmetric matrices
• Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix
• Going Off the Grid: Iterative Model Selection for Biclustered Matrix Completion
• Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness
• A multilevel approach to stochastic trace estimation
• Streaming low-rank matrix approximation with an application to scientific simulation
• How accurately should I compute implicit matrix-vector products when applying the Hutchinson trace estimator?
• Fast estimation of \(\mathrm{tr}(f(A))\) via stochastic Lanczos quadrature
• Mean-variance risk-averse optimal control of systems governed by PDEs with random parameter fields using quadratic approximations

This page was built for publication: Improved bounds on sample size for implicit matrix trace estimators

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