The split nobody is in a position to choose

A rate that belongs to the matrix found Hutchinson’s estimator with a convergence rate and Hutch++ with a rate per matrix. Hutchinson’s fitted exponent sits near a half on every spectrum measured — the central limit theorem, and nothing else; Hutch++'s runs from −7.15 to −0.67 across the same four budgets, decided entirely by how fast the singular values fall.

A quantity decided by the spectrum has a knob, and Hutch++ has one. Its budget is divided between a sketch, which costs two matrix–vector products per column — one to form AS and one to form AQ — and probes on the deflated remainder, which cost one each. The published algorithm takes a third of the budget as sketch columns, which spends two thirds of the products on deflation and leaves a third for the probes.

The third is a constant in every implementation. The rate it produces is not.

The split swept #

One draw in twenty is the standing warning about reading a median as a rule’s behaviour, and the last section here says why it does not bite. Sixty by sixty, eigenvalues decaying geometrically, a budget of 48 products, twenty-four draws of the probe stream at each split, and the error measured against a trace that is known because the spectrum was prescribed.

At a decay of 0.7 per eigenvalue the error falls monotonically as the sketch grows: 7.0·10⁻², 3.3·10⁻², 6.5·10⁻³, 5.9·10⁻⁴ and 2.1·10⁻⁴ at shares of 0, 0.1, 0.2, 1/3 and 0.45. The best split available is the largest, and the published third costs 2.83 times the best.

At 0.95 the shape inverts. Shares of 0, 0.1, 0.2, 1/3 and 0.45 give 1.7·10⁻², 2.1·10⁻², 9.7·10⁻³, 2.0·10⁻² and 2.6·10⁻². The best is 0.20, the third costs 2.07 times it, and the third is worse than sketching nothing at all — 1.7·10⁻² for plain Hutchinson against 2.0·10⁻² for Hutch++ at its published split.

Across six decay rates at the same budget, the third’s penalty is 4.11, 1.57, 1.31, 1.09, 2.07 and 3.05 as the decay goes from 0.7 to 0.99. It is a compromise in the exact sense: worst at both ends and nearly right in the middle.

One detail of the implementation had to change before the sweep was possible, and it is worth recording because it is the kind of thing that makes a knob invisible. The routine computed its sketch size as floor(budget / 3) with the three written into the expression. A share of zero — meaning do not sketch at all — was not merely unreachable; it was not expressible, because the floor is taken of a quotient whose denominator is a literal. So the question “what does the split cost” could not be asked of the method as implemented, which is the ordinary condition of a constant that nobody has swept.

It also needed a special case at zero. With no sketch the projection onto the orthogonal complement is the identity, and a routine that takes max(1, ...) sketch columns would spend two products on a rank-one deflation nobody asked for — so a share of zero returns plain Hutchinson on the whole budget rather than Hutch++ with one column. That is the honest zero and it is what the leftmost point of every curve is.

Which way it goes, and why #

The direction is not a surprise once the two halves are separated.

The sketch’s job is to capture a subspace the trace mostly lives in, and tr(QᵀAQ) over that subspace is computed exactly — no variance at all. What is left for the probes is the trace of the deflated matrix, whose Frobenius norm is what Hutchinson’s variance is proportional to. So every sketch column moves some of the answer from the noisy half to the exact half, and the question is how much it moves per product spent.

On a fast decay it moves a great deal: the k-th sketch column captures a direction whose eigenvalue is 0.7^k of the first, and the remainder’s Frobenius norm falls geometrically. On a slow decay it moves almost nothing — the remainder after k directions is nearly as large as the whole — and the two products it cost would each have been a probe.

Hutch++ buys nothing on a flat spectrum is the limiting case of that argument and was measured in the earlier measurement. What the sweep adds is that the limit is approached from inside the useful range: at a decay of 0.99 the deflation is already a net loss at the published split, and at 0.95 it is a net gain only if the split is cut nearly in half.

There is a second way to see the crossover and it is a count rather than an argument. A sketch of k columns costs 2k products and leaves budget − 2k probes. Hutchinson’s error on the remainder falls like its Frobenius norm over the square root of the probe count, so the error is roughly $\|A_k\|_F / \sqrt{\text{budget} - 2k}$, where $A_k$ is what is left after deflating k directions.

On a geometric spectrum $\|A_k\|_F$ falls like the decay raised to $k$, so the numerator falls geometrically in $k$ and the denominator falls like the square root of a linear function of $k$. A geometric beats a square root at every rate, so on a fast decay the expression is minimised at the largest k the budget allows — which is what the 0.45 is. As the decay approaches one the numerator stops falling, the denominator’s decrease is all that is left, and the minimum moves to k = 0.

The crossover is where the decay raised to $k$ stops beating $(\text{budget} - 2k)^{-1/2}$ over the range of $k$ available, which depends on both the decay and the budget — and the measurement says the budget dependence is weak over a factor of two, which the expression also predicts, since doubling the budget scales both terms.

The number is readable #

Counting what is inside a circle is the other estimator in these essays with two budgets to divide, and it divides them by a different mechanism. Which would be an unhelpful finding on its own, because the decay is a property of a matrix nobody can look at — that is the premise of this whole field. A trace is estimated rather than computed because the matrix is never formed.

The sketch reads it. After k columns the estimator holds Y = AS, an n-by-k matrix, and Y’s own singular values estimate A’s leading ones — that is what a randomised range finder is for. So the ratio of the last to the first singular value of the sketch is a one-number reading of how fast the spectrum falls, and it costs products the estimator has already spent.

Measured on a six-column sketch across the same six spectra, the reading is 0.094, 0.172, 0.223, 0.282, 0.397 and 0.580 — monotone in the decay, spanning a factor of 6.2. The best share over the same six is 0.45, 0.45, 0.45, 0.25, 0.20 and 0.00 — monotone the other way.

So the two are ordered together, and a rule is available: spend six products on a sketch, read the ratio, and decide how many more to buy. That is not a rule this essay fits or validates — six spectra from one family is not a calibration — but it is a rule with the right inputs, and the inputs are free.

What an adaptive estimator would look like #

The construction the sweep implies is a two-phase one and its cost is worth stating because it is not free.

Spend a small sketch — six columns, twelve products. Read the ratio. If it is small, the spectrum falls fast: buy more sketch columns up to something like 0.45 of the budget, leaving a tenth for probes. If it is large, stop sketching and spend the remainder on probes, which is plain Hutchinson with twelve products already gone.

That last case is where the adaptivity costs something. Twelve products spent on a sketch that turns out not to be worth having is twelve probes not taken, which on a 48-product budget is a quarter of it. At a decay of 0.99 the sweep says plain Hutchinson with 48 probes reaches 5.8·10⁻³ and the adaptive version would have 36, so it would reach about 5.8·10⁻³ times $\sqrt{48/36}$, or 6.7·10⁻³ — a 16 per cent penalty for finding out.

Against a 3.05-times penalty for guessing wrong, 16 per cent is cheap. Against the 1.09 the third costs in the middle of the range, it is not: an adaptive rule on a spectrum whose decay happens to be 0.9 does worse than the constant it replaced.

So the honest recommendation is conditional and the condition is about what is known. A code estimating traces of one matrix family repeatedly should measure the decay once and fix the split. A code handed an arbitrary operator should read it, and accept the sixteen per cent.

Counting what cannot be looked at is where these essays’ economics were first set out — 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 — and the split is the same economics one level in. Every product is the same price, the two halves of the estimator buy different things with it, and what each buys depends on a property of the operator that the estimator exists because nobody can see.

What must fail for any of this to be wrong #

That the best split at a decay of 0.7 is larger than the best split at 0.95, which is the direction the mechanism predicts and is the claim a constant denies. That the published third costs more than 1.3 times the best somewhere in the range. That the reading rises with the decay at every step and spans a factor of several. And that the best share never rises as the reading does, which is the monotonicity a rule would be built on.

The refusal is fed the claim that a third is within 1.2 times the best at every decay, and fails at 0.7 where it is 4.11 times.

What a published constant is for #

It is worth being fair to the third, because a paper’s constant is not a claim of optimality and this essay reads like an accusation if that is not said.

The third is the value at which the two halves of Hutch++'s error bound balance, under the assumption that the matrix’s spectrum is arbitrary. The theorem it comes with is a guarantee that holds for every positive semi-definite matrix, and a guarantee for every matrix is a statement about the worst one — so the constant is chosen against an adversary rather than against any particular spectrum. Under that reading it is exactly right and this sweep measures something else: what it costs on spectra that are not adversarial.

The distinction matters because the two readings recommend different things. A worst-case constant is what a library should ship when it knows nothing, and the sweep’s own figure says why: the third’s penalty is 1.09 at the middle of the range, so on a spectrum drawn at random from somewhere in it the constant is nearly free. What the sweep refuses is the stronger reading — that the third is the split, that the deflation is what the method’s advantage comes from, and that the division between them is a detail of the implementation rather than a parameter.

Four knobs and one floor is the general form of the same confusion in the regularisation field: a method’s parameter and a method’s identity are different things, and a parameter published as a constant is still a parameter. The measurement here is the parameter’s sweep, and its most useful single number is 3.05 — what the constant costs where it is worst, which is where the deflation should not have happened at all.

What this does not settle #

One matrix family: symmetric, a prescribed geometric spectrum, a random orthogonal basis. Real operators whose traces are wanted — a log-determinant’s, a Hessian’s, an influence matrix’s — have spectra that are not geometric and are sometimes not decaying at all.

One budget for the sweep, 48 products, with a check at 96. The claim that the split does not move with the budget is based on two budgets.

Twenty-four draws a cell, and the reported number is the median. The 90th percentile is computed and not drawn; the error’s distribution over draws is wide enough that a single run’s outcome says little, which is the standing condition of everything in these essays.

And the reading is one statistic of the sketch — the ratio of its last singular value to its first. The whole spectrum of the sketch is available for the same products and a better statistic may be in it; nothing here searches for one.

Why the median rather than the mean #

Every number above is a median over twenty-four draws, and the choice is not cosmetic.

A Hutchinson estimate’s error is |mean of t samples − truth|, whose distribution is a folded near-normal with a heavy-ish tail at small t. Its mean is dominated by the draws that happened to go badly, and averaging twenty-four such quantities gives a number that moves substantially from one set of twenty-four to the next. The median is stable at this sample size and it is what the comparison between splits needs, because the comparison is between curves whose separation is sometimes a factor of two.

The 90th percentile is computed alongside and is not drawn. It tells the same story with more noise: on the fast decay the best split’s p90 is below the third’s p90 by about the same factor the medians differ by, and on the slow decay the ordering is the same and the gaps are wider. Nothing in the argument turns on the tail, which is unusual for these essays — one draw in twenty is the standing reminder that a median can hide a rule’s whole failure mode, and the reason it does not here is that a split is not a search. There is no minimiser to run away, only a fixed division of a fixed budget, so the distribution of outcomes at each split is as well-behaved as the estimator itself.

Still open: a calibrated rule, and the same question for the other estimators #

A rule with a fitted constant. The reading and the best share are ordered together over six spectra. Fitting a share to a reading and testing it on spectra it was not fitted on is the measurement that would turn the ordering into a method, and it needs a second spectral family so that the test set is not the training set.

When to stop rather than how to split. Both halves of the budget above are fixed in advance. An estimator that watched its own probes could stop when they stopped buying accuracy, which is a different knob from the split and the subject of the next essay.

The same sweep on the contour estimator. Counting what is inside a circle uses a block of probes inside a quadrature, so it has two budgets — probes and quadrature nodes — and the same question of how to divide them. Whether its division has the same shape of answer, and whether anything the quadrature computes reads the decay, is unmeasured.

And whether the reading survives a non-decaying spectrum. The ratio $\sigma_k/\sigma_1$ of a sketch is near one on a flat spectrum, which is the reading that should say “do not sketch”. It does, on the geometric family. On a spectrum with a few large eigenvalues and a flat tail — the case a deflation should be best at — the reading would be small and the remainder large, which is the one configuration where the rule proposed here should get it wrong.