The sketch that is not the answer

The dimension does not appear established what a sketch is: a random matrix S with far fewer rows than columns, such that ‖SAx‖ ≈ ‖Ax‖ for every x in a subspace, with the required number of rows depending on the dimension of the subspace and not on the length of the vectors. On this site it was used to build a low-rank approximation, and randomisation does not create structure drew the boundary of what that buys.

There is a use of a sketch that this site filed under cost and then left alone. sketchAndSolve — form SA and Sb, solve the small least-squares problem, keep the answer — was measured at 10 to 30% off the exact residual, and the site’s summary was that what sketching buys is the same quality for fewer passes, which is a statement about cost.

That summary is wrong about this particular method, and the reason is a change of kind rather than of degree.

Keep both problems #

Sketch-and-solve throws the original problem away. Sketch-and-precondition keeps it.

Take the QR of the sketch: SA = QR, with R an n×n triangular factor costing O(ln²) where l is the sketch’s height. Then run an iterative least-squares solver — LSQR — on the full problem (AR⁻¹) y = b, and set x = R⁻¹y.

R⁻¹ is never formed. Each application is a triangular solve, O(n²), inside an iteration whose products with A cost O(mn).

The claim is that AR⁻¹ is beautifully conditioned however badly conditioned A was.

The flatness is exact, and here is why #

The bound in the literature is κ(AR⁻¹) ≤ (1+ε)/(1−ε) with ε the embedding distortion, and it is notable for having no κ(A) in it at all.

Measured with the spectrum as the only thing that changes — the same U, the same V, the same sketch — the numbers agree to nine digits across eight decades of κ(A). That is far more than a bound predicts, and two lines of algebra say why.

Write A = UΣVᵀ and G = SU, W = ΣVᵀ, so SA = GW. Then RᵀR = (GW)ᵀ(GW) = WᵀGᵀGW, so R = O·(WᵀGᵀGW)^(1/2) for some orthogonal O. The singular values of AR⁻¹ = UWR⁻¹ are those of WR⁻¹, whose squares are the eigenvalues of

(WᵀGᵀGW)^(−1/2) WᵀW (WᵀGᵀGW)^(−1/2)

which is similar to (WᵀGᵀGW)⁻¹WᵀW, which for invertible W is similar to (GᵀG)⁻¹.

There is no W in it. So κ(AR⁻¹) = κ(SU) exactly: the condition number of the sketch against the column space of A, with the spectrum of A cancelled out.

That is asserted as a second route. κ(SU) is computed from an orthonormal basis of the column space and the sketch, never touching Σ, and it agrees with the measured κ(AR⁻¹) to 10⁻⁶.

The nine digits rather than sixteen are worth a sentence: at κ(A) = 10¹⁰ the R⁻¹ is applied through a triangular factor spanning ten decades, so the shortfall is the rounding of the preconditioner and not a κ(A) term hiding in the answer.

Most of what a sketch can do for the conditioning is done by the time it has three rows per column, which is not obvious from either end of the theory:

The return on sketch width collapses after the first step. Across the slider κ(AR⁻¹) reads 6.128598, 2.786087, 2.228378, 2.070392 and 1.661585 at two, three, four, six and ten rows per column. Going from 2n rows to 3n buys a factor of 2.2. Going from 3n all the way to 10n — more than three times the sketch, and more than three times the passes over A to build it — buys 1.7.

And κ(AR⁻¹) equals κ(SU) to seven digits at every width: 6.128598 against 6.128598, 2.786087 against 2.786087, and so on down the sweep. Those are two different computations — one is the condition number of the preconditioned matrix and the other is how much the sketch distorts A’s column space — and they agree in every digit printed. That identity is the whole reason the preconditioned conditioning has no κ(A) in it: what it depends on is a property of the sketch, and the sketch does not know what it was applied to.

What it buys, in the quantity a user waits for #

The unpreconditioned curve is the rate the condition number predicts doing exactly what that essay says it must: a Krylov method’s step count grows like √κ, and the growth is visible over four of the five points and becomes non-convergence at the fifth.

The preconditioned curve does not know what κ(A) is. Ten steps at 10², ten at 10¹⁰.

That is a stronger claim than “preconditioning helps”, which any improvement would satisfy, and it is asserted as such: the spread of the preconditioned counts across the whole sweep is at most three steps.

Where the randomness went #

The half that makes this worth an essay rather than a note, and the half the dimension does not appear does not reach.

sketchAndSolve returns a different answer at every seed. The spread over twelve seeds, measured on a κ = 10⁶ problem with a 4n-row sketch, is 12.9 relative to the exact solution — an answer with no correct digits, and a different wrong answer each time.

sketchAndPrecondition on the same problem with the same sketch width returns the same answer at every seed to 6.7·10⁻¹⁰. What moves with the seed is the step count, between ten and eleven.

The randomness has been moved out of the answer and into the cost. A bad sketch — one that happens to embed the column space poorly — gives a worse preconditioner, so the iteration takes more steps, and the answer it converges to is the same one. That is the only place on this site where a probabilistic guarantee buys a deterministic result, and it is worth being precise about the mechanism: the sketch’s job is to produce an R, and in exact arithmetic any invertible R gives the right answer — the preconditioned problem has the same solution as the original, for every R.

How far “any invertible R” goes #

That is a theorem about the algebra and this site’s business is what happens to it in the arithmetic. Replacing the sketch’s R with triangular matrices of increasing conditioning, on the same κ = 10⁶ problem, and measuring the answer against a direct QR least-squares solve:

   κ(R)      κ(AR⁻¹)     steps      error against a direct solve
  1.2·10⁶      2.4         10             4.8·10⁻¹⁰      ← the sketch's own R
  1.2          1.1·10⁶     36             3.2·10⁻¹⁰      ← the identity
  8.0·10²      1.3·10⁸    >400            3.3·10⁻⁹
  2.1·10⁶      1.9·10¹¹   >400            5.2·10⁻⁷
  2.0·10¹⁰     1.1·10¹⁵   >400            1.8·10⁻⁴
  1.9·10¹⁹     9.6·10²³   >400            1.00

A sufficiently bad R costs the answer and not only the steps. The error tracks κ(AR⁻¹)·u — to within a factor of a few over ten orders of magnitude — and reaches a hundred per cent by κ(AR⁻¹) ≈ 10²⁴. So the sentence above holds in exact arithmetic and the arithmetic here has the same opinion about R that it has about everything else.

Two things follow, and the second is the more useful.

κ® is not the quantity. The sketch’s own R has κ® = 1.2·10⁶, as ill-conditioned as A, and gives κ(AR⁻¹) = 2.4 — which is the entire method. A preconditioner is judged by what it does to the problem, not by what it is.

And the headline result and the caveat at the end of this essay are one condition rather than two. The section on where the method does not apply lists the subspace embedding as a limit: l must exceed n by a constant factor or R can be singular. What the table above says is that the embedding is also what makes the randomness cost-only. The bound κ(AR⁻¹) ≤ (1+ε)/(1−ε) is what holds the accuracy term at u; without it, κ(AR⁻¹) is unbounded and the error is unbounded with it. The randomness moves into the cost because the sketch embeds, and a sketch that does not embed moves it back into the answer.

The second row of the table is the one worth keeping for a different reason. The identity is a perfectly valid “preconditioner” — it is invertible, the preconditioned problem is the original problem, and the answer comes back right to 3.2·10⁻¹⁰. It converges in thirty-six steps rather than ten. So the essay’s claim is exactly true for the R that does nothing, and the accuracy only starts to move once κ(AR⁻¹) climbs past the original problem’s own condition number. The dangerous region is not “R is not the sketch’s R”; it is “R makes the problem harder than it was”, and a preconditioner has to be actively bad rather than merely unhelpful to reach it.

That reframes what the sketch is insuring against. It is not insuring the answer against a bad draw — a bad draw would have to produce an R that is worse than no preconditioner at all by eight orders, which the embedding bound rules out by a wide margin. It is buying the ten steps, and the accuracy comes along because the same bound that makes the iteration fast makes the preconditioned problem no worse conditioned than the original.

What is worth carrying out of this is the general shape rather than the particular numbers. A transformation that is invertible in the algebra is invertible in the arithmetic only to the extent that it is well conditioned, and a method that reasons about correctness by pointing at invertibility has an unstated conditioning hypothesis in it. Here the hypothesis happens to be supplied — by the embedding bound, several sections away and labelled as a limit rather than as a premise — which is the ordinary situation for such hypotheses and the reason they are worth locating.

What “the same answer” means here #

Not “identical to rounding”. The preconditioned answer and a direct QR least-squares solve differ by about κ(A)·u at every κ: 3.7·10⁻¹⁵ at 10², 4.3·10⁻¹⁰ at 10⁶, 5.7·10⁻⁶ at 10¹⁰.

That is not a defect of either route. It is the accuracy the problem allows, and the site’s own identity is what says so. Two backward-stable routes to an ill-conditioned problem agree to κ times the unit roundoff and no better, and asserting a fixed tolerance instead would be asserting that the conditioning does not exist.

assertThePreconditionedIterationCountIsFlat asserts the gap is below 30·κ(A)·u at every κ and that the ratio of gap to κu is within a factor of a hundred across the whole sweep — the second being the claim that the gap tracks κu rather than merely being under it.

Why the width is the only knob #

The drag runs the sketch from 2n rows to 10n. It is the one parameter that moves κ(AR⁻¹), because the distortion ε in (1+ε)/(1−ε) is what the width buys, and the flatness against κ(A) holds at every width.

The cost is the trade. A sketch of l rows costs l products with the whole matrix to form SA, plus O(ln²) for its QR. A wider sketch is a better preconditioner and a more expensive one, and the optimum is a balance between one-off cost and per-iteration cost that depends on how many iterations would otherwise be needed — which is the same shape of decision as changing the condition number on purpose, where an incomplete factorisation is paid for once and saves iterations afterwards.

What is actually paid for, in operations #

The accounting, because “it converges in ten steps” is not by itself a claim about time.

A direct least-squares solve by Householder QR costs about 2mn². For m = 200 and n = 10 that is 40,000 operations, and on a problem that shape nobody sketches anything.

The interesting shape is m enormous and n moderate — a regression with a hundred million rows and a hundred columns, which is where the method was invented. There:

• The sketch. SA with l = 4n rows costs O(lmn) with a dense Gaussian S, which is worse than the direct solve. That is why nobody uses a dense Gaussian: the sketches that ship are subsampled randomised Hadamard transforms at O(mn log m), or sparse embeddings — CountSketch — with one nonzero per column, at O(nnz(A)). The theory in this essay does not care which; the distortion is what it needs, and all three provide it at their own l.
• Its QR. O(ln²) = O(n³), independent of m. Free.
• The iteration. Two products with A per LSQR step, O(mn) each, times about ten steps.

So the total is one pass to sketch plus twenty passes over A, against the direct method’s 2mn² — and the crossing is at n ≈ 20. Above that the sketched route wins, and it wins by a factor that grows with n.

The number that makes it worth doing is the ten, and the ten is what the flatness in the hero figure buys. An unpreconditioned LSQR on a κ = 10¹⁰ problem does not converge at all, so the comparison there is not a factor — it is between an answer and no answer.

Where it does not apply #

Three honest limits, because the flatness above is unqualified and the method is not.

The subspace embedding has to hold. l must exceed n by a constant factor, and the constant depends on the sketch: a Gaussian needs l ≳ n, a Hadamard l ≳ n log n, a sparse embedding somewhere between. Below that, R can be singular and the preconditioner does not exist — sketchPreconditioner returns singular: true rather than a matrix of infinities, and the figure refuses a sketch narrower than the subspace it has to embed.

The matrix must be tall. The whole argument is about SA being much smaller than A, which needs m ≫ n. For a square system there is nothing to sketch.

And it is least squares, not a general solve. The preconditioner is built from the column space, and AR⁻¹ having a small condition number is a statement about A’s columns. There are sketched preconditioners for square systems and they are a different construction with different guarantees.

The distinction this generalises to #

There are two things to do with an approximation, and they are not variations on each other.

Use it as the answer. The error in the answer is the error in the approximation, and improving the answer means improving the approximation, which costs what approximations cost.

Use it to accelerate an exact method. The error in the answer is the exact method’s, and the approximation controls only how long that method takes. Improving it is optional.

The second is what a preconditioner is, and it is why preconditioning is the one place in numerical analysis where a wild guess is a respectable input: changing the condition number on purpose uses an incomplete factorisation whose residual is not small, and nobody minds, because it is not the answer. Sketching arrived in this subject through the first use and the second one is where it belongs.

Why the distortion is what the width buys #

The bound κ(AR⁻¹) ≤ (1+ε)/(1−ε) deserves one paragraph of unpacking, because ε is the only quantity in this essay that a reader has to bring in from elsewhere.

A subspace embedding with distortion ε satisfies (1−ε)‖Ax‖ ≤ ‖SAx‖ ≤ (1+ε)‖Ax‖ for every x. Set y = R⁻¹x; since SA = QR with Q orthonormal, ‖SAy‖ = ‖Ry‖ = ‖x‖. So (1−ε)‖AR⁻¹x‖ ≤ ‖x‖ ≤ (1+ε)‖AR⁻¹x‖, which says every singular value of AR⁻¹ lies between 1/(1+ε) and 1/(1−ε), and their ratio is the bound.

Two things follow that are worth having explicitly. The bound is on the whole spectrum of AR⁻¹, not merely on its extremes, so the preconditioned problem has all its singular values clustered rather than merely a bounded ratio — which is what makes ten LSQR steps rather than forty the right expectation. And nowhere in the derivation does A’s own spectrum appear, which is the two-line observation the hero figure measures to nine digits.

What happens if the sketch is bad #

The failure modes are worth naming because they are unusually mild.

A distortion larger than expected gives a worse-conditioned preconditioned problem and more iterations. The answer is unaffected.

A rank-deficient sketch — l < n, or an unlucky draw at l ≈ n — gives a singular R and there is no preconditioner at all. sketchPreconditioner reports it rather than returning infinities, and the repair is to draw again or to widen.

A sketch that is not an embedding of this subspace — a structured S on a matrix adversarially aligned with its structure — gives the first failure and not a wrong answer, because the argument that AR⁻¹y = b has the same solution as Ax = b uses nothing about S beyond R being invertible.

So the whole family of things that can go wrong costs iterations. That is unusual enough among the randomised methods on this site to be the reason this one is worth the essay.

The same idea, elsewhere in the subject #

Once the pattern is named — approximate something cheaply, and use the approximation to accelerate an exact method rather than to replace it — it turns out to be most of what preconditioning is.

An incomplete factorisation is a factorisation that is wrong on purpose, and changing the condition number on purpose measured its residual, which is not small. Nobody minds, because it is not the answer.

A coarse-grid correction is a solve of a different problem, and the coarse problem is a different problem is about how different it is allowed to be. Again: not the answer.

A low-rank update to an approximate inverse, a domain decomposition that ignores the coupling between subdomains, a physics-based preconditioner built from a simplified model — all the same shape.

What is new here is where the approximation comes from. Every one of those is an approximation built by leaving something out of the problem, which requires knowing what can be left out. A sketch is built by multiplying by a random matrix, which requires knowing nothing at all — and the guarantee it comes with is stronger than any of them, because it does not mention the operator.

What is worth carrying #

A sketch used as a preconditioner leaves a condition number with no κ(A) in it — exactly, not approximately, because the spectrum cancels out of the similarity.

So the iteration count stops depending on the conditioning, which is the quantity the whole Krylov field is organised around.

And the randomness moves from the answer to the cost. A bad draw costs steps rather than digits, which is the difference between a probabilistic algorithm and a probabilistic answer.

The accuracy cost of sketch-and-solve was never the sketch’s. It was the decision to keep the small problem’s answer, and the same sketch used the other way pays nothing for it.