Speaker:  Fred Roosta, Department of Computer Science, University of British Columbia

Location:  ESB 4133

Intended Audience:  Public

This talk is concerned with Monte-Carlo methods for the estimation of the trace of an implicitly given matrix A, where the matrix information is only available through matrix-vector products. The need to estimate the trace of implicit matrices arises in many applications, where often A is symmetric positive semi-definite (SPSD). Thus, theoretical studies of accuracy and efficiency of these methods are very important. In order to set the scene, we initially present an application of such trace estimators which involves efficient stochastic methods for solving PDE-constrained inverse problems with many measurements.

The standard approach for estimating the trace of an implicit matrix involves averaging the quadratic forms of A with random vector realizations from a suitable probability distribution. We demonstrate the success of such stochastic methods in reducing the computational complexity of large scale inverse problems. We then derive new and improved theoretical results bounding the number of matrix-vector products required in order to guarantee a probabilistic bound on the relative error of the trace estimation. Bounds are derived for Rademacher (Hutchinson), Gaussian and uniform unit vector (with and without replacement) probability distributions. They provide some guidance in deciding which distribution to employ for a given application.