Randomized Matrix-free Trace and Log-Determinant Estimators
Provides theoretically grounded, matrix-free estimators for trace and log-determinant, benefiting large-scale linear algebra and uncertainty quantification.
The paper introduces randomized algorithms for estimating the trace and log-determinant of Hermitian positive semi-definite matrices using only matrix-vector products, with non-asymptotic error bounds. Numerical experiments demonstrate performance on low-dimensional matrices and a Bayesian optimal experimental design application.
We present randomized algorithms for estimating the trace and deter- minant of Hermitian positive semi-definite matrices. The algorithms are based on subspace iteration, and access the matrix only through matrix vector products. We analyse the error due to randomization, for starting guesses whose elements are Gaussian or Rademacher random variables. The analysis is cleanly separated into a structural (deterministic) part followed by a probabilistic part. Our absolute bounds for the expectation and concentration of the estimators are non-asymptotic and informative even for matrices of low dimension. For the trace estimators, we also present asymptotic bounds on the number of samples (columns of the starting guess) required to achieve a user-specified relative error. Numerical experiments illustrate the performance of the estimators and the tightness of the bounds on low-dimensional matrices; and on a challenging application in uncertainty quantification arising from Bayesian optimal experimental design.