Back to Search
Start Over
XTRACE: MAKING THE MOST OF EVERY SAMPLE IN STOCHASTIC TRACE ESTIMATION.
- Source :
-
SIAM Journal on Matrix Analysis & Applications . 2024, Vol. 45 Issue 1, p1-23. 23p. - Publication Year :
- 2024
-
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. [ABSTRACT FROM AUTHOR]
- Subjects :
- *BUDGET
*ALGORITHMS
Subjects
Details
- Language :
- English
- ISSN :
- 08954798
- Volume :
- 45
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Matrix Analysis & Applications
- Publication Type :
- Academic Journal
- Accession number :
- 177132684
- Full Text :
- https://doi.org/10.1137/23M1548323