of the $U_j$’s have mean 0 and variance 1; but, subject to this constraint, @hutchinson shows that, assuming the components of the $U_j$’s are independent, taking them to be symmetric Bernoulli minimizes the variance of $U_1'MU_1$ for any $n\times n$ matrix $M$. The Hutchinson trace estimator has also been used to approximate the GCV (generalized cross-validation) statistic in nonparametric regression \[@girard [@wahba]\]. In particular, @girard shows that $N$ does not need to be large to obtain a randomized GCV that yields results nearly identical to those obtained using exact GCV.

Suppose for now that it is possible to take $N$ much smaller than $n$ and obtain an estimate of $\theta$ that is nearly as efficient statistically as the exact MLE. From here on, assume that any solves in $K$ will be done using iterative methods. In this case, the computational effort to computing (\[score\]) or (\[ascore\]) is roughly linear in the number of solves required (although see Section \[sec4\] for methods that make $N$ solves for a common matrix $K$ somewhat less than $N$ times the effort of one solve), so that (\[ascore\]) is much easier to compute than (\[score\]) when $N/n$ is small. An attractive feature of the approximation 