Four knobs and one floor

By this point the site has five separate ways of deciding how much of a problem’s data to believe. Each arrived in its own field, with its own vocabulary, in an essay written as though the methods were alternatives:

• a truncation — keep K singular components and drop the rest, from rank is a decision and the regularisation field;
• a penalty — the Tikhonov parameter λ, from when the answer is a choice;
• a step count — where to stop conjugate gradients, from the previous essay;
• a rank — how many columns a randomised sketch keeps, from a bound that holds with probability;
• a precision — how many significand bits the arithmetic carries, which is the knob this whole site is built around.

They are taught by different people out of different books. This essay puts all five on one problem with an answer that is known exactly, sweeps each one across its whole range, and reads off where each lands.

Four of them land in the same place. The fifth does something else, and the fifth is the interesting one.

The problem, and why it has to be constructed #

A 64-point Gaussian deconvolution with 1% noise: a signal of two smooth bumps and a step, blurred by a Gaussian kernel, measured with noise drawn from a fixed seed. The matrix is symmetric Toeplitz — the structure field’s object arriving here for a different reason — and its singular values decay exponentially with no gap anywhere, which is what makes the problem ill-posed rather than merely ill-conditioned.

Constructed rather than measured, and that is not a convenience. Every number below is a forward error against a signal that is known, so the four methods can be compared against the truth rather than against each other. Without it this essay could only report that four methods agree, which is consistent with all four being wrong in the same way.

The four, and what they agree about #

Three per cent, across four methods that share no arithmetic. The truncation and the Tikhonov solution go through a singular value decomposition of the matrix; the conjugate gradient one touches only products with A and Aᵀ; the randomised one multiplies A by a Gaussian matrix and factorises the result. The four are not variants of each other.

And each has an interior optimum: at both ends of its own range every one of the four is substantially worse than at its best. That is asserted rather than described, because it is what makes each of them a trade rather than a limit. Too little regularisation — a high K, a small λ, many steps, a large rank — fits the noise. Too much discards the signal along with it.

So the agreement is not four methods being good. It is one obstruction being met four times. The noise in b is what puts a floor under the answer; how much of the data is worth believing is a property of the problem; and every method that decides how much of it to believe is deciding the same thing.

They agree about the answer and disagree about everything else #

If the four filters were the same function of σ, the table above would be arithmetic rather than a finding. They are not.

A filter factor is a number between zero and one saying how much of a component to keep — except for the conjugate gradient one, which goes to 1.2 and is not monotone, which no Tikhonov filter can be at any λ. These are genuinely different weightings of the same sixty-four numbers, and they produce errors within a few per cent of each other.

That is the sharper form of the finding. It is not that the methods are secretly the same. It is that the answer is insensitive to which sensible weighting is used and highly sensitive to how much weight is applied in total — which is why the parameter matters and the method does not, and why the parameter-choice literature is large and the method-choice literature is mostly about cost.

The fifth knob, which is not one #

Now sweep the precision. The same matrix, the same right-hand side, rounded to b significand bits and solved in an arithmetic of b bits, for eight values of b.

Eight times the significand bits, twelve million times the error, and the most accurate arithmetic available produces the worst answer in the table.

That reads as a paradox for about a second. Rounding is not a weakening of the data — it is a perturbation of the operator, and a perturbation of an ill-posed operator is amplified by exactly the tiny singular values the other four knobs exist to suppress. Lower precision perturbs A more, so it perturbs the answer more; it just happens that at eight bits the perturbation is so large that the computed solution has lost the small singular directions altogether, which is an accidental truncation and is why that row is the least bad of the eight rather than the worst.

Nothing here is a regularisation. There is no monotone trade, no interior optimum, and no setting of the knob that comes near the floor. This is the negative control the rest of the essay needs: a filter acts on the spectral components of the answer, and arithmetic acts on the matrix, and the difference is what stops “every knob is the same knob” from being a slogan.

It is also the correction of a genuinely common reading of this site. The precision is the knob on the slider in twenty other essays; it is the parameter the whole collection is organised around; and on this problem it is not a parameter of the same kind at all.

And one of the four does not return the same answer twice #

The randomised knob has a property the other three do not, and the randomised field’s own sentence is that this is a change in the kind of guarantee rather than in its size.

The spread is largest where the method is worst and smallest where it is best. That is worth stating plainly because the intuition a probabilistic bound encourages runs the other way: a bound that holds with high probability suggests the risk is concentrated in rare bad draws, and what the measurement shows is a wide band precisely in the regime where nobody would operate and a narrow one where everybody would.

The mechanism is not mysterious. At a rank well below what the problem needs, the random subspace has to find a few important directions and its luck in doing so varies; at a rank where enough directions have been captured, every draw captures them.

The other three sweeps are bit-identical when re-run, which is checked rather than assumed — the truncation sweep and the step sweep are run twice in the assertion and required to agree exactly.

Why this is a combination essay and not a regularisation one #

The regularisation field could have contained the first two knobs and the fourth. It could not have contained this comparison, for a reason worth being explicit about: the essays that introduced these knobs were each written as though their method was the subject, and each was right about its own method and silent about the others.

Reading them together produces three statements none of them makes.

The floor belongs to the problem. No method here reaches an error below 0.14, and no method could, because the information is not in b. A reader who has met one of these methods and not the others has no way to know whether 0.14 is that method’s limitation or the problem’s.

The choice of method is a cost decision. Given that the four reach the same error, what separates them is what they cost and what they need: a factorisation, a stacked least-squares solve, forty matrix products, or a sketch. On a problem where A is a fast transform, only some of those are available at all.

And the parameter is the whole of the modelling. Every one of the four is a one-parameter family, the parameter cannot be computed from the data, and the published rules for choosing it are the same rules in all four fields with the same failure modes. That is where the effort belongs, and it is not where the literature’s volume is.

What the drag does, and what it does not #

Take the noise down and every curve in the hero figure moves down and to the right — the floor falls, and each knob’s optimum moves towards the less-regularised end, because more of the data has become worth believing. The four move together: at every noise level from 10% to 0.1% the spread between the four best errors stays within a few per cent.

What does not happen at any noise level is one method separating from the others. There is no regime drawn here in which the randomised method is meaningfully better than the truncation, or the Krylov method meaningfully better than Tikhonov. That is a stronger statement than the single-noise table and it is the one the slider exists to support.

Where the optima go when the noise moves #

The slider is not decoration and the reason is that a single-noise table cannot distinguish two very different explanations of the agreement above. The four methods might land together because they are doing the same thing, or because 1% noise on this operator happens to be a place where four different things coincide.

Take the noise down a decade and every optimum moves in the same direction and by a comparable amount: the truncation keeps more components, λ falls, the step count rises, the rank rises. What each knob is doing is deciding how far down the spectrum to believe the data, and less noise means the data can be believed further down. The floor falls with them.

Take it up and the reverse happens, with one asymmetry worth noticing. At 10% noise the four are still within a few per cent of each other, and every one of them is now regularising heavily — a truncation in the low teens, a λ near 0.1. At that level the shape of the answer is being decided by the penalty rather than by the data, which is the situation the regularisation field’s own essays warn about, and no choice of method changes it.

That is the strongest form of the finding available from one problem: the agreement is not a coincidence at one noise level, it is the same curve seen four ways at every noise level the figure draws.

What a fair comparison would have to be #

Every number in the table above is each method at its own oracle — the parameter that actually minimises the error, which requires the answer. No run has that.

A fair comparison would score each method at the parameter its own best practical rule chooses, and the differences would then be differences between heuristics rather than between filters. Two things make that harder than it sounds, and both are worth stating because they are why this essay stops where it does.

The rules were written for λ. The discrepancy principle, the L-curve and generalised cross-validation are all stated for a continuous parameter, and transposing them to an integer knob is not mechanical: the L-curve’s corner is found by curvature, and a curve sampled at twenty integers has no curvature worth the name. The step-count essay in this field transposed one of the three and found that the transposition changes the failure mode — a lie about the noise level costs five orders of magnitude with λ and a bounded factor with an integer.

And the randomised method has no rule at all. Nobody has scored a parameter-choice rule against a method whose answer moves with the seed, and the obvious first question — whether the rule should be applied to one draw or to a median over several — changes what is being measured rather than how accurately.

So the honest statement is: four methods reach one floor at their own optima, and how much of that survives contact with a real parameter choice is a measurement this site has made for one of the four and not for the others.

What is left #

The comparison is at each method’s own oracle, which no practical run has. A fairer table would score each method at the parameter its own best published rule chooses, and the differences between the four would then be differences between four heuristics rather than between four filters. That is a phase’s work and it needs the rules transposed to the step count and the rank, which nobody has done carefully here.

And the problem is one problem. The floor is a property of this operator and this noise; a problem whose singular values decay like a power rather than exponentially has a rank to find, and the truncation would then be doing something the others are not. The regularisation field’s own essays make that distinction and this comparison does not test it.

The precision result deserves its own measurement in the other direction: at what conditioning does rounding stop behaving like a perturbation of the operator and start behaving like noise in the data? Somewhere between the well-posed problems the arithmetic field is built on and the ill-posed one here, the fifth knob turns into one of the four — and this essay measures the two ends and not the crossing.