Trace estimators and impact factors - Biased and Inefficient

For a Secret Project™, I needed a quick estimator of the trace of a matrix. To be precise, I have a rectangular matrix $A$ and I needed $t r (B)$ and $t r (B^{2})$ where $B = A^{T} A$ . That sounds easy, but $A$ is big enough that you don’t want to compute $A^{T} A$ .

The first one actually is easy: $t r (B) = \sum_{i j} (A_{i j})^{2} .$ The second one is harder. I tried a sampling approach: estimating a sample of the entries of $B$ and using $t r (B^{2}) = \sum_{i j} (B_{i j})^{2} .$ The performance was not great, even when I tried stratified sampling – getting all the diagonal entries of $B$ and a random sample of the off-diagonal entries.

I should have Googled before thinking, rather than after thinking. There is a standard solution: Hutchinson’s randomised trace estimator. If $z$ is a vector whose entries are independent, mean zero, unit variance, then $E [z^{T} B z] = t r (B) .$
So, if you have $k$ random vectors $z_{1}, \dots, z_{k}$ , a trace estimator is
$\hat{t r} (B^{2}) = \frac{1}{k} \sum_{i} z_{i}^{T} B^{2} z_{i} = \frac{1}{k} \sum_{i} z_{i} A^{T} A A^{T} A z_{i} = \frac{1}{k} \sum_{i} {‖ A^{T} A z_{i} ‖}_{2}^{2}$

Hutchinson used Rademacher (random $\pm 1$ ) variables for the entries of $z$ . You could also use standard Normals and it wouldn’t make much difference – it would affect what theoretical tools you could use to get tail bounds. There’s a slight benefit in having the $z_{i}$ be uncorrelated, so in one application where it was convenient I used vectors $A z$ produced by the subsampled randomised Hadamard transform, but when $A$ is sparse and that isn’t convenient I just used standard Normals. You don’t get high accuracy – the central limit theorem says the error is of order $k^{- 1 / 2}$ – but you get a reasonable estimator quickly.

The Hutchinson trace estimator has also been influential in thinking about degrees of freedom for semiparametric smoothers, as Grace Wahba mentions in her chapter of “Past, Present, Future of Statistical Science”.

Since I knew $t r (B)$ I could improve on the Hutchinson estimator by ratio estimation from survey sampling. If you estimate $t r (B)$ using the same $z$ , a better estimator of $t r (B^{2})$ is
${\hat{t r}}_{r a t i o} (B^{2}) = \hat{t r} (B^{2}) \frac{t r (B)}{{t r}^{^} (B)}$
The sampling errors in the two estimators are correlated, so the error in the ratio is smaller – by about 50% in my case.

So, impact factors? Hutchinson’s paper “A stochastic estimator of the trace of the influence matrix for laplacian smoothing splines” is in the journal ‘Communications in Statistics - Simulation and Computation’, well known for not being especially picky or well read. It still has quite a few gems, such as Hutchinson’s paper and Pepe & Anderson’s paper about conditioning on $X$ at all times or just the current time in longitudinal data analysis. “This paper is crap because it’s in a crap journal” has the same form as the classical argumentum ad hominem. It saves effort, but it’s still a fallacy.