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.

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.

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 any invertible R gives the right answer — the preconditioned problem has the same solution as the original, for every R. What the sketch controls is purely how fast the iteration finds it.

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.