Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Hutchinson's estimator — where it appears

The average of zᵀAz over random probes whose entries have mean zero and unit variance, which equals the trace in expectation for every matrix. It is unbiased with no assumption at all, and its entire cost is variance: one probe's variance is twice the squared Frobenius norm less whatever the probe distribution happens to account for exactly.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

1112131415193111.365129.731148.096166.461probes takenrunning estimate of the tracenormal±1one probe, no errorthe exact trace99±1 variance, this matrix0±1 variance, rotated57normal variance545the same spectrum in a general basiscosts the ±1 probe its whole advantage

Counting what cannot be looked at

The trace is n additions and one of the most expensive quantities in the subject to estimate, because the matrices whose trace is wanted are never stored. Hutchinson's estimator is unbiased with one line of algebra — and its variance depends on which random vector is used, by a factor that is a property of the matrix, and on a diagonal matrix one choice is exact from the first probe and the other is not.

randomised · Trace estimation 10¹10²10⁻⁴10⁻³10⁻²10⁻¹1products with Arelative errorHutchinsonHutch++measured at equal costfitted rate, Hutchinson-0.5fitted rate, Hutch++-1.7error at 96, Hutchinson0.017error at 96, Hutch++0.0022both axes count products with Aso the sketch is paid for in the picture

A rate that belongs to the matrix

Hutchinson's fitted exponent sits near a half on every spectrum measured. Hutch++'s runs from −7.15 to −0.67 across the same four budgets, decided entirely by how fast the singular values fall — so one of the two methods has a convergence rate and the other has a rate per matrix. The ±1 probe's advantage moves the same way, from 1.56× at n = 10 to 1.09× at n = 120.

randomised · Trace estimation

Named alongside it

The objects these essays reach for when they reach for this one.

Matrix-freeProbabilistic boundsRandom projectionSpectral decayTrace estimationCancellationDeflationFrobenius normGeneralised cross-validationInfluence matrix

All concepts