Analysis of stochastic probing methods for estimating the trace of functions of sparse symmetric matrices

Frommer, Andreas; Rinelli, Michele; Schweitzer, Marcel

doi:10.1090/mcom/3984

Analysis of stochastic probing methods for estimating the trace of functions of sparse symmetric matrices
HTML articles powered by AMS MathViewer

by Andreas Frommer, Michele Rinelli and Marcel Schweitzer;

Math. Comp. 94 (2025), 801-823

DOI: https://doi.org/10.1090/mcom/3984

Published electronically: June 17, 2024

HTML | PDF | Request permission

Abstract:

We consider the problem of estimating the trace of a matrix function $f(A)$. In certain situations, in particular if $f(A)$ cannot be well approximated by a low-rank matrix, combining probing methods based on graph colorings with stochastic trace estimation techniques can yield accurate approximations at moderate cost. So far, such methods have not been thoroughly analyzed, though, but were rather used as efficient heuristics by practitioners. In this manuscript, we perform a detailed analysis of stochastic probing methods and, in particular, expose conditions under which the expected approximation error in the stochastic probing method scales more favorably with the dimension of the matrix than the error in non-stochastic probing. Extending results from Aune, Simpson, and Eidsvik [Stat. Comput. 24 (2014), pp. 247–263], we also characterize situations in which using just one stochastic vector is always—not only in expectation—better than the deterministic probing method. Several numerical experiments illustrate our theory and compare with existing methods.

References

Erlend Aune, Daniel P. Simpson, and Jo Eidsvik, Parameter estimation in high dimensional Gaussian distributions, Stat. Comput. 24 (2014), no. 2, 247–263. MR 3165552, DOI 10.1007/s11222-012-9368-y
Haim Avron and Sivan Toledo, Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix, J. ACM 58 (2011), no. 2, Art. 8, 17. MR 2786589, DOI 10.1145/1944345.1944349
R. Babich, R. C. Brower, M. A. Clark, G. T. Fleming, J. C. Osborn, C. Rebbi, and D. Schaich, Exploring strange nucleon form factors on the lattice, Phys. Rev. D 85 (2012), no. 5, 054510.
Michele Benzi and Paola Boito, Matrix functions in network analysis, GAMM-Mitt. 43 (2020), no. 3, e202000012, 36. MR 4166335
Michele Benzi and Gene H. Golub, Bounds for the entries of matrix functions with applications to preconditioning, BIT 39 (1999), no. 3, 417–438. MR 1708693, DOI 10.1023/A:1022362401426
Michele Benzi and Michele Rinelli, Refined decay bounds on the entries of spectral projectors associated with sparse Hermitian matrices, Linear Algebra Appl. 647 (2022), 1–30. MR 4413324, DOI 10.1016/j.laa.2022.04.005
Michele Benzi, Michele Rinelli, and Igor Simunec, Computation of the von Neumann entropy of large matrices via trace estimators and rational Krylov methods, Numer. Math. 155 (2023), no. 3-4, 377–414. MR 4666428, DOI 10.1007/s00211-023-01368-6
Abraham Berman and Robert J. Plemmons, Nonnegative matrices in the mathematical sciences, Classics in Applied Mathematics, vol. 9, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1994. Revised reprint of the 1979 original. MR 1298430, DOI 10.1137/1.9781611971262
Samuel L. Braunstein, Sibasish Ghosh, and Simone Severini, The Laplacian of a graph as a density matrix: a basic combinatorial approach to separability of mixed states, Ann. Comb. 10 (2006), no. 3, 291–317. MR 2284272, DOI 10.1007/s00026-006-0289-3
Tyler Chen and Eric Hallman, Krylov-aware stochastic trace estimation, SIAM J. Matrix Anal. Appl. 44 (2023), no. 3, 1218–1244. MR 4629849, DOI 10.1137/22M1494257
Alice Cortinovis and Daniel Kressner, On randomized trace estimates for indefinite matrices with an application to determinants, Found. Comput. Math. 22 (2022), no. 3, 875–903. MR 4433116, DOI 10.1007/s10208-021-09525-9
Stephen Demko, William F. Moss, and Philip W. Smith, Decay rates for inverses of band matrices, Math. Comp. 43 (1984), no. 168, 491–499. MR 758197, DOI 10.1090/S0025-5718-1984-0758197-9
Ethan N. Epperly, Joel A. Tropp, and Robert J. Webber, XTrace: making the most of every sample in stochastic trace estimation, SIAM J. Matrix Anal. Appl. 45 (2024), no. 1, 1–23. MR 4683960, DOI 10.1137/23M1548323
Ernesto Estrada and Desmond J. Higham, Network properties revealed through matrix functions, SIAM Rev. 52 (2010), no. 4, 696–714. MR 2736969, DOI 10.1137/090761070
Miroslav Fiedler and Hans Schneider, Analytic functions of $M$-matrices and generalizations, Linear and Multilinear Algebra 13 (1983), no. 3, 185–201. MR 700883, DOI 10.1080/03081088308817519
Andreas Frommer, Mostafa Nasr Khalil, and Gustavo Ramirez-Hidalgo, A multilevel approach to variance reduction in the stochastic estimation of the trace of a matrix, SIAM J. Sci. Comput. 44 (2022), no. 4, A2536–A2556. MR 4469517, DOI 10.1137/21M1441894
Andreas Frommer, Claudia Schimmel, and Marcel Schweitzer, Bounds for the decay of the entries in inverses and Cauchy-Stieltjes functions of certain sparse, normal matrices, Numer. Linear Algebra Appl. 25 (2018), no. 4, e2131, 17. MR 3826933, DOI 10.1002/nla.2131
Andreas Frommer, Claudia Schimmel, and Marcel Schweitzer, Analysis of probing techniques for sparse approximation and trace estimation of decaying matrix functions, SIAM J. Matrix Anal. Appl. 42 (2021), no. 3, 1290–1318. MR 4301922, DOI 10.1137/20M1364461
Arjun Singh Gambhir, Andreas Stathopoulos, and Kostas Orginos, Deflation as a method of variance reduction for estimating the trace of a matrix inverse, SIAM J. Sci. Comput. 39 (2017), no. 2, A532–A558. MR 3632261, DOI 10.1137/16M1066361
Michael B. Giles, Multilevel Monte Carlo methods, Acta Numer. 24 (2015), 259–328. MR 3349310, DOI 10.1017/S096249291500001X
Didier A. Girard, A fast “Monte Carlo cross-validation” procedure for large least squares problems with noisy data, Numer. Math. 56 (1989), no. 1, 1–23. MR 1012701, DOI 10.1007/BF01395775
Alex Gittens and Michael W. Mahoney, Revisiting the Nyström method for improved large-scale machine learning, J. Mach. Learn. Res. 17 (2016), Paper No. 117, 65. MR 3543523
A. A. Hagberg, D. A. Schult, and P. J. Swart, Exploring network structure, dynamics, and function using NetworkX, Proceedings of the 7th Python in Science Conference (Pasadena, CA, USA) (G. Varoquaux, T. Vaught, and J. Millman, eds.), 2008, pp. 11–15.
Eric Hallman and Devon Troester, A multilevel approach to stochastic trace estimation, Linear Algebra Appl. 638 (2022), 125–149. MR 4357378, DOI 10.1016/j.laa.2021.12.010
I. Han, D. Malioutov, and J. Shin, Large-scale log-determinant computation through stochastic Chebyshev expansions, International Conference on Machine Learning, PMLR, 2015, pp. 908–917.
M. F. Hutchinson, A stochastic estimator of the trace of the influence matrix for Laplacian smoothing splines, Comm. Statist. Simulation Comput. 19 (1990), no. 2, 433–450. MR 1075456, DOI 10.1080/03610919008812864
Jesse Laeuchli and Andreas Stathopoulos, Extending hierarchical probing for computing the trace of matrix inverses, SIAM J. Sci. Comput. 42 (2020), no. 3, A1459–A1485. MR 4093597, DOI 10.1137/18M1176427
Xueliang Li, Yongtang Shi, and Ivan Gutman, Graph energy, Springer, New York, 2012. MR 2953171, DOI 10.1007/978-1-4614-4220-2
Raphael A. Meyer, Cameron Musco, Christopher Musco, and David P. Woodruff, Hutch++: optimal stochastic trace estimation, Symposium on Simplicity in Algorithms (SOSA), [Society for Industrial and Applied Mathematics (SIAM)], Philadelphia, PA, 2021, pp. 142–155. MR 4537958
C. Morningstar, J. Bulava, J. Foley, K. J. Juge, D. Lenkner, M. Peardon, and C. H. Wong, Improved stochastic estimation of quark propagation with Laplacian Heaviside smearing in lattice QCD, Phys. Rev. D 83 (2011), no. 11, 114505.
Mathew Penrose, Random geometric graphs, Oxford Studies in Probability, vol. 5, Oxford University Press, Oxford, 2003. MR 1986198, DOI 10.1093/acprof:oso/9780198506263.001.0001
David Persson, Alice Cortinovis, and Daniel Kressner, Improved variants of the Hutch++ algorithm for trace estimation, SIAM J. Matrix Anal. Appl. 43 (2022), no. 3, 1162–1185. MR 4451312, DOI 10.1137/21M1447623
Carl Edward Rasmussen and Christopher K. I. Williams, Gaussian processes for machine learning, Adaptive Computation and Machine Learning, MIT Press, Cambridge, MA, 2006. MR 2514435
Farbod Roosta-Khorasani and Uri Ascher, Improved bounds on sample size for implicit matrix trace estimators, Found. Comput. Math. 15 (2015), no. 5, 1187–1212. MR 3394708, DOI 10.1007/s10208-014-9220-1
C. Schimmel, Bounds for the decay in matrix functions and its exploitation in matrix computations, Ph.D. thesis, Bergische Universität Wuppertal, Wuppertal, Germany, 2019.
Marcel Schweitzer, Decay bounds for Bernstein functions of Hermitian matrices with applications to the fractional graph Laplacian, Electron. Trans. Numer. Anal. 55 (2022), 438–454. MR 4418423, DOI 10.1553/etna_{v}ol55s438
J. Sexton and D. Weingarten, Error estimate for the valence approximation and for a systematic expansion of full QCD, Phys. Rev. D 55 (1997), no. 7, 4025–4035.
Andreas Stathopoulos, Jesse Laeuchli, and Kostas Orginos, Hierarchical probing for estimating the trace of the matrix inverse on toroidal lattices, SIAM J. Sci. Comput. 35 (2013), no. 5, S299–S322. MR 3120774, DOI 10.1137/120881452
Jok M. Tang and Yousef Saad, A probing method for computing the diagonal of a matrix inverse, Numer. Linear Algebra Appl. 19 (2012), no. 3, 485–501. MR 2911385, DOI 10.1002/nla.779
C. Thron, S. J. Dong, K. F. Liu, and H. P. Ying, Padé-$Z_2$ estimator of determinants, Phys. Rev. D 57 (1998), no. 3, 1642.
S. Ubaru and Y. Saad, Applications of Trace Estimation Techniques, High Performance Computing in Science and Engineering: Third International Conference, HPCSE 2017, Karolinka, Czech Republic, May 22–25, 2017, Revised Selected Papers, Springer, 2018, pp. 19–33.
T. Whyte, A. Stathopoulos, E. Romero, and K. Orginos, Optimizing shift selection in multilevel Monte Carlo for disconnected diagrams in lattice QCD, Comput. Phys. Commun. 294 (2024), 108928.
Karl Wimmer, Yi Wu, and Peng Zhang, Optimal query complexity for estimating the trace of a matrix, Automata, languages, and programming. Part I, Lecture Notes in Comput. Sci., vol. 8572, Springer, Heidelberg, 2014, pp. 1051–1062. MR 3238692, DOI 10.1007/978-3-662-43948-7_{8}7