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

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.
37 min read 28 figures Where the algebra stops being the arithmeticMeasured, not assertedAssertions that reject

Worth reading first: The dimension does not appear · The projection and the right angle · A constraint is a weight at infinity.

Every guarantee this field publishes has one shape. A random S with enough rows is a subspace embedding: for every x in a subspace,

(1 − ε)‖Ax‖ ≤ ‖SAx‖ ≤ (1 + ε)‖Ax‖

and therefore a minimiser of ‖S(Ax − b)‖ has an objective within (1 + ε) of the true minimum. The sketch that is not the answer, the bound that holds with probability, the dimension that does not appear — all of them are statements about a norm being preserved to within a multiplicative factor.

An equality constraint is a statement that a quantity is zero, and a multiplicative distortion says nothing about zero: it maps a residual of size δ to something of size δ, and a comparable size is exactly what is not wanted.

How nearly the constraint is satisfied, when a sketch is allowed to see it and when it is notSketching reduces a least-squares problem to 8 rows and keeps its minimiser within (1 + ε) of the original's. That is a statement about a norm, and an equality constraint is a statement that a quantity is zero, which no multiplicative distortion preserves. Kept out of the sketch and imposed exactly, the constraint holds to 1.68·10⁻¹⁶ at every weight. Written as a weight and sketched along with everything else, it holds at 1.747·10⁻⁸ at τ = 10⁸ — and the slope is the finding: the violation falls as 1/τ, one power, where the unsketched weighted problem's falls as 1/τ². The sketch costs exactly half the decades the weight was buying, and buying them back means squaring τ, which the previous figure says the arithmetic stops allowing.2468101210⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²log₁₀ τ‖Bx − d‖ / ‖d‖sketched with the objectiveweighted, not sketchedkept out of the sketchone power instead of twokept out — feasibility1.7·10⁻¹⁶sketched at τ = 10⁸1.7·10⁻⁸unsketched at τ = 10⁸1.7·10⁻¹⁶objective ÷ optimum1.2a sketch preserves a normand a constraint is not one
Fig. 1 The same constraint, imposed two ways, over ten decades of weight. The upper line is the sketch seeing it and the lower one is the sketch not seeing it.

The two ways to sketch a constrained problem

Minimise ‖Ax − b‖ subject to Bx = d, and reduce the objective’s rows from twelve to l with a Gaussian sketch S.

Keep the constraint out. Solve minimise ‖S(Ax − b)‖ subject to Bx = d, with the constraint imposed exactly. The sketch touches only the objective, and it is the objective’s guarantee that applies.

Write the constraint as a weight and sketch everything. This is the previous essay’s construction: stack [τB; A] and sketch the whole stacked system, because to a routine that has been handed a least-squares problem the constraint rows are just more rows.

The second is not a straw man. It is what happens by default when a code implements constraints by weighting — which the previous essay explains is common, because it needs no special solver — and then reaches for sketch-and-solve to make a large problem affordable.

Minimise ‖Ax − b‖ subject to Bx = d, solved as a weighted least-squares problem, three waysStack the constraint on top of the objective with a weight τ and solve the ordinary least-squares problem that results. In exact arithmetic the answer approaches the constrained one like 1/τ² — measured here as exactly four orders of error per two decades of τ, against a solution computed in BigInt rationals from the problem's own optimality conditions. What stops the limit is the solver and not the problem. The normal equations on the weighted problem form entries of size τ², so the constraint block is lost once τ² passes 1/u: the last weight at which they are within an order of the right answer is 10⁴ here, against 1/√u = 6.71·10⁷, and by τ = 10¹⁴ they are wrong by 14.3. Householder QR has no such ceiling and is at 4.8·10⁻¹⁵ at the same weight. Classical Gram–Schmidt is worse than either, at 4.9·10¹⁰.0246810121410⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹10⁴10⁷10¹⁰log₁₀ τ — the weight on the constraintrelative error against the exact answerτ = 1/√uGram–Schmidtnormal equationsHouseholder QRthe ceiling is the method'sHouseholder, τ = 10¹⁴4.8·10⁻¹⁵normal equations14Gram–Schmidt4.9·10¹⁰1/√u6.7·10⁷a constraint is a weight at infinityand the solver decides how far infinity is
Fig. 2 The construction being sketched, from the previous essay, with no sketch anywhere.

The measurement, which did not come out as predicted

The prediction from the paragraph above is that sketching the weighted problem destroys the constraint outright. It does not, and the number is more interesting than the prediction was.

At l = 8 and τ = 10⁸, over twelve independent sketches:

constraint kept out of the sketch feasibility 1.7·10⁻¹⁶ constraint written as a weight, sketched 1.7·10⁻⁸ the same weight with no sketch 1.7·10⁻¹⁶

Eight orders between the first two. But the sketched violation is not O(1) — it falls with τ, and the slope is the finding: one power of τ, where the unsketched weighted problem gives two. Measured over ten decades, the sketched feasibility falls by ten orders and the unsketched one by twenty, until the second reaches the rounding level and stops.

So the sketch does not destroy the constraint. It demotes it from 1/τ² to ε/τ, and ε is the sketch’s own distortion. The sketch costs exactly half the decades the weight was buying.

How nearly the constraint is satisfied, when a sketch is allowed to see it and when it is notSketching reduces a least-squares problem to 24 rows and keeps its minimiser within (1 + ε) of the original's. That is a statement about a norm, and an equality constraint is a statement that a quantity is zero, which no multiplicative distortion preserves. Kept out of the sketch and imposed exactly, the constraint holds to 1.19·10⁻¹⁶ at every weight. Written as a weight and sketched along with everything else, it holds at 8.769·10⁻⁹ at τ = 10⁸ — and the slope is the finding: the violation falls as 1/τ, one power, where the unsketched weighted problem's falls as 1/τ². The sketch costs exactly half the decades the weight was buying, and buying them back means squaring τ, which the previous figure says the arithmetic stops allowing.2468101210⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²log₁₀ τ‖Bx − d‖ / ‖d‖sketched with the objectiveweighted, not sketchedkept out of the sketchone power instead of twokept out — feasibility1.2·10⁻¹⁶sketched at τ = 10⁸8.8·10⁻⁹unsketched at τ = 10⁸1.7·10⁻¹⁶objective ÷ optimum1.1a sketch preserves a normand a constraint is not one
Fig. 3 With a much wider sketch, where the distortion is smaller and the line drops bodily — and the slope does not change.

Why half

The weighted problem’s feasibility is 1/τ² because the solution is a stationary point of an exact quadratic, and the leading error term is second order in 1/τ. A sketch perturbs that quadratic by a relative ε — it replaces AᵀA by AᵀSᵀSA, which is (1 + O(ε)) times the original in the relevant subspace — and the perturbed stationary point’s feasibility is first order in the perturbation divided by the weight: ε/τ.

That is the same “a second-order cancellation is destroyed by a first-order perturbation” that this collection has met before. An energy-minimising interpolation matches a closed form to four digits where its assumption holds and separates where it does not; a stationary point of a residual curve is flat and therefore robust until something breaks the symmetry that made it flat. Feasibility at 1/τ² is a flat minimum, and ε moves it off the bottom.

The consequence is a design rule with a number in it. To recover the decades a sketch costs, τ must be squared — and the previous essay shows that the arithmetic stops allowing that at 1/√u for a solver that forms a Gram matrix and at 1/u for one that does not. So the sketch has consumed a resource that was already bounded.

Sketch distortion against sketch width, for 60 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. 4 The ε that is doing the demotion, measured in the field’s own terms.

What the sketch size does, and does not

The slider moves l from four rows to twenty-four, and reading it correctly separates a constant from an exponent.

The constant moves. At l = 4 the sketched feasibility at τ = 10⁸ is 5.25·10⁻⁸ and at l = 10 it is 1.21·10⁻⁸, roughly a factor of four for a factor of 2.5 in the sketch size — which is the ε of a Gaussian sketch falling like 1/√l, as the field’s bounds say it should.

The exponent does not. At every sketch size the violation falls as one power of τ, and no amount of oversampling turns that into two. That is what makes the halved exponent a property of sketching rather than of a sketch that was too small: a wider sketch distorts less, and the distortion enters the feasibility linearly at every width.

So a code that noticed the constraint violation and responded by oversampling would be buying square roots against a shortfall of decades. Doubling l buys a factor of 1.4; recovering what the sketch cost needs a factor of τ, which is 10⁸.

How nearly the constraint is satisfied, when a sketch is allowed to see it and when it is notSketching reduces a least-squares problem to 16 rows and keeps its minimiser within (1 + ε) of the original's. That is a statement about a norm, and an equality constraint is a statement that a quantity is zero, which no multiplicative distortion preserves. Kept out of the sketch and imposed exactly, the constraint holds to 1.68·10⁻¹⁶ at every weight. Written as a weight and sketched along with everything else, it holds at 1.259·10⁻⁸ at τ = 10⁸ — and the slope is the finding: the violation falls as 1/τ, one power, where the unsketched weighted problem's falls as 1/τ². The sketch costs exactly half the decades the weight was buying, and buying them back means squaring τ, which the previous figure says the arithmetic stops allowing.2468101210⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²log₁₀ τ‖Bx − d‖ / ‖d‖sketched with the objectiveweighted, not sketchedkept out of the sketchone power instead of twokept out — feasibility1.7·10⁻¹⁶sketched at τ = 10⁸1.3·10⁻⁸unsketched at τ = 10⁸1.7·10⁻¹⁶objective ÷ optimum1.2a sketch preserves a normand a constraint is not one
Fig. 5 A generous sketch, where the line has dropped and its slope is unchanged.

The control: the objective does exactly what it should

A page reporting a failure of a sketch has to show that the sketch is otherwise working, or the measurement is about a sketch that was too small rather than about constraints.

With the constraint kept out, the objective ratio — the sketched solution’s ‖Ax − b‖ against the true constrained minimum — falls with the sketch size as the bound says it should: 3.49 at l = 4, 1.80 at l = 6, 1.24 at l = 8, 1.15 at l = 10. Within a quarter of the optimum with twelve rows sketched down to eight, on a problem whose subspace is six-dimensional.

And the feasibility in that arrangement is at the rounding level at every sketch size, including l = 4 where the objective is off by a factor of three and a half. The two quantities are completely separate: the sketch is free to be bad at the thing it guarantees and is exactly right at the thing it never touches.

That separation is the whole content of the page in one sentence. What a sketch is allowed to see decides which of a problem’s requirements survive it, and the decision is made when the arrays are stacked rather than when the guarantee is quoted.

The error of a rank-4 Tucker representation built from a sketch, against the columns of oversamplingThe flat line is the deterministic decomposition — d matrix SVDs — at 8.81·10⁻⁴, and nothing random can go below it, since every curve here is a projection onto a subspace of the same size. The upper two are medians over five seeds: a dense Gaussian sketch, which the randomised field's bounds cover, and a Khatri–Rao sketch, whose columns are outer products of small random vectors and which no bound in that field applies to. With no oversampling the dense sketch is 3.65 times the deterministic answer; at twelve extra columns it is 1.15. The structured one costs 6.8 per cent more at four extra columns and 9.5 per cent at twelve — measured, because there is nothing else to say about it.-113579111310⁻³10⁻²extra columns in the sketchrelative errora Khatri–Rao sketch: no bound covers ita dense Gaussian sketchthe decomposition, which nothing beatsrank 4, five seedsdeterministic8.8·10⁻⁴dense, p = 00.0032dense, p = 120.001structured, p = 120.0011structured ⁄ dense1.1a bound and a measurementand only one of them is available
Fig. 6 The objective improving with the sketch size, in the field’s own picture of it.

What the guarantee actually promises

It is worth restating the subspace-embedding property to see precisely where the constraint falls outside it.

The property is about ‖SAx‖ against ‖Ax‖ for x in a subspace, and it is multiplicative on both sides. If ‖Bx − d‖ is 10⁻¹⁶, a distortion of (1 ± ε) leaves it at 10⁻¹⁶ — the guarantee is perfectly good and perfectly useless, because it says a small number stays small and the requirement was that a number be zero.

What breaks is not the guarantee but the inference from it. In the weighted construction the constraint is enforced by being expensive to violate, and the sketch changes what “expensive” means: SτB is not τSB in any useful sense, because the sketch mixes constraint rows into the same l rows as objective rows and the two are then indistinguishable to the solver. The weight survives — which is why the violation still falls with τ — and the separation does not.

That is the same failure mode as the second essay in the constraint field records for an elimination, and as the componentwise essay records for a Schur complement: a transformation that is exact in the algebra destroys a structural distinction the numerics were relying on. Three fields, one shape.

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. 7 The field’s own statement about what a random projection cannot supply.

The refusals

The claim to close is the natural over-reading of the field’s central guarantee: a sketch that preserves a least-squares problem’s objective to within (1 + ε) preserves everything about the problem to within (1 + ε), constraints included. The assertion is fed the pair of feasibilities — 1.7·10⁻¹⁶ and 1.7·10⁻⁸ on one problem at one weight — and required to reject it.

The second refusal is about the slope rather than the values. It is fed the sketched feasibilities across ten decades of τ and required to reject the claim that they fall like the unsketched ones. They fall by ten orders where the others fall by twenty, and asserting the exponent rather than the ratio is what makes the finding a law rather than a pair of numbers.

Both are checked at several sketch sizes, because the whole risk in a randomised measurement is that a single draw is unrepresentative: every number on the page is a median over twelve independent sketches, and the seed is stated.

How nearly the constraint is satisfied, when a sketch is allowed to see it and when it is notSketching reduces a least-squares problem to 4 rows and keeps its minimiser within (1 + ε) of the original's. That is a statement about a norm, and an equality constraint is a statement that a quantity is zero, which no multiplicative distortion preserves. Kept out of the sketch and imposed exactly, the constraint holds to 4.76·10⁻¹⁶ at every weight. Written as a weight and sketched along with everything else, it holds at 5.254·10⁻⁸ at τ = 10⁸ — and the slope is the finding: the violation falls as 1/τ, one power, where the unsketched weighted problem's falls as 1/τ². The sketch costs exactly half the decades the weight was buying, and buying them back means squaring τ, which the previous figure says the arithmetic stops allowing.2468101210⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²log₁₀ τ‖Bx − d‖ / ‖d‖sketched with the objectiveweighted, not sketchedkept out of the sketchone power instead of twokept out — feasibility4.8·10⁻¹⁶sketched at τ = 10⁸5.3·10⁻⁸unsketched at τ = 10⁸1.7·10⁻¹⁶objective ÷ optimum3.5a sketch preserves a normand a constraint is not one
Fig. 8 At the smallest sketch the figure draws, where the objective is off by a factor of three and the kept-out constraint is still exact.

And whether the answer is even feasible

Feasibility is a quantity this field does not usually report, and the reason it has to be reported here is worth a paragraph.

A sketched least-squares solve returns a vector whose objective is nearly optimal. Whether that vector is admissible — whether it satisfies the constraints the problem came with — is a separate question, and in an unconstrained problem there is nothing to ask. As soon as a constraint exists, an answer has two ways to be wrong and the field’s guarantee covers one of them.

The distinction matters most where the constraint is not a numerical device but a physical requirement. A flow that must balance at a node, a set of probabilities that must sum to one, a displacement field that must vanish at a support: a solution that is 10⁻⁸ off those is not a slightly worse answer, it is an answer of a different kind, and downstream code that assumes the constraint will behave badly rather than inaccurately.

So a page in this field about a constrained problem has to carry a feasibility column, and the measurement here is that the column reads 10⁻¹⁶ or 10⁻⁸ depending on a choice made when the arrays were stacked. That choice is invisible in the objective, which is within a quarter of optimal either way.

How nearly the constraint is satisfied, when a sketch is allowed to see it and when it is notSketching reduces a least-squares problem to 6 rows and keeps its minimiser within (1 + ε) of the original's. That is a statement about a norm, and an equality constraint is a statement that a quantity is zero, which no multiplicative distortion preserves. Kept out of the sketch and imposed exactly, the constraint holds to 1.68·10⁻¹⁶ at every weight. Written as a weight and sketched along with everything else, it holds at 1.841·10⁻⁸ at τ = 10⁸ — and the slope is the finding: the violation falls as 1/τ, one power, where the unsketched weighted problem's falls as 1/τ². The sketch costs exactly half the decades the weight was buying, and buying them back means squaring τ, which the previous figure says the arithmetic stops allowing.2468101210⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²log₁₀ τ‖Bx − d‖ / ‖d‖sketched with the objectiveweighted, not sketchedkept out of the sketchone power instead of twokept out — feasibility1.7·10⁻¹⁶sketched at τ = 10⁸1.8·10⁻⁸unsketched at τ = 10⁸1.7·10⁻¹⁶objective ÷ optimum1.8a sketch preserves a normand a constraint is not one
Fig. 9 The column, at a sketch small enough that the objective is visibly suboptimal and the kept-out feasibility is not.

What to do instead, which is cheap

The repair is the one the measurement points at: keep the constraint out of the sketch and impose it exactly. Concretely, sketch A and b to l rows, then solve the constrained problem minimise ‖SAx − Sb‖ subject to Bx = d — which is a saddle-point system of size n + m with (SA)ᵀ(SA) in its (1, 1) block, and which the constraint field has two methods for.

The cost is unchanged in the part that matters. The expensive object was the m₁ × n data matrix and it has been reduced to l × n; the constraint block was small and stays small. What is given up is the ability to use a plain least-squares routine, which was the reason the weighting construction was attractive in the first place — so the choice is between a special solver and a halved exponent, stated as a number rather than as a preference.

There is a second repair for a code that cannot change its solver: project first. Compute a null-space basis for B once, substitute x = x_p + Zv, and sketch the resulting unconstrained problem in v. The constraint is then satisfied by construction whatever the sketch does, and the basis essay says which basis to use.

Three bases for the same null space, at 10 unknowns and 4 constraintsThe same constrained problem solved three times, differing only in which basis Z is used for the null space of A. The orthonormal basis, from a QR of Aᵀ, has κ(Z) = 1 exactly and is dense — 100 per cent of its entries are nonzero. The fundamental basis built on the first 4 columns has κ(Z) = 4.436, and its reduced Hessian comes out at 83.77, which is κ(Z)² to within a factor of 4.26 — the square attained rather than bounded. Its answer is wrong by 1.26·10⁻¹⁵, against 1.29·10⁻¹⁵ for the orthonormal one. Choosing the same kind of basis by pivoting instead gives κ(Z) = 2.258, an error of 1.41·10⁻¹⁵, and the same 50 per cent density: all of the sparsity and none of the loss.κ(A) = 10⁶ throughout · κ(H) = 100 · the answer is the same answer for every basisorthonormal — κ(Z)1κ(ZᵀHZ)32relative error1.29·10⁻¹⁵first m basic — κ(Z)4.44κ(ZᵀHZ)83.8relative error1.26·10⁻¹⁵pivoted basic — κ(Z)2.26κ(ZᵀHZ)43.1relative error1.41·10⁻¹⁵what the choice costsdensity, orthonormal1density, fundamental0.5κ(ZᵀHZ) ÷ κ(Z)², naive4.3error, pivoted choice1.4·10⁻¹⁵every one of them is a basisand one of them loses fourteen digits
Fig. 10 The second repair’s ingredient, from the orthogonality field.

The exact answer, and why it exists

Every number on this page is a comparison against a constrained solution that no sketch was involved in producing, and it is available for the same reason the previous essay’s was.

The optimality conditions of the unsketched constrained problem are a saddle-point system with AᵀA in the (1, 1) block. Every entry of that system is a double, every double is a dyadic rational, and BigInt elimination on rationals rounds nowhere. So the reference is the exact solution of the problem the machine is holding, computed once, and the twelve sketches are measured against it rather than against each other.

That matters more in a randomised measurement than in a deterministic one. A comparison between two sketched answers would be measuring the variance of the sketch and calling it an error, and a comparison against an averaged sketched answer would be worse. With an exact reference the median over twelve draws is a median of twelve errors rather than a spread of twelve guesses, and the quantity being reported is what it says.

The exact solution of a 13×13 Hilbert system beside the computed oneTwo columns of numbers: the exact answer, which is the integers one to thirteen, and the answer double-precision elimination returns, with the number of correct digits beside each.H13 x = b, b formed exactly so that x = (1, 2, …, 13)12345678910111213exact1.00002.00003.00133.97865.18864.993010.46720.048921.2657-2.575319.21478.906013.5113computed6.6 correct digits4.8 correct digits3.4 correct digits2.3 correct digits1.4 correct digit0.8 correct digitno correct digitsno correct digitsno correct digitsno correct digitsno correct digits0.6 correct digit1.4 correct digitbackward error2.2·10⁻¹⁷κ = 1.7·10¹⁸The algorithm solved a neighbouring problem perfectly. That problem's answer is this one.right-hand side built in BigInt rationalsthe truth is known
Fig. 11 The discipline in the form the collection has had it longest, where the entries were rationals before they were stored.

Where this leaves the field’s guarantee

Nothing on this page weakens the subspace-embedding property, and it is worth saying so plainly because the measurement reads like a failure of sketching.

The guarantee is about the objective. It is measured here doing exactly what it promises, at every sketch size, on the same problem. The failure is in an inference nobody made explicitly: that a problem’s requirements are all of the same kind, and that a technique guaranteed for one kind applies to a problem containing another.

The general lesson for the field is a question to ask before sketching anything. What does this problem require that is not a norm? An equality constraint is one such requirement. A non-negativity constraint is another, and a sketch has nothing to say about it either. An integrality requirement is a third. Each of them has to be imposed outside the sketch or abandoned, and the guarantee will not mention them.

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. 12 The field’s guarantee working on the quantity it is about.

What the anchor has now measured

Six essays into sketching, the pattern of what a sketch buys and what it does not is worth collecting.

It buys a cost: the same quality for fewer passes over the data, which is the anchor’s opening claim and is what the technique is for. It buys a bound whose form is unusual for this collection — one that holds with a probability rather than always. It does not buy structure the matrix does not have: on a flat spectrum it finds nothing, and neither does anything else.

And now: it does not buy anything about a requirement that is not a norm. That is a different kind of limit from the flat-spectrum one. There, the sketch works exactly as advertised and there is nothing worth finding; here, the sketch works exactly as advertised and the problem had a second requirement the advertisement never mentioned.

Both are worth having written down in the same anchor, because they are the two ways a guarantee can be true and unhelpful.

The error of a rank-4 Tucker representation built from a sketch, against the columns of oversamplingThe flat line is the deterministic decomposition — d matrix SVDs — at 8.81·10⁻⁴, and nothing random can go below it, since every curve here is a projection onto a subspace of the same size. The upper two are medians over five seeds: a dense Gaussian sketch, which the randomised field's bounds cover, and a Khatri–Rao sketch, whose columns are outer products of small random vectors and which no bound in that field applies to. With no oversampling the dense sketch is 3.65 times the deterministic answer; at twelve extra columns it is 1.15. The structured one costs 6.8 per cent more at four extra columns and 9.5 per cent at twelve — measured, because there is nothing else to say about it.-113579111310⁻³10⁻²extra columns in the sketchrelative errora Khatri–Rao sketch: no bound covers ita dense Gaussian sketchthe decomposition, which nothing beatsrank 4, five seedsdeterministic8.8·10⁻⁴dense, p = 00.0032dense, p = 120.001structured, p = 120.0011structured ⁄ dense1.1a bound and a measurementand only one of them is available
Fig. 13 The anchor’s usual reading, on the quantity the guarantee is about.

At other settings

How nearly the constraint is satisfied, when a sketch is allowed to see it and when it is notSketching reduces a least-squares problem to 6 rows and keeps its minimiser within (1 + ε) of the original's. That is a statement about a norm, and an equality constraint is a statement that a quantity is zero, which no multiplicative distortion preserves. Kept out of the sketch and imposed exactly, the constraint holds to 1.68·10⁻¹⁶ at every weight. Written as a weight and sketched along with everything else, it holds at 1.841·10⁻⁸ at τ = 10⁸ — and the slope is the finding: the violation falls as 1/τ, one power, where the unsketched weighted problem's falls as 1/τ². The sketch costs exactly half the decades the weight was buying, and buying them back means squaring τ, which the previous figure says the arithmetic stops allowing.2468101210⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²log₁₀ τ‖Bx − d‖ / ‖d‖sketched with the objectiveweighted, not sketchedkept out of the sketchone power instead of twokept out — feasibility1.7·10⁻¹⁶sketched at τ = 10⁸1.8·10⁻⁸unsketched at τ = 10⁸1.7·10⁻¹⁶objective ÷ optimum1.8a sketch preserves a normand a constraint is not one
Fig. 14 Six rows, where the objective is 1.80 times the optimum and the feasibility is unchanged.
How nearly the constraint is satisfied, when a sketch is allowed to see it and when it is notSketching reduces a least-squares problem to 12 rows and keeps its minimiser within (1 + ε) of the original's. That is a statement about a norm, and an equality constraint is a statement that a quantity is zero, which no multiplicative distortion preserves. Kept out of the sketch and imposed exactly, the constraint holds to 1.19·10⁻¹⁶ at every weight. Written as a weight and sketched along with everything else, it holds at 1.587·10⁻⁸ at τ = 10⁸ — and the slope is the finding: the violation falls as 1/τ, one power, where the unsketched weighted problem's falls as 1/τ². The sketch costs exactly half the decades the weight was buying, and buying them back means squaring τ, which the previous figure says the arithmetic stops allowing.2468101210⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²log₁₀ τ‖Bx − d‖ / ‖d‖sketched with the objectiveweighted, not sketchedkept out of the sketchone power instead of twokept out — feasibility1.2·10⁻¹⁶sketched at τ = 10⁸1.6·10⁻⁸unsketched at τ = 10⁸1.7·10⁻¹⁶objective ÷ optimum1.2a sketch preserves a normand a constraint is not one
Fig. 15 Twelve, where the sketch is no reduction at all and the demotion still happens.
How nearly the constraint is satisfied, when a sketch is allowed to see it and when it is notSketching reduces a least-squares problem to 16 rows and keeps its minimiser within (1 + ε) of the original's. That is a statement about a norm, and an equality constraint is a statement that a quantity is zero, which no multiplicative distortion preserves. Kept out of the sketch and imposed exactly, the constraint holds to 1.68·10⁻¹⁶ at every weight. Written as a weight and sketched along with everything else, it holds at 1.259·10⁻⁸ at τ = 10⁸ — and the slope is the finding: the violation falls as 1/τ, one power, where the unsketched weighted problem's falls as 1/τ². The sketch costs exactly half the decades the weight was buying, and buying them back means squaring τ, which the previous figure says the arithmetic stops allowing.2468101210⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²log₁₀ τ‖Bx − d‖ / ‖d‖sketched with the objectiveweighted, not sketchedkept out of the sketchone power instead of twokept out — feasibility1.7·10⁻¹⁶sketched at τ = 10⁸1.3·10⁻⁸unsketched at τ = 10⁸1.7·10⁻¹⁶objective ÷ optimum1.2a sketch preserves a normand a constraint is not one
Fig. 16 And sixteen, where it is an expansion.
The same Householder QR on the same rows, in two ordersOne weighted least-squares problem, one factorisation, and the only difference is whether the 2 heavily weighted constraint rows are placed above the 12 data rows or below them. The algebra is identical, the operation count is identical, the reflectors are the same reflectors. Up to τ = 10⁴ the two answers agree. At τ = 10¹⁴ they are 4.8·10⁻¹⁵ and 0.00208 — a factor of 4.324·10¹¹, from the sequence of the rows and nothing else. The reason is that the first reflector is built from the first column, and a column whose large entries are at the bottom has them annihilated last, after the small ones have already been added to them and lost.0246810121410⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹log₁₀ τrelative error against the exact answerconstraint rows lastconstraint rows firstthe same arithmetic, resequencedconstraint first, τ = 10¹⁴4.8·10⁻¹⁵constraint last, same τ0.0021the ratio4.3·10¹¹multiplications, either order0same reflectors, same countand ten digits between them
Fig. 17 The other thing that can go wrong with the weighted construction, from the previous essay.
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. 18 A bound that holds with a probability, in the field’s own first essay.
Random numbers a sketch needs, against the number of indices, at n = 8A dense Gaussian sketch of a mode-k unfolding multiplies an n × n^{d−1} matrix by a random one with n^{d−1} rows, so the random object is the size of the tensor divided by n — the line that crosses the tensor's own entry count at d = 2 and is 1.51·10⁸ by d = 8. A Khatri–Rao sketch replaces it with d − 1 small Gaussians per column, costing 4,032 numbers at the same point — a factor of 3.74·10⁴ — and is applied as mode products, so nothing the size of the tensor is ever formed. What it is not is Gaussian, which is what the previous figure has to measure rather than bound.12345678910¹10³10⁵10⁷number of indicesrandom numbers drawna dense Gaussian sketchdashes: the tensor's own entriesa Khatri–Rao sketcha random matrix nobody can afforddense at d = 81.5·10⁸structured4032the tensor's entries1.7·10⁷dense ⁄ structured3.7·10⁴crossing at d2the sketch outgrows its tensorand the structured one does not
Fig. 19 Why every number here is a median over twelve draws.
What extra columns buy a construction that never sees the matrix, over five seedsThe band is the range across five seeds and the line is their mean; the flat lower line is the best representation of rank 8 there is, which a decomposition of every block would find. With no oversampling the construction is 11.6 times behind it and the spread across seeds is 44 per cent of the mean. Eight extra columns bring it to 3.0× and the spread to 12 per cent. Both halves matter and only one of them is visible in a single run: what oversampling buys is a better answer and a more predictable one, and a figure drawn from one seed would have shown the first and hidden the second. No draw is ever better than the flat line, which is the check that the comparison is honest — a sample cannot beat the decomposition it is approximating.048121610⁻⁸10⁻⁷10⁻⁶10⁻⁵extra columns in the sample, p‖A − A_H‖ ⁄ ‖A‖the best rank-8 representationfive draws, mean and rangea band, not a lineexcess at p = 012excess at p = 83spread at p = 00.44spread at p = 80.12the optimum of this rank7.8·10⁻⁸one seed shows the meanand five show the risk
Fig. 20 What oversampling buys, on the quantity it buys it for.
The 12 eigenvalues of a saddle-point matrix with 10 unknowns and 2 constraints, inside their closed-form bracketsK = [[H, Aᵀ], [A, 0]] with κ(H) = 100 and κ(A) = 100. The shaded bands are the Rusten–Winther brackets, computed from four numbers — the extreme eigenvalues of H and the extreme singular values of A — before the matrix was assembled: negative eigenvalues in [-0.995, -10·10⁻⁵] and positive ones in [0.01, 1.62]. The marks are the computed spectrum. There are exactly 10 above zero and 2 below, which is Sylvester's law of inertia and not a property of this matrix: K is congruent to blkdiag(H, −AH⁻¹Aᵀ), both blocks are definite, and congruence preserves signs. The two groups are separated by a gap containing zero, at a ratio of 4.48 between the innermost positive eigenvalue and the innermost negative one.-1-0.582271-0.1645420.2531860.6709151.088641.506370eigenvalue2 negative10 positivecounted before it was formedpositive10negative2at zero0innermost ratio4.5the zero block is a theoremand so is the count either side of it
Fig. 21 The system the repair solves.
What each way of eliminating a constraint inherits, over five decades of κ(A)The same system solved twice, at 8 unknowns and 3 constraints with κ(H) = 100. The range-space method forms S = AH⁻¹Aᵀ and inherits κ(S), which rises from 12.99 to 3.981·10¹⁰ — the square of κ(A), for the reason the normal equations square it. The null-space method solves with the reduced Hessian ZᵀHZ, whose condition number is 21.13 at the start of the sweep and 21.13 at the end: it does not contain κ(A) at all. The two forward errors, measured against a solution computed in BigInt rationals, follow their own condition numbers: 5.314·10⁻⁶ against 5.788·10⁻¹² at the far end. Both methods are correct and one of them is usable.01234510⁻¹⁷10⁻¹³10⁻⁹10⁻⁵10⁻¹10³10⁷10¹¹log₁₀ κ(A)condition number, and relative errorκ(S)κ(ZᵀHZ)range-space errornull-space erroragainst a BigInt answerκ(S) at κ(A) = 10⁵4·10¹⁰κ(ZᵀHZ), all stops21range-space forward error5.3·10⁻⁶null-space forward error5.8·10⁻¹²both are the same algebraand only one squares
Fig. 22 And the two ways of solving it.
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. 23 A spectrum with nothing for a sketch to find, which is the other way this field’s guarantee becomes vacuous.
The least-squares solution as a projection, with the right angle measuredThe column space drawn edge-on as a plane, the data vector above it, and the perpendicular dropped to the plane, with the residual marked at a right angle to it.everything Ax can reachb = (1.1, 0.4, 1.5)Ax, the closest reachable pointr = b − Ax‖Aᵀr‖ / (‖A‖‖r‖)1.7·10⁻¹⁶‖b‖² − ‖Ax‖² − ‖r‖²1.3·10⁻¹⁵‖r‖1.3200 random nearby points of the plane were tried; none is closer.a 3×2 system, Householder QRperpendicularity is checked
Fig. 24 The unconstrained problem underneath all of it.
How nearly the constraint is satisfied, when a sketch is allowed to see it and when it is notSketching reduces a least-squares problem to 8 rows and keeps its minimiser within (1 + ε) of the original's. That is a statement about a norm, and an equality constraint is a statement that a quantity is zero, which no multiplicative distortion preserves. Kept out of the sketch and imposed exactly, the constraint holds to 1.68·10⁻¹⁶ at every weight. Written as a weight and sketched along with everything else, it holds at 2.439·10⁻⁸ at τ = 10⁸ — and the slope is the finding: the violation falls as 1/τ, one power, where the unsketched weighted problem's falls as 1/τ². The sketch costs exactly half the decades the weight was buying, and buying them back means squaring τ, which the previous figure says the arithmetic stops allowing.2468101210⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²log₁₀ τ‖Bx − d‖ / ‖d‖sketched with the objectiveweighted, not sketchedkept out of the sketchone power instead of twokept out — feasibility1.7·10⁻¹⁶sketched at τ = 10⁸2.4·10⁻⁸unsketched at τ = 10⁸1.7·10⁻¹⁶objective ÷ optimum1.3a sketch preserves a normand a constraint is not one
Fig. 25 Twenty-four draws a point rather than twelve, where the medians barely move.
Minimise ‖Ax − b‖ subject to Bx = d, solved as a weighted least-squares problem, three waysStack the constraint on top of the objective with a weight τ and solve the ordinary least-squares problem that results. In exact arithmetic the answer approaches the constrained one like 1/τ² — measured here as exactly four orders of error per two decades of τ, against a solution computed in BigInt rationals from the problem's own optimality conditions. What stops the limit is the solver and not the problem. The normal equations on the weighted problem form entries of size τ², so the constraint block is lost once τ² passes 1/u: the last weight at which they are within an order of the right answer is 10⁴ here, against 1/√u = 6.71·10⁷, and by τ = 10¹⁴ they are wrong by 35.3. Householder QR has no such ceiling and is at 1.35·10⁻¹⁵ at the same weight. Classical Gram–Schmidt is worse than either, at 0.74.0246810121410⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹10⁴10⁷10¹⁰log₁₀ τ — the weight on the constraintrelative error against the exact answerτ = 1/√uGram–Schmidtnormal equationsHouseholder QRthe ceiling is the method'sHouseholder, τ = 10¹⁴1.4·10⁻¹⁵normal equations35Gram–Schmidt0.741/√u6.7·10⁷a constraint is a weight at infinityand the solver decides how far infinity is
Fig. 26 One constraint to demote rather than two.
The reduced Hessian and the answer, against how badly the basic columns were chosenγ is the condition number of the first 4 columns of A, and the naive rule calls exactly those columns basic. Its reduced Hessian's condition number climbs from 83.77 to 4.871·10¹⁸ across ten decades of γ — the square, because κ(ZᵀHZ) ≤ κ(H)κ(Z)² and the bound is attained. Choosing the basic columns by a column-pivoted QR instead holds it between 31.72 and 43.09 at every stop. The two forward errors, measured against a BigInt answer, follow their own condition numbers: 0.3173 against 8.07·10⁻¹⁶ at γ = 10¹⁰. κ(A) is 10⁶ throughout and never moves — nothing about the problem's difficulty changes across this axis, only which columns a one-line rule happens to pick.024681010⁻¹⁷10⁻¹³10⁻⁹10⁻⁵10⁻¹10³10⁷10¹¹10¹⁵10¹⁹log₁₀ γ — conditioning of the first m columnscondition number, and relative errorκ(ZᵀHZ), naiveκ(ZᵀHZ), pivotederror, naiveerror, orthonormalone problem, two rulesκ(ZᵀHZ) naive, γ = 10¹⁰4.9·10¹⁸κ(ZᵀHZ) pivoted, worst43error, naive0.32error, pivoted8.1·10⁻¹⁶κ(A) does not move across this axisand the answer moves by fourteen digits
Fig. 27 The projection repair’s ingredient, priced.
Both forms of an interior-point step: two condition numbers that climb together and two errors that do notOne Newton step of an interior-point method for a quadratic programme with 8 unknowns and 6 constraints, 3 of them active, written twice. The augmented form is [[H, Cᵀ], [C, −D⁻¹]] and the condensed form is H + CᵀDC, and they have the same solution. As the barrier parameter μ falls, the diagonal D separates — z/s runs to 1/μ on the active constraints and to μ on the inactive ones — so both condition numbers climb: 29.04 to 3.044·10¹⁵ for the augmented form and 155.8 to 2.403·10¹⁶ for the condensed one, within a factor of 7.9 of each other. The two forward errors, both measured against the exact rational solution of the system the machine is holding, do not follow: the condensed form's rises to 0.3098 and the augmented form's stays at 1.035·10⁻¹⁵ — fifteen correct digits at a condition number of 3.04·10¹⁵.-14-12-10-8-6-4-2010⁻¹⁷10⁻¹³10⁻⁹10⁻⁵10⁻¹10³10⁷10¹¹10¹⁵log₁₀ μ — the barrier parametercondition number, and relative errorκ₂, condensedκ₂, augmentederror, condensederror, augmentedagainst a BigInt answerκ₂ augmented, μ = 10⁻¹⁴3·10¹⁵its relative error10⁻¹⁵κ₂ condensed2.4·10¹⁶its relative error0.31the same step, written two waysand only one of them is solvable
Fig. 28 And a constrained problem nobody would sketch, from the constraint field.

Where this goes next

0246810121410⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹10⁴10⁷10¹⁰log₁₀ τ — the weight on the constraintrelative error against the exact answerτ = 1/√uGram–Schmidtnormal equationsHouseholder QRthe ceiling is the method'sHouseholder, τ = 10¹⁴4.8·10⁻¹⁵normal equations14Gram–Schmidt4.9·10¹⁰1/√u6.7·10⁷a constraint is a weight at infinityand the solver decides how far infinity is A constraint is a weight at infinity Stack an equality constraint on top of a least-squares problem with a large weight and the answer approaches the constrained one like 1/τ². The limit is takeable to any accuracy — and how far it can be taken is a property of the solver, not of the problem. One of them stops at the square root of the precision, and one of them does not stop. 10²10⁴10⁶10⁸10¹⁰110²10⁴10⁶10⁸10¹⁰condition number of the matrixcondition number seen by the iterationκ(A), unchangedκ(AR⁻¹)a bound with no κ(A) in itκ(AR⁻¹), every κ(A)2.2κ(SU), the other route2.2κ(A), across the sweep10⁸κ(AR⁻¹), across the sweep1the sketch never sees the spectrumand the spectrum cancels out of the answer 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. 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 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.

What links here

Computed from the collection, not written here: the essays that point at this one.

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.

Condition numberEquality constrained least squaresExact ground truthLeast squaresMethod of weightingOversamplingRandom projectionSaddle-point systemsSketchingSubspace embedding