Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Trace estimation — where it appears

Computing the trace of a matrix that is never formed, by averaging quadratic forms against random probes. The variance depends on the distribution the probes are drawn from rather than on the matrix, which makes that choice a decision rather than a detail.

Named by 11 essays across 3 fields — each of them below, with the objects they name alongside it.

κ of the suma component of b − Ax1.01·10¹⁷ad − bc, near-degenerate3.6·10¹⁶qᵢᵀqⱼ, an orthogonality check7.39·10¹⁵pᵀAp, a curvature409zᵀAz, a trace probe41.8rᵀr, a residual norm1measured, not assumedhighest10¹⁷lowest1above 10¹⁰3terms64sums of squares are safeand nobody decides anything from one

The vector that hides it

Every quick demonstration of a parallel sum uses positive numbers, and positive numbers are the one family where the effect is absent. Measured on six inner products this site already computes, the summation condition number runs from exactly 1 to 10¹⁷ — and the safe end is where nobody makes a decision.

machine · Summation 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 11.31.61.92.210⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹10²log₁₀ quadrature pointsdistance from the true counthalf an eigenvaluean integer, eventuallytrue count2at 4 points2at 128 points2finest error1.4·10⁻¹³the integral is an integerand a rounding hides how far it was

The last digit is the cheapest

Every cost curve measured here has the same shape: the first digits are cheap and the last ones are not. One method inverts it. Doubling the work buys twice as many digits as the previous doubling did, so the price of a digit halves every time it is paid.

cost · Nonlinear cost 11.31.61.92.210⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹10²log₁₀ quadrature pointsdistance from the true counthalf an eigenvaluean integer, eventuallytrue count2at 4 points2at 128 points2finest error1.4·10⁻¹³the integral is an integerand a rounding hides how far it was

Counting what is inside a circle

A trace of a matrix nobody wants to form, integrated around a contour, gives an integer — how many eigenvalues are inside. It converges exponentially, it is estimated with random probes, and the probe block is a ceiling that the answer does not mention.

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 48 products, 24 drawsbest share, decay 0.70.45best share, decay 0.950.2worst cost of a third2.800.10.20.30.410⁻³10⁻²10⁻¹share spent on the sketchmedian relative errorthe published thirddecay 0.7decay 0.85decay 0.95large dots: the best split on each curveand the dashed line is the one a library picks

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.

randomised · Trace estimation 40 drawsproducts at target 0.01696deflated277draws inside the target0.810⁻²10⁻¹10⁻²10⁻¹target standard errorrelative error reachedworst draw, no deflationmedian error, no deflationmedian error, deflatedthe grey diagonal is a calibrated rulethe medians are on it and the worst draws are not

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.

randomised · Trace estimation decay 0.8, 400 draws3% target, c = 10.663% target, c = 1.960.9410% target, c = 10.6611.251.51.7522.252.5556065707580859095100margin c on the standard errordraws inside the target, %3% target10% targeta normal tablethe dashed curve is 2Φ(c) − 1what a margin of c promises if the error is normal

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.

randomised · Trace estimation points of coveragegain at c = 1, fast decays, best5.3worst0.750.811.21.41.61.822.22.42.6-30-20-10010products ÷ the sequential rule'scoverage gained, pointsdecay 0.8decay 0.9decay 0.97dashed: no gaina few points, bought with a fifth to double the probes

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.

randomised · Trace estimation sixteenth trace, c = 1, %a new pilot every trace, fastest drift63the first pilot, frozen, fastest drift34the last trace's probes, carried, fastest drift65304050607080decay lost per traceestimates inside the target, %00.0050.010.02a new pilot every tracethe first pilot, frozenthe last trace's probes, carrieddashed: the normal tablea frozen spread fails; a carried one holds

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.

randomised · Trace estimation traces 3 to 16, %a new pilot every trace, fastest66the last trace's spread, fastest66times the last ratio, fastest69times a four-trace trend, fastest6962646668707274decay lost per traceestimates inside the target, %00.0050.010.02a new pilot every tracethe last trace's spreadtimes the last ratiotimes a four-trace trenddashed: the normal tableone ratio puts the drift back

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.

randomised · Trace estimation

Named alongside it

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

Hutchinson's estimatorMatrix-freeProbabilistic boundsSpectral decayRandom probeStopping criterionFlop countDeflationExact ground truthRandom projectionCancellationContour integral

All concepts