XT<scp>race</scp>: Making the Most of Every Sample in Stochastic Trace Estimation
From MaRDI portal
Publication:6180350
Abstract: The implicit trace estimation problem asks for an approximation of the trace of a square matrix, accessed via matrix-vector products (matvecs). This paper designs new randomized algorithms, XTrace and XNysTrace, for the trace estimation problem by exploiting both variance reduction and the exchangeability principle. For a fixed budget of matvecs, numerical experiments show that the new methods can achieve errors that are orders of magnitude smaller than existing algorithms, such as the Girard-Hutchinson estimator or the Hutch++ estimator. A theoretical analysis confirms the benefits by offering a precise description of the performance of these algorithms as a function of the spectrum of the input matrix. The paper also develops an exchangeable estimator, XDiag, for approximating the diagonal of a square matrix using matvecs.
Recommendations
Cites work
- A fast ``Monte-Carlo cross-validation procedure for large least squares problems with noisy data
- A fast randomized algorithm for overdetermined linear least-squares regression
- A Stochastic Estimator of the Trace of the Influence Matrix for Laplacian Smoothing Splines
- Algorithm 971
- An estimator for the diagonal of a matrix
- Blendenpik: Supercharging LAPACK's Least-Squares Solver
- Computing the action of the matrix exponential, with an application to exponential integrators
- Deflation as a method of variance reduction for estimating the trace of a matrix inverse
- Fast estimation of \(\mathrm{tr}(f(A))\) via stochastic Lanczos quadrature
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- Functions of Matrices
- scientific article; zbMATH DE number 5485456 (Why is no real title available?)
- Improved Variants of the Hutch++ Algorithm for Trace Estimation
- Krylov-Aware Stochastic Trace Estimation
- Practical sketching algorithms for low-rank matrix approximation
- Randomized estimation of spectral densities of large matrices made accurate
- Randomized matrix-free trace and log-determinant estimators
- Randomized numerical linear algebra: Foundations and algorithms
- The many facets of the Estrada indices of graphs and networks
- The Theory of Unbiased Estimation
- The University of Florida sparse matrix collection
Cited in
(16)- Faster randomized partial trace estimation
- Analysis of stochastic probing methods for estimating the trace of functions of sparse symmetric matrices
- Deep Gaussian process priors for Bayesian image reconstruction
- Randomized matrix-free quadrature: unified and uniform bounds for stochastic Lanczos quadrature and the kernel polynomial method
- Improved bounds for randomized Schatten norm estimation of numerically low-rank matrices
- ContHutch++: stochastic trace estimation for implicit integral operators
- Randomized block-Krylov subspace methods for low-rank approximation of matrix functions
- Preconditioning without a preconditioner using randomized block Krylov subspace methods
- Estimation of spectral gaps for sparse symmetric matrices
- Optimal sensor placement under model uncertainty in the weak-constraint 4D-Var framework
- Stochastic trace estimation for parameter-dependent matrices applied to spectral density approximation
- Scalability of the second-order reliability method for stochastic differential equations with multiplicative noise
- Stochastic trace and diagonal estimator for tensors
- Walk based Laplacians for modeling diffusion on complex networks
- Hutch#: Optimal non-adaptive Frobenius norm estimation
- matsketch
This page was built for publication: XT<scp>race</scp>: Making the Most of Every Sample in Stochastic Trace Estimation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6180350)
