Two trace estimators against their budget, on a 80×80 matrix whose spectrum decays at 0.85
At its defaults it draws two trace estimators against their budget, on a 80×80 matrix whose spectrum decays at 0.85. Two curves of relative error against the number of products with A, both axes logarithmic, as medians over 32 seeds. Hutchinson's fitted exponent is -0.54 and Hutch++'s is -2.55. The deflation changes the exponent rather than the constant, which is what makes it worth two thirds of the budget.
trace-rate is one function in lib/figures/trace.js —
counting the diagonal without looking — two probes, and one of them is free. Everything below came out of it during this build, at
arguments taken from the essays rather than invented for this page. A figure here is the
figure a reader meets in an essay, and if the generator changes, this page changes with it.
At its defaults
Drawn even though every essay passes arguments — which on this site is every essay, at 100% of placements since the standard pass. A default nothing exercises is a trap for the next essay to call this with none, and this is the page where a default that has drifted from the figures around it becomes visible.
Two curves of relative error against the number of products with A, both axes logarithmic, as medians over 32 seeds. Hutchinson's fitted exponent is -0.54 and Hutch++'s is -2.55. The deflation changes the exponent rather than the constant, which is what makes it worth two thirds of the budget.
decay: 0.9
The arguments are the ones A rate that belongs to the matrix passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
Two curves of relative error against the number of products with A, both axes logarithmic, as medians over 32 seeds. Hutchinson's fitted exponent is -0.50 and Hutch++'s is -1.65. The deflation changes the exponent rather than the constant, which is what makes it worth two thirds of the budget.
decay: 0.85
The arguments are the ones A rate that belongs to the matrix passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
Two curves of relative error against the number of products with A, both axes logarithmic, as medians over 32 seeds. Hutchinson's fitted exponent is -0.54 and Hutch++'s is -2.55. The deflation changes the exponent rather than the constant, which is what makes it worth two thirds of the budget.
decay: 0.6
The arguments are the ones A rate that belongs to the matrix passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
Two curves of relative error against the number of products with A, both axes logarithmic, as medians over 32 seeds. Hutchinson's fitted exponent is -0.28 and Hutch++'s is -7.15. The deflation changes the exponent rather than the constant, which is what makes it worth two thirds of the budget.
decay: 0.75
The arguments are the ones A rate that belongs to the matrix passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
Two curves of relative error against the number of products with A, both axes logarithmic, as medians over 32 seeds. Hutchinson's fitted exponent is -0.36 and Hutch++'s is -4.09. The deflation changes the exponent rather than the constant, which is what makes it worth two thirds of the budget.
decay: 0.95
The arguments are the ones A rate that belongs to the matrix passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
Two curves of relative error against the number of products with A, both axes logarithmic, as medians over 32 seeds. Hutchinson's fitted exponent is -0.50 and Hutch++'s is -1.03. The deflation changes the exponent rather than the constant, which is what makes it worth two thirds of the budget.
What it checked while drawing
Every figure above checked its own claims on the way to being drawn, and a claim that failed
would have stopped the picture rather than shipped a wrong one. Those checks used to leave
no trace at all: a passing one returned true and the only evidence the figure had
checked anything was that nothing crashed. The list below is what they actually said, collected
by running this generator with an observer installed — not a description of
what it is believed to check.
58 distinct claims across 6 sets of arguments, grouped below by shape — because most of them are one sentence with a different number in it, and how many separate times that sentence was put to the test is the informative part.
a margin of 1 costs its square at decay 0.8, 3% — checked 8 times
the best share does not rise as the reading does, at decay 0.8 — checked 5 times
sitting above it at every budget, at s = 12 — checked 4 times
a longer warm-up covers more at decay 0.8 — checked 3 times
and the worst draw is outside the target of 0.1 — checked 3 times
no run hits the probe cap at a target of 0.1 — checked 3 times
the loose target covers at least the tight one at 0.8 — checked 3 times
a budget large enough for every split to buy something
a decay rate between everything and nothing
a decay the margin studies draw
a decay the margin sweep measured
a drift the sequence is run at
a drift the stale pilot is measured along
a faster decay wants more of the budget in the sketch
a margin the drift sweep is run at
a pilot with at least one degree of freedom
a relative standard error a run could reach
a sequence whose decay stays a decay
a share of the budget the sketch can have
a size the repeated sweeps can afford
a trace-rate view this figure draws
and Hutch++ does NOT change the exponent when there is nothing to deflate
and Hutch++ falls faster on a spectrum that decays
and the published third costs a real factor somewhere
and where the warm-up binds the first probes are free
and where the warm-up decides, the tail is heavier
at an exponent past one
deflation reaches the tightest target for fewer products
enough seeds for a median
Hutchinson falls like one over the square root of the budget
matmul shapes agree
reaching a smaller error at the largest budget
the reading spans a factor of several across the decays
the spectrum leaves a trace worth estimating
where the criterion decides, coverage sits on the normal table
where the criterion decides, the 95th percentile of the error in standard errors is a normal's
Against the rule
It draws a decomposition and prints its residual. It calls
hutchPP,
and every figure above carries the badge — which residualcheck verifies by looking
for it in the emitted SVG rather than by finding the call that builds one. A badge that is
constructed and then left out of the body is the failure that check exists for.
Across the library: the rule bites on 217
of 397 generators —
199 print a residual and
18 are exempt with a published reason;
180 factorise nothing.
Read from lib/residual-rule.js, which is the same body the gate enforces from,
and the gate's last check fails the build if this page and it disagree about any generator.
Where it is called
Changing this generator changes every figure on this list. That is what makes the list worth publishing rather than keeping in a check script.
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, and the guarantee that changes kindA 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.
Randomised, and the guarantee that changes kindA 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.
Randomised, and the guarantee that changes kindA 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.
Randomised, and the guarantee that changes kindCounting 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, and the guarantee that changes kindThe 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.
Randomised, and the guarantee that changes kindThe 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.