Hutchinson's estimator — where it appears
Named by 9 essays across one field — each of them below, with the objects they name alongside it.
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.
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.
The split nobody is in a position to choose
Hutch++ spends two thirds of its budget on a sketch and a third on probes, and the third is published as a constant. Swept across six rates of spectral decay at a fixed budget of 48 products, the best share is 0.45 on the fastest and 0.00 on the slowest — sketch nothing at all — and the published third costs between 1.09 and 4.11 times the best error. The decay that decides it is readable from the sketch's own singular values, for products the estimator was going to spend anyway.
A rule that reads only its own probes
A trace estimator is a mean of independent samples, so its own standard error is estimable from the samples and a stopping rule needs nothing the estimator does not already have. Over forty draws it is calibrated in the middle and not at the edge: at a target relative standard error of 1% the median error reached is 5.3·10⁻³ and the worst of forty is 2.9·10⁻² — three times the target. And the cost of the target is the estimator's own square root: tightening it from 3% to 1% takes the median probe count from 75 to 696.
The miss a normal table already priced
A trace estimator that stops when its own standard error reaches a target misses the target on about a third of draws, and the essay that measured it read the loose targets as the worst calibrated. Over 400 draws the loose target is the better covered — 76% at 10% against 64% at 3% — because the warm-up stops most of its runs with probes to spare. Where the criterion decides, the misses are a normal distribution's: a margin of c on the standard error buys what a normal table says, 94.8% at 1.96, and costs c² in probes, 3.86 times.
A spread measured on probes it does not average
A trace estimator that stops on its own standard error misses its target a few points more often than a normal table says, because the runs that stop earliest are the ones that underestimated their noise. Spend a pilot of probes only on the spread, fix the number of probes to average in advance, and the selection is gone: with Student's margin the two-stage rule covers 64.8 to 73.3 per cent at one standard error where the table says 68.3. With the normal's margin and a pilot of four it covers 58.5. At one standard error it recovers one to five points for a fifth to two fifths more probes; at 1.96 there was nothing to recover, and the guarantee costs a tenth to double.
A spread carried from the trace before
A two-stage trace estimator spends a pilot of probes learning its spread, and a computation that needs many traces of a slowly changing operator would rather pay for that once. Frozen at the first trace, the pilot is wrong by the sixteenth: on a spectrum that drifts from decay 0.9 to 0.86 the last estimate is inside a 3% target 52 times in a hundred against the table's 68, and at a faster drift 34. Carry instead the spread of the previous trace's own averaged probes — free, independent of this trace's, one step stale — and its sixteenth estimate covers between 64.5 and 69.5 per cent at every drift, for up to a quarter fewer products than a fresh pilot every time.
A drift put back at the table's price
A trace estimator that carries its spread from the trace before loses one step of drift, and the drift is visible in the spreads themselves, so the repair proposed was to multiply the carried spread by the ratio of the last two. Over 400 drifting sequences it works: averaged over the third to sixteenth traces it covers 67.8 to 68.9 per cent at one standard error at every drift, where the plain carry falls to 65.4 and the table says 68.3. It costs what the table says closing that gap costs — 10.5 per cent more products at the fastest drift against a price of 11.9 — so at that drift it spends more than a fresh pilot every trace. Its factor is noisy, scattering the spread it uses two and a half times as widely as the plain carry does, and on a sequence that does not drift that noise costs nothing at all. And the single-trace comparison the proposal named turned out to be smaller than its own draw noise.
A turn is seen one trace late
A carried spread multiplied by the ratio of the last two spreads restored a drifting sequence's coverage, and the prediction for a sequence whose drift turns was a dip of four or five points on the trace after the turn, gone a trace later, and a guard that removes it for nothing. Run on the turn the prediction described — the spread rising and then falling — there is no dip: the extrapolation promises more rise, uses a spread eleven per cent too large, and covers 70.5 per cent against a table of 68.3. Run on the mirror turn, the spread falling and then rising, the dip is there and larger than predicted: a spread a quarter too small and 59.5 per cent coverage. Either way it is gone a trace later and the sequence's average stays within a point. The guard costs nothing and does not help, because no rule that reads past spreads can see a turn before the trace that shows it.
Named alongside it
The objects these essays reach for when they reach for this one.
Probabilistic boundsSpectral decayTrace estimationMatrix-freeRandom probeStopping criterionFlop countDeflationExact ground truthRandom projectionCancellationFrobenius norm