The half of a problem a sketch may touch

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.

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.

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.

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.

The rule run out to where it fails #

That rule has a ceiling in it and the ceiling is worth reaching rather than citing. τ from 10⁴ to 10¹⁸, l = 8, twelve sketches a stop:

The slope is 1.00 per decade to two digits across ten decades, and then the sketched feasibility reaches the rounding level at τ ≈ 10¹⁶ — which is 1/u, exactly where a Householder solve’s ceiling sits. So squaring τ does recover the whole of what the sketch cost, arriving within a factor of two of the constraint that was never sketched at all, and it arrives precisely at the ceiling: 10⁸ is the midpoint of the available range and the sketch costs exactly the other half of it. The resource was bounded and the sketch consumes all of it, which is a sharper statement than consumed a resource that was already bounded and is the one the measurement supports.

Past the ceiling the objective goes. At τ = 10¹⁸ the ratio jumps from 1.42 to 15.78 — eleven times worse — so the ceiling is a ceiling rather than a guideline, and a code that responded to a constraint violation by raising τ past 1/u would trade a feasibility it could measure for an objective it was not watching.

And the row order stops existing #

There is a second consequence, and it is one neither essay predicts. The previous one measures the row order of the weighted stack at eleven orders of magnitude: constraint rows first gives 4.8·10⁻¹⁵ at τ = 10¹⁴ and constraint rows last gives 2.1·10⁻³, from nothing but which rows the first reflector sees.

Under a sketch that difference does not exist. At τ = 10⁸, l = 8, twelve sketches:

Indistinguishable, and the worse order is if anything the better one. A dense sketch mixes every row into every row, so by the time the solver sees the stack there is no row order left to get right — the rows it is ordering are linear combinations of all of them.

The reason that does not show up as a loss is worth stating, because it is the essay’s own mechanism one level down. The row order was worth eleven orders when the largest term in the feasibility was u·τ from the backward error landing on the wrong rows. Here the largest term is ε/τ from the sketch, which is 1.75·10⁻⁸ either way — seven orders above the best the row order could have bought and one order above the worst it could have cost. A repair is worth what it repairs only while the thing it repairs is the largest term, and a sketch changes which term that is.

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

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.

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.

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.

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.

The kept constraint is satisfied at the rounding level at every width — 1.19 to 4.76·10⁻¹⁶ across a sixfold range of ℓ, with no trend. A constraint that is enforced exactly is enforced exactly whatever the sketch does, which is the half of the result nobody doubts and is worth having measured because it is the baseline the other column is read against.

The sketched constraint improves as 1/√ℓ, which is much worse than it looks. Multiplying the violation by √ℓ gives 4.51, 4.94, 5.50, 5.04 and 4.30 × 10⁻⁸ for the five widths from six upward — constant to within 13% while ℓ itself moves by a factor of four. So going from ℓ = 6 to ℓ = 24 quadruples the sketch and buys a factor of 2.1 in feasibility: 1.841·10⁻⁸ to 8.769·10⁻⁹.

That rate is the reason this is a limitation rather than a tuning problem. Reaching the kept constraint’s 10⁻¹⁶ from 10⁻⁸ at a square-root rate would take a sketch 10¹⁶ times wider, which is not a sketch. The gap between the two columns is about 10⁸ at every width drawn, and nothing on this slider closes it.

The l = 4 row is the one to discount: at 1.05·10⁻⁷ its √ℓ product is twice everything else’s, and four columns is fewer than the twelve points being sketched — the regime where the sketch cannot represent the problem at all rather than the regime where it represents it approximately.

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.

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.

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