The sketch that is spent

Every object carried between the members of a sequence in this collection has a lifetime. A factorisation serves five members. A preconditioner serves eight or twelve depending on what it cost. A pivot order serves a whole run if the rows are in the right units.

A random sketch serves one, and the failure is not a degradation. It arrives on the second use, it is total, and nothing about the run reports it.

The mechanism, which is one line of algebra #

A randomised range finder draws Ω, forms Y = AΩ, and takes Q with the same range as Y. What it has found is a subspace, and the natural next round is to deflate — set A ← A − QQᵀA and go again, which is what every adaptive or blocked randomised scheme does.

With the same Ω,

A₂Ω = (A − QQᵀA)Ω = AΩ − QQᵀ(AΩ) = Y − QQᵀY = 0

because Q spans Y exactly. The second sketch is the zero matrix.

Measured: ‖AΩ‖/‖A‖ is 2.62 at the first round and 9.0·10⁻¹⁵ at the second, then 8.6·10⁻¹⁶, 7.6·10⁻¹⁶, 7.6·10⁻¹⁶. That is the unit roundoff, which is to say the sketch returns nothing at all, and the subspace the method then builds from it is whatever the rounding error happened to point at.

With a fresh Ω each round the signal stays at 2.62, 3.05, 3.12, 3.16, 3.31.

What it costs #

Both runs do the same arithmetic: five products with A, five orthogonalisations, five deflations. The approximation error after each round:

Two and a half times the error, for identical arithmetic. And the kept run’s error does fall a little — from 0.3291 to 0.2845 — which is worth understanding rather than dismissing: the deflation is still a projection, and projecting out a rounding-level subspace still removes a rounding-level amount of the matrix. The fall is real and it is worth almost nothing.

Nothing in the run reports a problem. The orthogonalisation succeeds, Q is orthogonal to the working precision, the projector is a projector, and every residual the method prints is the residual of what it actually computed.

Half a sketch is worth half a sketch #

Redrawing j of the ℓ columns and keeping the rest recovers a subspace of dimension j, not ℓ. The kept columns contribute nothing at all, and the run behaves as a smaller sketch would:

0 fresh → 0.2845 · 1 → 0.2594 · 2 → 0.2143 · 5 → 0.1717 · 8 → 0.1370 · 10 → 0.1126

The signal at the second round follows the same line: 9.0·10⁻¹⁵ with none redrawn, 0.82 with one, 1.80 with five, 3.05 with all ten. The number of useful directions per round is exactly the number of fresh columns, which is what makes this a quantitative statement rather than a warning.

Why the guarantee does not cover it #

The bounds in this field are statements about a random Ω drawn independently of the matrix it is applied to. That independence is not decoration — it is the whole content of the probability, which is over the draw.

Deflating with Q makes the next matrix a function of Ω. The next round’s input and its randomness are now the same object, and the probability that made the bound true is over a draw that has already happened and been conditioned on. There is nothing left to average over.

This is the same reading error as testing a hypothesis on the data that suggested it, arriving in a subject that does not usually think of itself as doing statistics. And it is worth noticing how easy it is to make: nothing in the code looks wrong, the sketch is still a Gaussian matrix, its entries are still independent of each other, and the failure is entirely in a relationship between two objects that no line of the program mentions.

The counterweight, which is most sequences #

The rule is not redraw every time, and the measurement that establishes that is the one worth having.

Twenty matrices drawn from the same construction with different seeds, so none of them can depend on Ω. One sketch applied to all twenty, against a fresh sketch for each:

one sketch kept: mean error 0.36184, spread 0.01936 twenty fresh: mean error 0.35789, spread 0.02271

A difference of 0.00395, against a standard error of 0.0051. The two distributions overlap completely, and both have a spread — so the agreement is two samples from one distribution rather than two constants that happen to match.

This is the case the bounds were written for, and reuse across it is completely safe. The randomness is spent the moment the input starts depending on it, and not before.

What the safe case can and cannot say #

The twenty-matrix comparison is the load-bearing half of this essay — without it the finding is “randomness is fragile, redraw always”, which is advice rather than a measurement — so it is worth saying exactly how strong it is, in the way a null result has to be.

The design is paired: the same twenty matrices are solved twice, once with the kept sketch and once with a fresh one, so the right statistic is the twenty differences rather than the two means. Those differences have a mean of 0.00395 and a standard deviation of 0.0243, giving a standard error of 0.00544 and a t of 0.73. The kept sketch is worse on 9 of the 20 matrices and better on 11, which is a coin toss and needs no distributional assumption to read.

The interval is the useful number. At 95 per cent the paired mean difference lies between −0.0074 and +0.0153, which as a fraction of the fresh policy’s own error is −2.1 per cent to +4.3 per cent. So the experiment does not say that reuse costs nothing. It says that reuse across independent inputs costs less than about four per cent, and that if it costs anything at all this measurement cannot see it.

Four per cent is the right resolution for the question being asked, and the comparison that shows it is the essay’s own first table: the effect when the dependence is real is 153 per cent — 0.2845 against 0.1126. The control is thirty-eight times finer than the effect it has to distinguish itself from, which is what makes “safe here, fatal there” a measured statement rather than two anecdotes.

One detail of the pairing is worth recording because it is mildly surprising and it constrains what a larger run would buy. Pairing usually helps by removing between-subject variation, and here it does not: the standard deviation of the differences, 0.0243, is larger than that of either policy alone (0.0194 and 0.0227). The two policies’ errors on the same matrix are essentially uncorrelated, so what a matrix “is” contributes almost nothing to which sketch does better — the variation is in the draw rather than in the problem. That is consistent with the bounds this field rests on, which are statements about the draw, and it means the way to tighten the interval is more trials rather than a better-matched set of matrices.

What the rule costs when it is wrong in the safe direction #

The one-line rule below is defended on an asymmetry — reusing where reuse was safe costs a Gaussian draw, and reusing where it was not costs the round — and the paired interval puts a number on the first half of that.

Redrawing when it was unnecessary costs n·ℓ normal variates and one extra pass to generate them, and buys, at the outside, the 4.3 per cent the interval’s upper end allows. Not redrawing when it was necessary costs 153 per cent. The ratio between the two mistakes is at least thirty-five, and the cheap mistake is also the one whose cost is known in advance — a draw is a fixed number of operations, while the expensive mistake’s cost depends on how much of the input has come to depend on the draw, which is exactly the quantity nobody is measuring.

That is the argument for a rule rather than a decision, stated as arithmetic rather than as a preference, and it is the reason this object is the only one of the five where the field’s usual crossover measurement is not worth taking. A crossover exists when both directions cost. Here one of them costs n·ℓ numbers, and the other costs the round.

The other four assets, and why this one is different #

It is worth putting the five objects this collection has now measured a lifetime for side by side, because the reason this one has a lifetime of one is not that randomness is fragile.

A factorisation, a preconditioner and a pivot order are all approximations to something about the current matrix. When the matrix drifts they become approximations to something about a matrix that is no longer there, and they degrade smoothly, because the thing they approximate degrades smoothly. The decision is a price.

An inner tolerance is not an object at all; it is a demand, and a demand made twice is the same demand.

A sketch is neither. It is not an approximation to anything about the matrix — it is a source of information about the matrix, and the information it carries is the whole of what it is for. Use it once and the information is extracted; the object that remains is a matrix of numbers with no relationship to the problem except the one that has already been exploited.

Which is why the failure is total rather than gradual. There is no drift, no shelf life, no crossover and no rule to write. The sketch has not gone stale; it has been spent.

That distinction is worth carrying because it says which of the five decisions needs a measurement and which needs only a rule. Four of them need a measurement, and the measurements are different for each object and each machine. This one needs a sentence: draw fresh randomness whenever the input has seen the last draw.

Where this bites in practice #

The construction in this essay is deliberately the simplest thing that shows the effect, and it is worth naming the real situations it stands for, because none of them looks like deflation.

Adaptive rank selection. Draw a sketch, estimate the error, and if it is too large, take more samples. The estimate was computed from the sketch; the decision to take more is a function of the draw; and the additional samples are being asked to certify a decision they participated in.

Blocked randomised factorisations, of the kind the field’s own range finder is built from. Process the matrix in blocks, deflating what each block finds. Exactly the loop in this essay, with the deflation implicit in the block structure.

Sketch-and-precondition, iterated. Build a preconditioner from a sketch, solve, and use the residual to decide whether to sketch again. The residual is a function of the sketch.

And any streaming method that reuses a fixed hash or projection across items whose arrival depends on earlier answers.

In all four the fix is the same and costs nothing: draw fresh randomness for each round. A Gaussian matrix is n·ℓ numbers, and the essay’s measurement is that they are worth 2.5× in error.

The reason to list them is that none of the four contains the word deflate, and three of them do not look like a loop at all. The dependence that spends the randomness is created by a decision — take more samples, process the next block, sketch again — and a decision is not an operation anybody records. A code review that asks “is this sketch reused?” gets a straight answer; one that asks “does anything downstream of this sketch decide what the sketch is next applied to?” is asking the question that matters and is much harder to answer by reading.

Which is the practical form of the essay’s finding: the failure is not in an expression, it is in a data-flow relationship between two objects that no single line of the program contains. The only cheap defence is the one above — fresh randomness per round, always — because it makes the question unnecessary.

Two routes to the zero #

The claim that the second sketch is exactly zero is an algebraic one, and this collection’s habit is to have two routes to anything it publishes. Both are here and they are worth separating.

The algebra. Q is an orthonormal basis for the range of Y = AΩ, so QQᵀ acts as the identity on Y. Then A₂Ω = (A − QQᵀA)Ω = Y − QQᵀY = 0, with no approximation anywhere: it is exact whenever Q spans Y exactly, which is what an orthogonal factorisation of Y produces.

The measurement. ‖A₂Ω‖/‖A₂‖ = 9.0·10⁻¹⁵ at the second round and 7.6·10⁻¹⁶ by the fourth. The first of those is fifty times the unit roundoff, which is what an orthogonalisation of a moderately-conditioned block costs, and the later ones are at it.

The two agree, and the disagreement between them is itself informative: the second round’s number is larger than the later ones because the first Q was computed from a Y whose columns are the least well conditioned in the run — the deflated matrices that follow have smaller dynamic range, so their sketches orthogonalise more cleanly. A run that reported 0 exactly would be a run whose arithmetic was not being measured.

That is the difference between a derivation and a figure, and it is the reason the vertical axis here is ‖AΩ‖/‖A‖ rather than the approximation error. An error curve that fails to improve says the round was disappointing. A signal curve at the unit roundoff says there was nothing there, which is a much stronger statement and the one the algebra predicts.

The one-line rule, and why it is worth having as a rule #

Most of this field ends in a measurement and a decision that has to be made per problem. This one ends in a sentence, and the difference is worth noticing.

Draw fresh randomness whenever the input has seen the last draw.

It costs n·ℓ numbers, which is nothing beside the matrix product that follows. It never needs tuning, never needs a drift rate or a setup cost, and cannot be wrong in the expensive direction — reusing where reuse was safe costs a Gaussian draw, and reusing where it was not costs the round entirely. There is no crossover to measure because one side of the trade is free.

That asymmetry is what makes it a rule rather than a decision. The other four objects in this field are expensive to build and cheap to keep, so keeping them is worth a measurement; this one is cheap to build and worthless to keep, so keeping it is worth nothing at all. Naming the asymmetry is more useful than naming the failure, because a reader who remembers only that reuse is dangerous will also avoid the safe case — where twenty independent matrices sketched with one draw cost 0.36184 against 0.35789, which is to say nothing.

What is asserted #

That the first round of the kept sketch sees the matrix — 2.62 — so the failure is not a bad draw.

That every later round sees below 10⁻¹³, which is the algebra’s prediction measured rather than derived.

That the error stops falling: five rounds of fresh sketches reduce it 2.92-fold and five kept rounds 1.16-fold, leaving the kept run more than twice as far out after the same arithmetic.

That the kept columns are worth nothing: the final error falls monotonically with the number of redrawn columns, and half a sketch sees a signal between a whole one’s and none.

And that reuse is safe when nothing adapts, with the two means agreeing inside a standard error and both distributions having a spread.

The refusals are the three misreadings: the annihilated sketch claimed for a sketch that was redrawn; the safety of reuse claimed for the adaptive sequence; and one fresh column claimed to be worth ten.

The first round is the same number in both columns at every width — 1.4 against 1.42, 2.3 against 2.33, 2.6 against 2.62 — which is the check that nothing else differs between the two runs. They are the same arithmetic on the same draw until the moment one of them draws again.

Zero on the second round at every width, from 2.3·10⁻¹⁵ at four columns to 2.3·10⁻¹⁴ at twenty-four. The one number that grows with ℓ is the rounding, which is what it should be. Nothing about the failure is a matter of the sketch being too narrow to see anything.

But something else changes across the slider, and it is bigger than the finding the dek states. The final errors, kept against fresh:

Below sixteen columns, reuse costs a factor of about two and a half. At sixteen and above it costs everything. Fresh sketching crosses a width at which it recovers the answer to the unit roundoff — the subspace is fully found and there is nothing left to deflate — and the kept sketch is still at 0.236, because the second and subsequent rounds contributed nothing at any width.

That is the reading a caller needs and it is the opposite of reassuring. A wider sketch does help the reuse case: 0.535 down to 0.155 across the slider, so someone tuning ℓ upward sees the error improve and may conclude the method is converging. It is not. The improvement is entirely in the first round, and every column added widens the gap to what the same code would have done with a fresh draw.