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.

How well they agree is itself a function of the noise, and it is not monotone.

Fifteen per cent is the widest disagreement anywhere on the slider, and it is at the noisiest end — which is the opposite of where a reader would look for it, since that is the regime where every method has the least to work with and might be expected to agree on failing.

Across noise levels of 10%, 5%, 2%, 1%, 0.5%, 0.2% and 0.1% the spread reads 15.4%, 6.7%, 1.3%, 3.1%, 7.1%, 1.2% and 0.7%. It falls, rises again through the middle of the range, and falls to under one per cent — so “the four knobs land in the same place” is a claim whose accuracy runs from one part in a hundred and forty to one part in six and a half.

And the outlier changes identity halfway down. At 10%, 5% and 2% noise the method furthest from the pack is Tikhonov, high by 15%, 7% and 1%. At 1%, 0.5%, 0.2% and 0.1% it is the randomised rank, high by 3%, 7%, 1% and 0.7% — and Tikhonov has become the best of the four. A penalty spread smoothly over every component is the wrong shape when the noise is large enough that most components are noise, and a sketch drawn from a fixed number of random vectors is the wrong shape when the noise is small enough that the components it misses still carry signal.

The rise at half a per cent is the part that rules out reading the spread as a simple function of the noise: it is 1.3% two stops earlier and 7.1% here, on the same problem with the same four methods, so whatever decides the agreement is not the data quality alone.

The floor itself moves much less than the noise does. The best of the four reads 0.1630, 0.1549, 0.1494, 0.1406, 0.1217, 0.1113 and 0.1050 across the seven — a factor of 1.55 for a factor of a hundred in the data’s quality. That is the sentence this essay exists to be able to write: the choice of knob is worth a few per cent, choosing it well is worth a few per cent, and the problem’s own ill-posedness is worth everything else.

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.

Which is not an accidental truncation, though it looks like one #

The tempting account of why eight bits is the least bad row is that the perturbation is large enough to have lost the small singular directions altogether — an accidental truncation. Half of that is right, and the half that is wrong is a factor of two thousand.

Counting the singular values of the rounded matrix that stand above its own rounding level:

The rank half is right: rounding does raise the effective rank as the precision rises, 28 to 64, and both columns rise with it, so the ordering of the eight rows is a rank ordering.

The execution half is not. A deliberate truncation at rank 28 gives 0.247 — within a factor of 1.7 of the best any of the four knobs achieves — and the eight-bit solve gives 460. Eight-bit arithmetic identifies very nearly the right rank and then throws the benefit away by a factor of 1,860, and it does the same at every precision: the solve is one hundred to nineteen hundred times worse than a truncation at the rank its own rounding leaves.

The reason is the one two paragraphs up, and it is worth noticing that the two explanations are incompatible. Rounding does not remove the small singular directions; it perturbs them. The solve then divides by a perturbed tiny number, where a truncation would not divide by it at all. So the first explanation is the right one and the accidental truncation is a description of the rank rather than of what happens to it — the last row is the control that settles it, where no truncation happens and the two columns are the same number.

The 0.247 in that table is worth one more sentence, because it is the most interesting number on the page and it is not about precision at all. It says that the rounding level of eight-bit arithmetic picks out a rank within a factor of two of the optimal one, on a problem whose optimal rank is 21 and whose rounding-level rank at eight bits is 28. That is a parameter-choice rule with no parameter in it: round the operator to b bits, count what survives, and truncate there.

It is not a good rule — 0.247 against 0.1445 is a factor of 1.7, which choosing without knowing shows several proper rules beating — and it is a rule nobody would have looked for, because the precision sweep was set up to show that precision is not a knob. It is not one. What it turns out to be is a rank selector that the solve immediately ignores, and the four-order gap between what it selects and what it delivers is the whole of why the fifth knob is not a knob. The same gap between a decision and its execution appears in rank is a decision from the other side, where the decision is deliberate and the execution is exact.

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.

A knob with a worst value at both ends #

Every knob on this page has a best value in the middle because two effects pull against each other. The clearest instance of that shape elsewhere on the site is the number of squarings in a matrix exponential, where the two effects are approximation range and amplified rounding.