Krylov-Aware Stochastic Trace Estimation

DOI10.1137/22M1494257zbMath1525.65042arXiv2205.01736OpenAlexW4385985976MaRDI QIDQ6094742

Tyler Chen, Eric Hallman

Publication date: 14 September 2023

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

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

zbMATH Keywords

spectral functionKrylov subspace methodlow-rank approximationblock-Lanczos methodHutchinson's methodquadratic trace estimation

Mathematics Subject Classification ID

Determinants, permanents, traces, other special matrix functions (15A15) Numerical computation of matrix exponential and similar matrix functions (65F60) Numerical methods for low-rank matrix approximation; matrix compression (65F55)

Related Items (5)

Computation of the von Neumann entropy of large matrices via trace estimators and rational Krylov methods ⋮ XT<scp>race</scp>: Making the Most of Every Sample in Stochastic Trace Estimation ⋮ Faster randomized partial trace estimation ⋮ Analysis of stochastic probing methods for estimating the trace of functions of sparse symmetric matrices ⋮ A posteriori error bounds for the block-Lanczos method for matrix function approximation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions
• Error bounds and estimates for Krylov subspace approximations of Stieltjes matrix functions
• Randomized estimation of spectral densities of large matrices made accurate
• Block Krylov-Schur method for large symmetric eigenvalue problems
• The simple Lanczos procedure: Estimates of the error of the Gauss quadrature formula and their applications
• Error bounds in the simple Lanczos procedure for computing functions of symmetric matrices and eigenvalues
• Estimating the trace of the matrix inverse by interpolating from the diagonal of an approximate inverse
• Randomized block Krylov subspace methods for trace and log-determinant estimators
• A multilevel approach to stochastic trace estimation
• An estimator for the diagonal of a matrix
• 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
• Thick-Restart Lanczos Method for Large Symmetric Eigenvalue Problems
• A Krylov--Schur Algorithm for Large Eigenproblems
• 2-Norm Error Bounds and Estimates for Lanczos Approximations to Linear Systems and Rational Matrix Functions
• The university of Florida sparse matrix collection
• A restarted Lanczos approximation to functions of a symmetric matrix
• The kernel polynomial method
• An Algorithm for the Principal Component Analysis of Large Data Sets
• 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
• Stopping Criteria for Rational Matrix Functions of Hermitian and Symmetric Matrices
• Implicit Application of Polynomial Filters in a k-Step Arnoldi Method
• On the Perturbation of Pseudo-Inverses, Projections and Linear Least Squares Problems
• IRBL: An Implicitly Restarted Block-Lanczos Method for Large-Scale Hermitian Eigenproblems
• Improved Bounds for Small-Sample Estimation
• Fast Estimation of $tr(f(A))$ via Stochastic Lanczos Quadrature
• Stability of the Lanczos Method for Matrix Function Approximation
• Improved Variants of the Hutch++ Algorithm for Trace Estimation
• A Comparison of Limited-memory Krylov Methods for Stieltjes Functions of Hermitian Matrices
• Convergence of Restarted Krylov Subspace Methods for Stieltjes Functions of Matrices
• Approximating Spectral Sums of Large-Scale Matrices using Stochastic Chebyshev Approximations
• Structural Convergence Results for Approximation of Dominant Subspaces from Block Krylov Spaces
• Functions of Matrices
• Deflation as a Method of Variance Reduction for Estimating the Trace of a Matrix Inverse
• Error Bounds for Lanczos-Based Matrix Function Approximation
• Randomized numerical linear algebra: Foundations and algorithms
• Randomized Low-Rank Approximation of Monotone Matrix Functions

This page was built for publication: Krylov-Aware Stochastic Trace Estimation