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

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