Improved bounds on sample size for implicit matrix trace estimators

DOI10.1007/S10208-014-9220-1zbMATH Open1323.65043arXiv1308.2475OpenAlexW3105113144MaRDI QIDQ887152FDOQ887152

Authors: Farbod Roosta-Khorasani, Uri M. Ascher 

Publication date: 28 October 2015

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

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.

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

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

zbMATH Keywords

Monte Carlo methodsrandomized algorithmstrace estimationimplicit linear operators

Mathematics Subject Classification ID

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

Cites Work

• Generalized Cross-Validation as a Method for Choosing a Good Ridge Parameter
• Title not available (Why is that?)
• Extremal probabilities for Gaussian quadratic forms
• Title not available (Why is that?)
• Lectures on Stochastic Programming
• Stochastic algorithms for inverse problems involving PDEs and many measurements
• Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix
• 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
• A stochastic estimator of the trace of the influence matrix for laplacian smoothing splines
• Some large-scale matrix computation problems
• An estimator for the diagonal of a matrix
• Probability inequalities for the sum in sampling without replacement
• Column subset selection, matrix factorization, and eigenvalue optimization
• Adaptive and stochastic algorithms for electrical impedance tomography and DC resistivity problems with piecewise constant solutions 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
• Title not available (Why is that?)
• Randomized approaches to accelerate MCMC algorithms for Bayesian inverse problems
• Fast Estimation of Approximate Matrix Ranks Using Spectral Densities
• A Multilevel Approach to Variance Reduction in the Stochastic Estimation of the Trace of a Matrix
• Stochastic sampling for deterministic structural topology optimization with many load cases: density-based and ground structure approaches
• Full Waveform Inversion Using Extended and Simultaneous Sources
• Algorithms that satisfy a stopping criterion, probably
• Title not available (Why is that?)
• A general scheme for log-determinant computation of matrices via stochastic polynomial approximation
• Approximating spectral sums of large-scale matrices using stochastic Chebyshev approximations
• Improved bounds for small-sample estimation
• Randomized matrix-free trace and log-determinant estimators
• 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
• Efficient estimation of eigenvalue counts in an interval.
• Randomized block Krylov subspace methods for trace and log-determinant estimators
• 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
• Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness
• Going Off the Grid: Iterative Model Selection for Biclustered Matrix Completion
• A multilevel approach to stochastic trace estimation
• Streaming low-rank matrix approximation with an application to scientific simulation
• Fast estimation of \(\mathrm{tr}(f(A))\) via stochastic Lanczos quadrature
• How accurately should I compute implicit matrix-vector products when applying the Hutchinson trace estimator?
• 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)