Two Variations on the XTrace Algorithm
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912742592479232 |
|---|---|
| author | Hallman, Eric |
| author_facet | Hallman, Eric |
| contents | This paper studies two potential modifications of XTrace (Epperly et al., SIMAX 45(1):1-23, 2024), a randomized algorithm for estimating the trace of a matrix. The first is a variance reduction step that averages the output of XTrace over right-multiplications of the test vectors by random orthogonal matrices. The second is to form a low-rank approximation to the matrix using the whole Krylov space produced by the test vectors, rather than the output of a single power iteration as is used by XTrace. Experiments on synthetic data show that the first modification offers only slight benefits in practice, while the second can lead to significant improvements depending on the spectrum of the matrix. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_02316 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Two Variations on the XTrace Algorithm Hallman, Eric Numerical Analysis 65C05, 65F30, 68W20 This paper studies two potential modifications of XTrace (Epperly et al., SIMAX 45(1):1-23, 2024), a randomized algorithm for estimating the trace of a matrix. The first is a variance reduction step that averages the output of XTrace over right-multiplications of the test vectors by random orthogonal matrices. The second is to form a low-rank approximation to the matrix using the whole Krylov space produced by the test vectors, rather than the output of a single power iteration as is used by XTrace. Experiments on synthetic data show that the first modification offers only slight benefits in practice, while the second can lead to significant improvements depending on the spectrum of the matrix. |
| title | Two Variations on the XTrace Algorithm |
| topic | Numerical Analysis 65C05, 65F30, 68W20 |
| url | https://arxiv.org/abs/2512.02316 |