Improved bounds on sample size for implicit matrix trace estimators

DOI10.1007/S10208-014-9220-1zbMath1323.65043arXiv1308.2475OpenAlexW3105113144MaRDI QIDQ887152

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)

Related Items (34)

Algorithms that satisfy a stopping criterion, probably ⋮ Monte Carlo Methods for Estimating the Diagonal of a Real Symmetric Matrix ⋮ Randomized approaches to accelerate MCMC algorithms for Bayesian inverse problems ⋮ A Fast and Scalable Method for A-Optimal Design of Experiments for Infinite-dimensional Bayesian Nonlinear Inverse Problems ⋮ Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness ⋮ Improved Bounds for Small-Sample Estimation ⋮ Randomized matrix-free trace and log-determinant estimators ⋮ Improved Variants of the Hutch++ Algorithm for Trace Estimation ⋮ On randomized trace estimates for indefinite matrices with an application to determinants ⋮ Monte Carlo estimators for the Schatten \(p\)-norm of symmetric positive semidefinite matrices ⋮ A Multilevel Approach to Variance Reduction in the Stochastic Estimation of the Trace of a Matrix ⋮ Schur properties of convolutions of gamma random variables ⋮ Fast Estimation of $tr(f(A))$ via Stochastic Lanczos Quadrature ⋮ Approximating Spectral Sums of Large-Scale Matrices using Stochastic Chebyshev Approximations ⋮ A FEAST SVDsolver based on Chebyshev-Jackson series for computing partial singular triplets of large matrices ⋮ Efficient estimation of eigenvalue counts in an interval ⋮ Randomized Low-Rank Approximation of Monotone Matrix Functions ⋮ Hypercontractivity via tensor calculus ⋮ Taylor approximation and variance reduction for PDE-constrained optimal control under uncertainty ⋮ Fast Estimation of Approximate Matrix Ranks Using Spectral Densities ⋮ A general scheme for log-determinant computation of matrices via stochastic polynomial approximation ⋮ Mean-Variance Risk-Averse Optimal Control of Systems Governed by PDEs with Random Parameter Fields Using Quadratic Approximations ⋮ Norm and Trace Estimation with Random Rank-one Vectors ⋮ Error bounds for computed least squares estimators ⋮ Randomized block Krylov subspace methods for trace and log-determinant estimators ⋮ Full Waveform Inversion Using Extended and Simultaneous Sources ⋮ Going Off the Grid: Iterative Model Selection for Biclustered Matrix Completion ⋮ Scalable Gaussian Process Computations Using Hierarchical Matrices ⋮ Stochastic sampling for deterministic structural topology optimization with many load cases: density-based and ground structure approaches ⋮ 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? ⋮ A multilevel approach to stochastic trace estimation ⋮ Unnamed Item ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Extremal probabilities for Gaussian quadratic forms
• Probability inequalities for the sum in sampling without replacement
• An estimator for the diagonal of a matrix
• Some large-scale matrix computation problems
• Adaptive and Stochastic Algorithms for Electrical Impedance Tomography and DC Resistivity Problems with Piecewise Constant Solutions and Many Measurements
• 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
• Lectures on Stochastic Programming
• Generalized Cross-Validation as a Method for Choosing a Good Ridge Parameter
• Column Subset Selection, Matrix Factorization, and Eigenvalue Optimization
• 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

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