Randomised, and the guarantee that changes kind
A bound that holds with probability
Every other guarantee in this collection is deterministic. The randomised low-rank approximation offers one that holds with a probability, the seed changes the answer, and the honest figure is a band rather than a line.
The dimension does not appear
A random projection preserves the lengths of a set of vectors to within a distortion that depends on how many vectors there are and not on how many coordinates each one has. That is the fact the whole field rests on, and it is genuinely surprising.
Randomisation does not create structure
On a matrix whose singular values are all equal, a rank-ten randomised approximation has error 1.0 — and so does the optimal deterministic one. Neither achieved anything, and only one of them is usually sold with the implication that it might.
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.
The sketch that is not the answer
Sketch-and-solve throws away the original problem and keeps the small one's answer, which is why its answer moves with the seed. Use the same sketch as a preconditioner instead and the condition number the iteration sees is the same number at every κ from a hundred to ten billion — identically the same, to nine digits, because the spectrum cancels out of it.
The sketch that is spent
Every other object a sequence carries has a shelf life. A random sketch has one use. Deflate what its first round found and apply it again, and it returns the zero matrix — 9.0·10⁻¹⁵ where the first round saw 2.62 — because the input has been made orthogonal to the very draw the guarantee is over.
Built from products alone
A 512-square hierarchical representation, at a relative error of 4·10⁻⁷, from 256 applications of an operator that is never assembled. The compression route reads 262,144 entries; this one reads none, and pays for it with a factor of seven against the representation the entries would have given.
Sketching what is never unfolded
A range finder multiplies its matrix by a few random vectors. For a mode-k unfolding those vectors have nᵈ⁻¹ entries, so the random object is the size of the tensor divided by n — and by six indices it is larger than the tensor it is sketching.
The half of a problem a sketch may touch
A sketch guarantees that a norm is preserved to within a factor. An equality constraint is a statement that a quantity is zero, and no multiplicative guarantee says anything about zero. Sketch a constrained problem written as a weighted one and the constraint is not destroyed — it is demoted, from a violation of 1/τ² to one of ε/τ, exactly half the exponent.
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.
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.
What a single draw cannot report
With no oversampling the construction's error is 11.6 to 50 times the best representation of the same rank, and the spread across five seeds runs from 16 to 146 per cent of the mean. Sixteen extra columns bring the excess to between 2.0 and 2.9 at every rank measured and the spread to between 4 and 20 per cent — and the second number is the one a single run cannot report and the one that decides whether the first is a measurement.
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 rank a certificate charges
A randomised range finder can choose its own rank: grow the basis a column at a time and stop when ten fresh probes all come back short. With the published safety factor it never stopped early in any draw measured, and on a matrix whose singular values fall by 0.8 a step it stopped at rank 30 for a tolerance the best rank-11 approximation already meets. The nineteen extra columns are three separate prices — four for building the basis from random vectors, five because a probe reads more than the spectral norm, and ten for the constant — and the spectrum decides which of them dominates.
A sketch that finds the columns it can see
A sparse sketch with one nonzero in each row is twenty times cheaper to apply than a Gaussian one, and on a matrix whose important directions are spread across its columns it finds the same range: a median error of 0.45 against 0.43. Put the same ten directions into ten particular columns and it is eight times worse — 3.33 against 0.41, with a worst draw of 7.1 — because two important columns hashed to one bucket are one direction. Three nonzeros a row repair it at a sixth of the Gaussian's cost, and a randomised Hadamard transform never had the problem.
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.
The leverage that did not move
A one-nonzero sketch fails on a matrix whose leading directions sit on ten particular columns, and coherence — the largest column leverage — is the statistic that names the failure. Turn the directions away from their columns by a hundredth of a radian and the sketch's median error falls from 3.47 to 1.23 times σ₁₁ while the coherence stays at 6.40 to three figures. Giving the heaviest columns buckets of their own repairs the rest, but only when it reserves more buckets than the rank: ten reserved leave 1.16, sixteen reach 0.36, below the Gaussian's 0.41.
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 fade made of drops
A one-nonzero sketch's median error fell by about forty per cent for every factor of ten in how far a coherent matrix had been mixed toward an incoherent one, and nothing explained the rate. Followed one draw at a time, no draw fades at that rate. Each holds its coherent error — as large as the singular value of the direction its hash lost — and then drops, within one to three decades of mixing, never faster than one decade of error per decade of mixing. The median's steady slope is where the drops happen to fall. Change the spectrum and they fall elsewhere: at a decay of 0.9 there is no slope, only a cliff.
The probe that refuses becomes the column
An adaptive range finder grows its basis from probes and stops when ten fresh ones come back short. Sparse probes cost a twentieth as much and fail on a matrix whose important directions sit on particular columns. Used for both jobs on such a matrix they certify falsely on eight draws of thirty, with the error ten times the tolerance. Let Gaussian probes do the certifying and the sparse basis is never certified falsely — but on eighteen draws of thirty it is never certified at all. The repair is to let a certifying probe that sees eight times more, per unit of its own length, than the next sparse candidate become the column instead. On the incoherent matrix that never happens and the rule costs 29 per cent of the all-Gaussian one; on the coherent matrix it happens a median ten times — about once for each direction the sparse probes cannot find — and every draw certifies correctly at 54 per cent.
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.
Promotion buys rank, not safety
A range finder that grows its basis from cheap sparse probes and certifies it with dense ones was made safe on a coherent matrix by promoting a refusing dense probe into the basis — ten promotions for ten coherent directions, none for none. On matrices mixed between the two, the promotions fade as predicted: ten at the coherent end, nine at a mixture angle of 0.1, none from 0.8. But the danger they guard against does not fade with them. It is gone at an angle of 0.05, where the rule that never promotes already certifies every draw correctly. What promotion buys there is rank — a basis of 30 columns instead of 38 — for four fifths more probe work, and the threshold that decides it is a price, not a safety margin.
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.
The fall sets the undershoot
A trend-carried spread meets a turn sharper than the drift before it — the decay rising 0.02 a trace and then falling 0.06 — and the prediction was a spread about 0.6 of the truth on the trace after the turn, coverage under 55 per cent, a fresh pilot there restoring it, and the sequence's average within two points. All four hold: 0.617, 48.5 per cent, 71.0 per cent, and 67.7 against the table's 68.3. What fails is the rule the earlier essay gave for the error, the square of the last ratio. The undershoot is the last ratio over the next one, and the coverage it costs is the normal table's at that fraction.