XTrace: Making the most of every sample in stochastic trace estimation
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911749186256896 |
|---|---|
| author | Epperly, Ethan N. Tropp, Joel A. Webber, Robert J. |
| author_facet | Epperly, Ethan N. Tropp, Joel A. Webber, Robert J. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2301_07825 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | XTrace: Making the most of every sample in stochastic trace estimation Epperly, Ethan N. Tropp, Joel A. Webber, Robert J. Numerical Analysis 65C05, 65F30, 68W20 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. |
| title | XTrace: Making the most of every sample in stochastic trace estimation |
| topic | Numerical Analysis 65C05, 65F30, 68W20 |
| url | https://arxiv.org/abs/2301.07825 |