randomized-trace-logdet-diag-diaginv

Some Python implementations of randomized, matrix-free algorithms for estimating $\text{tr}(A)$, $\log \det(A)$, $\text{diag}(A)$, and $\text{diag}(A^{-1})$. Here $A$ is SPD or SPSD. We also provide implementations of non-randomized methods requiring access to matrices for convenience.

This package is a work-in-progress. The goal is to implement some of the algorithms detailed in the references below.

References

[1] M.F. Hutchinson (1989). A Stochastic Estimator of the Trace of the Influence Matrix for Laplacian Smoothing Splines. Communications in Statistics - Simulation and Computation, 18(3), 1059-1076.

[2] Avron, H., & Toledo, S. (2011). Randomized Algorithms for Estimating the Trace of an Implicit Symmetric Positive Semi-Definite Matrix. J. ACM, 58(2).

[3] Roosta-Khorasani, F., & Ascher, U. (2015). Improved Bounds on Sample Size for Implicit Matrix Trace Estimators. Foundations of Computational Mathematics, 15(5), 1187–1212.

[4] Saibaba, A., Alexanderian, A., & Ipsen, I. (2017). Randomized matrix-free trace and log-determinant estimators. Numerische Mathematik, 137(2), 353–395.

[5] C. Bekas, E. Kokiopoulou, & Y. Saad (2007). An estimator for the diagonal of a matrix. Applied Numerical Mathematics, 57(11), 1214-1229.

[6] Christos Boutsidis, Petros Drineas, Prabhanjan Kambadur, Eugenia-Maria Kontopoulou, & Anastasios Zouzias (2017). A randomized algorithm for approximating the log determinant of a symmetric positive definite matrix. Linear Algebra and its Applications, 533, 95-117.

[7] Han, I., Malioutov, D.M., & Shin, J. (2015). Large-scale log-determinant computation through stochastic Chebyshev expansions. International Conference on Machine Learning.

[8] Chen, J. (2016). How Accurately Should I Compute Implicit Matrix-Vector Products When Applying the Hutchinson Trace Estimator? SIAM J. Sci. Comput., 38.

[9] Meyer, R.A., Musco, C., Musco, C., & Woodruff, D.P. (2020). Hutch++: Optimal Stochastic Trace Estimation. Proceedings of the SIAM Symposium on Simplicity in Algorithms, 2021, 142-155 .

[10] Persson, D., Cortinovis, A., & Kressner, D. (2021). Improved variants of the Hutch++ algorithm for trace estimation. SIAM J. Matrix Anal. Appl., 43, 1162-1185.