Back to Search
Start Over
IMPROVED VARIANTS OF THE HUTCH++ ALGORITHM FOR TRACE ESTIMATION.
- Source :
-
SIAM Journal on Matrix Analysis & Applications . 2022, Vol. 43 Issue 3, p1162-1185. 24p. - Publication Year :
- 2022
-
Abstract
- This paper is concerned with two improved variants of the Hutch++ algorithm for estimating the trace of a square matrix, implicitly given through matrix-vector products. Hutch++ combines randomized low-rank approximation in a first phase with stochastic trace estimation in a second phase. In turn, Hutch++ only requires O \bigl(\varepsilon 1 \bigr) matrix-vector products to approximate the trace within a relative error \varepsilon with high probability, provided that the matrix is symmetric positive semidefinite. This compares favorably with the O \bigl(\varepsilon 2 \bigr) matrix-vector products needed when using stochastic trace estimation alone. In Hutch++, the number of matrix-vector products is fixed a priori and distributed in a prescribed fashion among the two phases. In this work, we derive an adaptive variant of Hutch++, which outputs an estimate of the trace that is within some prescribed error tolerance with a controllable failure probability, while splitting the matrix-vector products in a near-optimal way among the two phases. For the special case of a symmetric positive semidefinite matrix, we present another variant of Hutch++, called Nystr\"om++, which utilizes the so-called Nystr\"om approximation and requires only one pass over the matrix, as compared to two passes with Hutch++. We extend the analysis of Hutch++ to Nystr\"om++. Numerical experiments demonstrate the effectiveness of our two new algorithms. [ABSTRACT FROM AUTHOR]
- Subjects :
- *SYMMETRIC matrices
*ALGORITHMS
*STOCHASTIC matrices
Subjects
Details
- Language :
- English
- ISSN :
- 08954798
- Volume :
- 43
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Matrix Analysis & Applications
- Publication Type :
- Academic Journal
- Accession number :
- 159779258
- Full Text :
- https://doi.org/10.1137/21M1447623