  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.
