Randomized algorithms to estimate the trace and determinant of a matrix

Abstract: Our present work is motivated by the need for estimating uncertainty measures in Bayesian inverse problems - which involves computing the trace and determinant of an implicit matrix. Monte Carlo-based methods, which are prevalent in practice, may require many samples to accurately estimate the trace. I will describe new randomized estimators based on subspace iteration to approximate the trace and determinant. Our analysis has two components: (1) structural, which is applicable to any valid distribution, and (2) probabilistic, which is applicable to Gaussian and Rademacher sampling matrices. We demonstrate the performance of our bounds on several test matrices and a challenging application in optimal experimental design.