Numerical Linear Algebra
where the algebra stops being the arithmetic
Randomised, and the guarantee that changes kind

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.
30 min read 24 figures Where the algebra stops being the arithmeticMeasured, not assertedAssertions that rejectTwo routes to a number

Worth reading first: The dimension does not appear · A bound that holds with probability · The problem that arrives again.

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.

What each round of sketch-and-deflate actually sees, for a sketch kept, half redrawn, and redrawnA randomised range finder forms Y = AΩ, takes Q spanning it, and deflates: A ← A − QQᵀA. With the same Ω the next sketch is A₂Ω = AΩ − QQᵀ(AΩ) = Y − QQᵀY, which is zero exactly, because Q spans Y. Measured, the kept sketch sees 2.62 at the first round and 9.03·10⁻¹⁵ at the second — the unit roundoff, which is to say nothing at all, and the subspace it produces after that is whatever the rounding error happened to point at. A fresh sketch stays at about 3.3, and redrawing half the columns sees about half as much. After 5 rounds of identical arithmetic the kept run is at 0.2845 and the redrawn one at 0.1126.012345610⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹round‖AΩ‖ ⁄ ‖A‖ at that roundredrawn each roundhalf redrawnkept: the sketch is now the zero matrixthe randomness is spentkept, round 12.6kept, round 29·10⁻¹⁵redrawn, round 23.1kept, final error0.28redrawn, final error0.11a random matrix used twiceis not random the second time
Fig. 1 What each round of sketch-and-deflate actually sees, for a sketch kept, half redrawn, and redrawn. The lower curve is at the unit roundoff from the second round onwards.

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 each round of sketch-and-deflate actually sees, for a sketch kept, half redrawn, and redrawnA randomised range finder forms Y = AΩ, takes Q spanning it, and deflates: A ← A − QQᵀA. With the same Ω the next sketch is A₂Ω = AΩ − QQᵀ(AΩ) = Y − QQᵀY, which is zero exactly, because Q spans Y. Measured, the kept sketch sees 1.42 at the first round and 2.26·10⁻¹⁵ at the second — the unit roundoff, which is to say nothing at all, and the subspace it produces after that is whatever the rounding error happened to point at. A fresh sketch stays at about 2.6, and redrawing half the columns sees about half as much. After 5 rounds of identical arithmetic the kept run is at 0.5355 and the redrawn one at 0.2255.012345610⁻¹⁷10⁻¹³10⁻⁹10⁻⁵10⁻¹round‖AΩ‖ ⁄ ‖A‖ at that roundredrawn each roundhalf redrawnkept: the sketch is now the zero matrixthe randomness is spentkept, round 11.4kept, round 22.3·10⁻¹⁵redrawn, round 21.9kept, final error0.54redrawn, final error0.23a random matrix used twiceis not random the second time
Fig. 2 A narrower sketch, which finds less per round and fails on the second round in exactly the same way. The problem is not that the sketch is too small.
What each round of sketch-and-deflate actually sees, for a sketch kept, half redrawn, and redrawnA randomised range finder forms Y = AΩ, takes Q spanning it, and deflates: A ← A − QQᵀA. With the same Ω the next sketch is A₂Ω = AΩ − QQᵀ(AΩ) = Y − QQᵀY, which is zero exactly, because Q spans Y. Measured, the kept sketch sees 4.23 at the first round and 2.26·10⁻¹⁴ at the second — the unit roundoff, which is to say nothing at all, and the subspace it produces after that is whatever the rounding error happened to point at. A fresh sketch stays at about 4.7, and redrawing half the columns sees about half as much. After 5 rounds of identical arithmetic the kept run is at 0.1548 and the redrawn one at 1.686·10⁻¹⁶.012345610⁻¹⁶10⁻¹²10⁻⁸10⁻⁴1round‖AΩ‖ ⁄ ‖A‖ at that roundredrawn each roundhalf redrawnkept: the sketch is now the zero matrixthe randomness is spentkept, round 14.2kept, round 22.3·10⁻¹⁴redrawn, round 24.8kept, final error0.15redrawn, final error1.7·10⁻¹⁶a random matrix used twiceis not random the second time
Fig. 3 And a wider one, which finds more and fails identically. Widening moves the upper curve and leaves the lower one on the floor.

What it costs

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

round sketch kept half redrawn redrawn
1 0.3291 0.3291 0.3291
2 0.3183 0.2784 0.2384
3 0.3056 0.2341 0.1806
4 0.2948 0.1978 0.1401
5 0.2845 0.1717 0.1126

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.

Error of the best rank-k approximation to a 40×40 matrixApproximation error against k on a logarithmic axis, with the measured error and the next singular value drawn as separate curves lying exactly on top of one another.12345678910111213141516171819202122232425262728293031323334353637383910⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²1rank k of the approximation‖A − Aₖ‖measured, 2-normσₖ₊₁, from theorymeasured, Frobeniusthe first two agreeto 2·10⁻⁸worst |‖A−Aₖ‖₂ − σₖ₊₁| / σₖ₊₁2·10⁻⁸worst Frobenius discrepancy2·10⁻⁸κ = 10⁹; 30 random rank-3 matrices, none closerthe error is σₖ₊₁
Fig. 4 What a low-rank approximation’s error should look like against the rank kept, from the field that measured it. The kept-sketch run is climbing a much flatter version of this curve.
What a rank-10 approximation can achieve, by spectrumA semi-logarithmic plot of singular value against index for three spectra — geometric decay, algebraic decay, and flat — with the rank-ten approximation error marked on each.1112131415110⁻³10⁻²10⁻¹1index jσⱼσ11geometric, 0.85ʲalgebraic, j^−1.00flatmeasured, and equal to σ₁₁rank-10 error, geometric0.2rank-10 error, algebraic0.091rank-10 error, flat160×60, spectrum chosen rather than the entriesthe matrix decides, not the method
Fig. 5 And the spectrum being approximated, which decays slowly on purpose: a fast decay is captured in the first round whatever happens next, and there would be nothing left to measure.

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.

What each round of sketch-and-deflate actually sees, for a sketch kept, half redrawn, and redrawnA randomised range finder forms Y = AΩ, takes Q spanning it, and deflates: A ← A − QQᵀA. With the same Ω the next sketch is A₂Ω = AΩ − QQᵀ(AΩ) = Y − QQᵀY, which is zero exactly, because Q spans Y. Measured, the kept sketch sees 2.33 at the first round and 9.28·10⁻¹⁵ at the second — the unit roundoff, which is to say nothing at all, and the subspace it produces after that is whatever the rounding error happened to point at. A fresh sketch stays at about 2.3, and redrawing half the columns sees about half as much. After 5 rounds of identical arithmetic the kept run is at 0.4114 and the redrawn one at 0.1802.012345610⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹round‖AΩ‖ ⁄ ‖A‖ at that roundredrawn each roundhalf redrawnkept: the sketch is now the zero matrixthe randomness is spentkept, round 12.3kept, round 29.3·10⁻¹⁵redrawn, round 22.3kept, final error0.41redrawn, final error0.18a random matrix used twiceis not random the second time
Fig. 6 The middle policy at a different width, where half of six behaves as three fresh columns would.
The randomised SVD against the optimum it cannot beatA semi-logarithmic plot of approximation error against target rank. A shaded band shows the spread across seeds, a solid line the optimal error from the exact singular values, and a dashed line the published probabilistic bound well above both.04812162010⁻¹10⁻⁰.⁵1target rank k‖A − A_k‖₂published boundrandomisedσ_{k+1}, optimalhow far apart the three areworst seed spread1.6bound / median at k = 125.9median / optimum at k = 121.960×60, 6 seeds, oversampling p = 5band is best to worst
Fig. 7 The randomised error bound as a band, from the essay that established that the guarantee changes kind. Everything here is about what that band is a statement over.

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.

160 single-probe estimates of one 40×40 trace, from the two standard probe distributionsTwo clouds of points, each one estimate of the trace from one random vector. Both are centred on the true value of 171.14 — the estimator has no bias at all — and the dashed bands are the standard deviation each distribution is known in closed form to have: 59.14 for the ±1 probe and 72.01 for the normal one. Measured over these draws they come out 56.68 and 68.57.027548110813544119.306194.613269.919345.226420.532drawzᵀAz from one probenormal±1two routes to one spreadthe trace171±1 spread, predicted59±1 spread, measured57normal ÷ ±11.2no bias in either cloudand one of them is narrower for a reason
Fig. 8 The spread over draws, from the field that measures it — the object the guarantee is an average over, and the thing a second use has already spent.
Which of the two least-squares methods is more accurate, as a fixed amount of noise moves from b into AOne curve: the ordinary least-squares error over the total least-squares error, at each share of the noise placed in the matrix, as the median over 40 seeds. It runs from 0.28 when all the noise is in b — where ordinary least squares is the more accurate — to 2.47 when all of it is in A. The line at one is where the two methods are equally right.00.250.50.75110⁻¹110¹share of the noise placed in the matrixleast-squares error ÷ total least-squares errorequally accuratetotal leastsquares aheadordinary leastsquares aheadthe model, not the methodadvantage, all noise in b0.28advantage, all noise in A2.5seeds at each share40the same total noise at every pointand only where it sits changes
Fig. 9 And the seed as a variable in its own right, from the essay that measured how much of an answer it owns.

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.

One sketch reused across 20 independent matrices, against a fresh sketch for eachThe matrices are drawn from the same construction with different seeds, so none of them can depend on the sketch. This is the case the randomised bounds were written for, and the two rows of points are the answer: mean error 0.36184 with one sketch kept and 0.35789 with 20 fresh ones, a difference of 0.00396 against a standard error of 0.00508. The rule is therefore not that a sketch must be redrawn — it is that the randomness is spent the moment the input starts depending on it.31323334353637383940410123relative approximation error ‖A − QQᵀA‖ ⁄ ‖A‖, per centone sketch, kepta fresh sketch eachthe vertical marks are the two meansreuse, where nothing adaptskept sketch, mean error0.36fresh sketches, mean error0.36difference0.004standard error of either0.0051spread, kept0.019the guarantee is about a drawthe input has not seen
Fig. 10 Twenty independent matrices, sketched twice: once with a kept sketch and once with a fresh one each time. The vertical marks are the two means.
One sketch reused across 40 independent matrices, against a fresh sketch for eachThe matrices are drawn from the same construction with different seeds, so none of them can depend on the sketch. This is the case the randomised bounds were written for, and the two rows of points are the answer: mean error 0.36090 with one sketch kept and 0.35638 with 40 fresh ones, a difference of 0.00452 against a standard error of 0.00342. The rule is therefore not that a sketch must be redrawn — it is that the randomness is spent the moment the input starts depending on it.3132333435363738394041420123relative approximation error ‖A − QQᵀA‖ ⁄ ‖A‖, per centone sketch, kepta fresh sketch eachthe vertical marks are the two meansreuse, where nothing adaptskept sketch, mean error0.36fresh sketches, mean error0.36difference0.0045standard error of either0.0034spread, kept0.017the guarantee is about a drawthe input has not seen
Fig. 11 And at forty, where both strips narrow towards the same place — the shape a null result should have, rather than two distributions converging on each other from opposite sides.

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.

Chord steps per member of a drifting sequence, with the factorisation rebuilt every 4Each point is one member of a continuation, warm-started from the previous member's answer and solved with a factorisation that is between zero and 3 members old. The lower series is the same sequence with a fresh factorisation at every member, which costs 6 to 5 steps throughout. The kept run costs 6 steps on a fresh factor and 12 at its worst, for 5 factorisations against 20.03691215182103691215member of the sequencechord steps to reach the tolerancea fresh factorisation each memberthe ringed points are the refactorisationsrebuilt every 4factorisations5chord steps160worst member's steps12multiplications1.2·10⁷with a fresh factor each time1.8·10⁷a factor is cheapest the member it was built forand dearest the member before it is replaced
Fig. 12 An object that ages, for contrast: a factorisation costing more the further it is from the member it was built for.
An incomplete Cholesky kept while the operator turns anisotropic, against one rebuilt at every memberThe five-point operator's two directions stop being equally weighted, ε running from 1 down to 0.0331, with the sparsity pattern unchanged throughout — so the factorisation from the first member stays applicable for the whole run, which is the situation in which it gets kept. The kept one goes from 18 iterations to 52. The rebuilt one goes from 18 to 13, because an anisotropic operator is an easier problem for a factorisation that knows about the anisotropy. The two start at the same point by construction and never meet again.0246810121416182001020304050member of the sequencepreconditioned conjugate gradient iterationskept from the first memberrebuilt every memberone operator, two policieskept, first member18kept, last member52rebuilt, first member18rebuilt, last member13ε at the last member0.033the problem got easierand the kept preconditioner got worse at it
Fig. 13 And another, whose ageing is gentle enough that nothing in a run announces it.
What 24 members of a sequence cost, by what changes between themEvery bar is 24 solves of an 120×120 system, costed in multiplications with a dense Cholesky at n³/3 and a solve at 4n². When nothing changes the answer is reused and the cost is one factorisation. When only the right-hand side changes, one factorisation serves every member — 12.7 per cent of the independent cost, with every solve still at a relative residual of 1.54·10⁻¹³. When the matrix drifts, the factorisation is reusable for a while and the while has to be measured: 7 factorisations for 24 members. When everything changes, nothing carries.nothing4.2%the right-hand side12.7%the matrix, slowly83.2%everything100.0%what can be reused: the answerwhat can be reused: the factorisationwhat can be reused: the factorisation, for a whilewhat can be reused: nothingshare of the cost of a sequence that shares nothingwhat 24 members cost in factorisationssame: factorisations1rhs: factorisations1drift: factorisations7independent: factorisations24what changes between the membersdecides what may be carried
Fig. 14 The ledger of what a sequence licenses, at twice the length. Every bar in it has a shelf life except the one this essay is about.

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. 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.

Sketch distortion against sketch width, for 200 vectorsA log-log plot of the worst relative change in vector length against the number of rows in the sketch, for vectors of two dimensions a factor of four apart. The two curves lie almost on top of one another and both fall steadily.10²10².³10².⁵⁹⁹⁹⁹⁹⁹⁹⁹⁹⁹⁹⁹⁹⁹⁶10⁻¹10⁻⁰.⁵1rows in the sketchworst relative distortiondimension 64dimension 2565 seeds per point, band is best to worstthe dimension does not appear
Fig. 15 What a sketch does to lengths, from the essay that established the machinery. Every one of those guarantees is over the draw.
The recovered signal at three λ, 1.0% noiseThree recovered signals against the truth. At the best λ the two bumps are recovered and the step is rounded off. Fifty times smaller and the answer is dominated by amplified noise; fifty times larger and the step has gone entirely. The step is the feature that costs the most to represent and it is the first thing any filter loses.0816243240485600.511.5positionvaluethe truthbest λtoo littletoo mucheither side of the bestbest λ, relative error0.14fifty times smaller1.6fifty times larger0.43the step is the first thing every filter losesand it does not come back
Fig. 16 And a randomised method used as a filter, from the field about methods designed apart — one of the places a sketch is reused without the reuse being visible.

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.

‖QᵀQ − I‖ of the implied Q, against the condition numberLoss of orthogonality against κ, both axes logarithmic, for three factorisations of the same 256×8 matrix. The column sweep and the reduction tree run from 2.7·10⁻¹⁴ to 1.5·10⁻¹⁰. Cholesky QR — the one with a single reduction — runs from 2.3·10⁻¹³ to 1.8·10⁻⁵, a fitted slope of 1.97 against the others' near-flat one.10²10³10⁴10⁵10⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶condition number κ‖QᵀQ − I‖Cholesky QRsweeptreethe price of one roundfitted slope, Cholesky QR2‖QᵀQ − I‖ at κ = 10·10⁵1.8·10⁻⁵the sweep's, at the same κ1.5·10⁻¹⁰one reduction instead of nand the condition number squared
Fig. 17 What an orthogonalisation costs against the conditioning of what it is given, from the field that measured it. The 9.0·10⁻¹⁵ above is a reading of this curve at the first block’s conditioning.
QᵀQ from classical Gram–Schmidt and from Householder on the 10×10 Hilbert matrixTwo eight-by-eight tables of QᵀQ. The upper one has ones on the diagonal and entries as large as one off it; the lower one is the identity to three decimal places everywhere.A = H10 · κ = 1.6·10¹³ · both factorisations reconstruct A to 6.4·10⁻¹⁷the diagonal is 1 in both — every column is a unit vector either way1.00000000000001.00000000000001.00000000000001.00000000000001.0000-0.001-0.001-0.001-0.001000001.000-0.053-0.042-0.035-0.0280000-0.001-0.0531.0001.0001.0001.0000000-0.001-0.0421.0001.0001.0001.0000000-0.001-0.0351.0001.0001.0001.0000000-0.001-0.0281.0001.0001.0001.000classical Gram–Schmidt1.00000000000001.00000000000001.00000000000001.00000000000001.00000000000001.00000000000001.00000000000001.00000000000001.00000000000001.000Householderclassical ‖QᵀQ − I‖3.5Householder ‖QᵀQ − I‖1.9·10⁻¹⁵largest off-diagonal 1 against 4·10⁻¹⁶length is not angle
Fig. 18 And orthogonality printed as a number rather than assumed, which is the collection’s standing discipline and is what licenses the paragraph above.

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.

What each round of sketch-and-deflate actually sees, for a sketch kept, half redrawn, and redrawnA randomised range finder forms Y = AΩ, takes Q spanning it, and deflates: A ← A − QQᵀA. With the same Ω the next sketch is A₂Ω = AΩ − QQᵀ(AΩ) = Y − QQᵀY, which is zero exactly, because Q spans Y. Measured, the kept sketch sees 3.40 at the first round and 1.42·10⁻¹⁴ at the second — the unit roundoff, which is to say nothing at all, and the subspace it produces after that is whatever the rounding error happened to point at. A fresh sketch stays at about 3.8, and redrawing half the columns sees about half as much. After 5 rounds of identical arithmetic the kept run is at 0.2358 and the redrawn one at 4.372·10⁻¹⁵.012345610⁻¹⁶10⁻¹²10⁻⁸10⁻⁴1round‖AΩ‖ ⁄ ‖A‖ at that roundredrawn each roundhalf redrawnkept: the sketch is now the zero matrixthe randomness is spentkept, round 13.4kept, round 21.4·10⁻¹⁴redrawn, round 24kept, final error0.24redrawn, final error4.4·10⁻¹⁵a random matrix used twiceis not random the second time
Fig. 19 The measurement once more at a fourth width, because the finding is about the reuse and not about ℓ.
The randomised SVD against the optimum it cannot beat, with 1 power iterationA semi-logarithmic plot of approximation error against target rank. A shaded band shows the spread across seeds, a solid line the optimal error from the exact singular values, and a dashed line the published probabilistic bound well above both.04812162010⁻¹10⁻⁰.⁵1target rank k‖A − A_k‖₂published boundrandomisedσ_{k+1}, optimalhow far apart the three areworst seed spread1.2bound / median at k = 1211median / optimum at k = 12160×60, 6 seeds, oversampling p = 5band is best to worst
Fig. 20 The same bound with a power iteration applied, from the essay that measured what that buys. It moves the band and does not change what a second use of the same draw is worth.
What 12 members of a sequence cost, by what changes between themEvery bar is 12 solves of an 120×120 system, costed in multiplications with a dense Cholesky at n³/3 and a solve at 4n². When nothing changes the answer is reused and the cost is one factorisation. When only the right-hand side changes, one factorisation serves every member — 16.5 per cent of the independent cost, with every solve still at a relative residual of 1.54·10⁻¹³. When the matrix drifts, the factorisation is reusable for a while and the while has to be measured: 4 factorisations for 12 members. When everything changes, nothing carries.nothing8.3%the right-hand side16.5%the matrix, slowly85.9%everything100.0%what can be reused: the answerwhat can be reused: the factorisationwhat can be reused: the factorisation, for a whilewhat can be reused: nothingshare of the cost of a sequence that shares nothingwhat 12 members cost in factorisationssame: factorisations1rhs: factorisations1drift: factorisations4independent: factorisations12what changes between the membersdecides what may be carried
Fig. 21 And the field’s ledger of what a sequence licenses, where this is the one entry whose licence is a single use.
A single Newton step solved to eleven inner tolerances, against how far the resulting point is from the rootThe iterate is 0.0372 from a root that is known exactly by construction. The same linear system is solved to relative residuals from 0.3 down to 10⁻¹⁴, at 109 and 1126 conjugate gradient iterations, and the resulting point is 0.005319 and 0.002497 from the root. The curve is flat below about 10⁻³: the linearisation is wrong at second order, so the step cannot land closer than the square of the distance it started at — 0.001383 — however exactly it is computed.10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³110⁻⁴10⁻³10⁻²10⁻¹1inner tolerance η, relative residual of the linear solvedistance from the root after the stepd² = 0.00138distance before the step, 0.03721093547231126the number by each point is the iterations it costeleven decades, one landing placedistance before the step0.037its square0.0014where η = 10⁻³ lands0.0025where η = 10⁻¹⁴ lands0.0025iterations for the first354iterations for the second1126the accuracy that is thrown awaymeasured against a root that is known
Fig. 22 And the opposite end of that ledger: an inner object whose error is forgiven eleven decades over, because the loop that uses it asks the matrix again.
Sketch distortion against sketch width, for 400 vectorsA log-log plot of the worst relative change in vector length against the number of rows in the sketch, for vectors of two dimensions a factor of four apart. The two curves lie almost on top of one another and both fall steadily.10²10².³10².⁵⁹⁹⁹⁹⁹⁹⁹⁹⁹⁹⁹⁹⁹⁹⁶10⁻¹10⁻⁰.⁵1rows in the sketchworst relative distortiondimension 64dimension 2565 seeds per point, band is best to worstthe dimension does not appear
Fig. 23 The distortion of a sketch at twice the sample count, which narrows the band and does nothing whatever about a second use.
How close Hager's estimate is to the true κ₁, over 200 seeded 8×8 matricesFive bars. The estimate is exactly the true condition number on 81% of the sample and inside ten per cent on 87%; the worst underestimate in the whole sample returns 38% of the truth. The last bar is the matrix built to defeat it, at 7.7%, well below anything the random sample reached.each bar is a percentage — of the sample, or of the true condition numberexactly right80.5%inside 10%87.0%inside a factor of 287.0%worst in the sample, ×10037.7%the constructed matrix, ×1007.7%usually exactexact share0.81worst of the sample0.38the constructed matrix0.077a routine that is right most of the timeand never wrong in the safe direction
Fig. 24 And a randomised estimate’s spread, from the field that measured it — another quantity whose guarantee is over a draw the input has not seen.

Where this goes next

04812162010⁻¹10⁻⁰.⁵1target rank k‖A − A_k‖₂published boundrandomisedσ_{k+1}, optimalhow far apart the three areworst seed spread1.6bound / median at k = 125.9median / optimum at k = 121.960×60, 6 seeds, oversampling p = 5band is best to worst A bound that holds with probability Every other guarantee on this site 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. 04812162010⁻¹10⁻⁰.⁵1target rank k‖A − A_k‖₂published boundrandomisedσ_{k+1}, optimalhow far apart the three areworst seed spread1.1bound / median at k = 1211median / optimum at k = 12160×60, 6 seeds, oversampling p = 5band is best to worst 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. nothing8.3%the right-hand side16.5%the matrix, slowly85.9%everything100.0%what can be reused: the answerwhat can be reused: the factorisationwhat can be reused: the factorisation, for a whilewhat can be reused: nothingshare of the cost of a sequence that shares nothingwhat 12 members cost in factorisationssame: factorisations1rhs: factorisations1drift: factorisations4independent: factorisations12what changes between the membersdecides what may be carried The problem that arrives again A hundred and thirty essays have solved a system once and measured how wrong the answer was. Almost no computation is shaped like that. A solve is one step of an outer loop, its answer is an input rather than a deliverable, and four quantities this collection has treated as accuracy requirements turn out to be assets with a shelf life.

Shares its objects with

Essays that name at least two of the same things, and that neither author linked.

Named objects

A flat tag is an object no other essay names yet.

AdaptivityDeflationLow-rank approximationOrthogonal projectionProbability boundRandomised SVDRange finderSketchingUnit roundoff