Fetching the paper…

Reading the bibliography…

2023

XTrace: Making the most of every sample in stochastic trace estimation

Epperly, Ethan N., Tropp, Joel A., Webber, Robert J.

Original
PDF
Post on X

Understand

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.

XTrace: Making the most of every sample in stochastic trace estimation · Around

Built on

P. R. Halmos
1946
Earlier work this paper cites.
P. Pfeuty
1970
Earlier work this paper cites.
A. Girard
1989
Earlier work this paper cites.
M. F. Hutchinson
1989
Earlier work this paper cites.
V. S. Koroljuk and Y. V. Borovskich
1994
Earlier work this paper cites.
R. A. Meyer, C. Musco, C. Musco, and D. P. Woodruff
Original
2002
Earlier work this paper cites.
D. Bu, Y. Zhao, L. Cai, H. Xue, X. Zhu, H. Lu, J. Zhang, S. Sun, L. Ling, N. Zhang, G. Li, and R. Chen
2003
Earlier work this paper cites.
C. Bekas, E. Kokiopoulou, and Y. Saad
2007
Earlier work this paper cites.
A. C. Gilbert, M. J. Strauss, J. A. Tropp, and R. Vershynin
2007
Earlier work this paper cites.
N. J. Higham
2008
Earlier work this paper cites.
V. Rokhlin and M. Tygert
2008
Earlier work this paper cites.
H. Avron, P. Maymounkov, and S. Toledo
2010
Earlier work this paper cites.

Similar

A. H. Al-Mohy and N. J. Higham
2011
Cited alongside, same era.
T. Davis and Y. Hu
2011
Cited alongside, same era.
N. Halko, P.-G. Martinsson, and J. A. Tropp
2011
Cited alongside, same era.
A. S. Gambhir, A. Stathopoulos, and K. Orginos
2017
Cited alongside, same era.
H. Li, G. C. Linderman, A. Szlam, K. P. Stanton, Y. Kluger, and M. Tygert
2017
Cited alongside, same era.
A. K. Saibaba, A. Alexanderian, and I. C. F. Ipsen
2017
Cited alongside, same era.
J. A. Tropp, A. Yurtsever, M. Udell, and V. Cevher
2017
Cited alongside, same era.

Then

P.-G. Martinsson and J. A. Tropp
2020
Later among the works it cites.
S. Jiang, H. Pham, D. P. Woodruff, and Q. Zhang
2021
Later among the works it cites.
R. A. Meyer, C. Musco, C. Musco, and D. P. Woodruff
2021
Later among the works it cites.
R. A. Baston and Y. Nakatsukasa
Original
2022
Later among the works it cites.
T. Chen and E. Hallman
Original
2022
Later among the works it cites.
T. Chen, T. Trogdon, and S. Ubaru
Original
2022
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

S. Ubaru, J. Chen, and Y. Saad

2017

Cited alongside, same era.

S. Ubaru and Y. Saad

2017

Cited alongside, same era.

M. Al Hasan and V. S. Dave

2018

Cited alongside, same era.

Available at http://staff.fysik.su.se/~ardonne/files/theses/bachelor-thesis_christopher-litens.pdf

C. Litens · 2019

Cited alongside, same era.

E. Estrada

2022

Later among the works it cites.

Available at https://www.mathworks.com/matlabcentral/fileexchange/29576-matrix-exponential-times-a-vector (accessed 10/25/2022)

N. J. Higham · 2022

Later among the works it cites.

D. Persson, A. Cortinovis, and D. Kressner

2022

Later among the works it cites.

E. N. Epperly and J. A. Tropp

2023

Closest in time.

J. A. Tropp and R. J. Webber

2023

Closest in time.