  Given a real symmetric positive semi-definite matrix E, and an approximation
S that is a sum of n independent matrix-valued random variables, we present
bounds on the relative error in S due to randomization. The bounds do not
depend on the matrix dimensions but only on the numerical rank (intrinsic
dimension) of E. Our approach resembles the low-rank approximation of kernel
matrices from random features, but our accuracy measures are more stringent.
  In the context of parameter selection based on active subspaces, where S is
computed via Monte Carlo sampling, we present a bound on the number of samples
so that with high probability the angle between the dominant subspaces of E and
S is less than a user-specified tolerance. This is a substantial improvement
over existing work, as it is a non-asymptotic and fully explicit bound on the
sampling amount n, and it allows the user to tune the success probability. It
also suggests that Monte Carlo sampling can be efficient in the presence of
many parameters, as long as the underlying function f is sufficiently smooth.
