Improved Variants of the Hutch++ Algorithm for Trace Estimation

DOI10.1137/21M1447623zbMath1492.65112arXiv2109.10659OpenAlexW3200812363MaRDI QIDQ5094217

David Persson, Alice Cortinovis, Daniel Kressner

Publication date: 2 August 2022

Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

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

zbMATH Keywords

adaptive algorithmslow-rank approximationtrace estimation

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Monte Carlo methods (65C05) Determinants, permanents, traces, other special matrix functions (15A15) Numerical methods for low-rank matrix approximation; matrix compression (65F55)

Related Items (5)

Hutch++ ⋮ Krylov-Aware Stochastic Trace Estimation ⋮ Computation of the von Neumann entropy of large matrices via trace estimators and rational Krylov methods ⋮ Randomized Low-Rank Approximation of Monotone Matrix Functions ⋮ XT<scp>race</scp>: Making the Most of Every Sample in Stochastic Trace Estimation

Uses Software

• SparseMatrix

Cites Work

• Unnamed Item
• Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions
• Randomized estimation of spectral densities of large matrices made accurate
• Improved bounds on sample size for implicit matrix trace estimators
• Estimating the trace of the matrix inverse by interpolating from the diagonal of an approximate inverse
• Estimating the Estrada index
• Randomized matrix-free trace and log-determinant estimators
• Some large-scale matrix computation problems
• On randomized trace estimates for indefinite matrices with an application to determinants
• A DEIM Induced CUR Factorization
• The university of Florida sparse matrix collection
• Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix
• Network Properties Revealed through Matrix Functions
• Analysis of Probing Techniques for Sparse Approximation and Trace Estimation of Decaying Matrix Functions
• Assessing Stochastic Algorithms for Large Scale Nonlinear Least Squares Problems Using Extremal Probabilities of Linear Combinations of Gamma Random Variables
• A Stochastic Estimator of the Trace of the Influence Matrix for Laplacian Smoothing Splines
• On Krylov Subspace Approximations to the Matrix Exponential Operator
• Improved Bounds for Small-Sample Estimation
• Log-determinant relaxation for approximate inference in discrete Markov random fields
• Practical Sketching Algorithms for Low-Rank Matrix Approximation
• Norm and Trace Estimation with Random Rank-one Vectors
• Functions of Matrices
• Deflation as a Method of Variance Reduction for Estimating the Trace of a Matrix Inverse
• Randomized numerical linear algebra: Foundations and algorithms

This page was built for publication: Improved Variants of the Hutch++ Algorithm for Trace Estimation