A parameter that counts steps

Two fields on this site end on a knob, and only one of them calls it that.

The regularisation field’s is λ, a positive real number multiplying a penalty, and choosing it is a subject with a literature: three published rules, scored here against an oracle that requires the exact answer, landing at 1.00, 1.06 and 2.29 times its error.

The iterative field’s is when to stop. It appears in every account of every method in that field as a tolerance — a number small enough that the residual falling below it means the work is done. It is not presented as a modelling decision, and on the problems that field is built on it is not one: the model problem has an exact answer, the iteration converges to it, and stopping early costs accuracy in a way stopping later would fix.

Put the second knob on the first field’s problem and it stops being a tolerance. It becomes the regularisation parameter, it has an optimal value that is not the smallest available, and running past it destroys the answer — while every quantity the method can compute says the run is going well.

The method, and the one thing about it that is not standard #

CGLS is conjugate gradients applied to AᵀAx = Aᵀb with AᵀA never formed. That distinction matters more here than anywhere else on the site, because the road that squares the problem is what forming it costs: κ(AᵀA) = κ(A)², and below ε = √u the product of a matrix with itself comes out exactly singular. The iteration touches A and Aᵀ separately, so its arithmetic is done at κ(A) while its convergence behaves as though the operator were AᵀA.

Every iterate is kept, because the whole subject is which one to hand back. A routine that returned only the last would have thrown away the question.

Semi-convergence, and the two curves that make it #

Read the hero figure as two claims rather than one.

The residual falls at every step. Not on average, not in trend: at every one of the 120 steps, and this is asserted step by step rather than between the ends, because a quantity that falls throughout is the whole of what a solver can see. Conjugate gradients minimises ‖b − Ax‖ over a space that grows by one dimension per step, so the minimum over the larger space cannot be worse than the minimum over the smaller one. This is a theorem, and the figure is it.

The error turns. It falls for twenty steps, reaches 0.1426, and then climbs through two orders of magnitude. Nothing has gone wrong with the arithmetic — the run at step 120 is exactly what the recurrence produces — and nothing has gone wrong with the method. What has happened is that the iteration has started fitting the noise, and the noise is the part of b that has no answer behind it.

The mechanism is the one the previous field measured. The singular values of this operator decay exponentially with no gap anywhere; the coefficients uₖᵀb of the exact right-hand side decay faster; the coefficients of the noisy one flatten at the noise floor and stop. Every term of the solution past that flattening is noise divided by a σ of 10⁻¹⁰ or less. The early iterations reconstruct the components where the signal is; the later ones reconstruct the components where it is not.

So the site’s oldest sentence — a small residual is not a small error — arrives here with a stopping rule attached, and the stopping rule is the regularisation.

The filter, and why it is a claim rather than a change of coordinates #

The regularisation field writes both of its standard methods as one expression with different weights:

x_reg  =  Σₖ fₖ · (uₖᵀb / σₖ) · vₖ

with fₖ = 1 or 0 for a truncation and fₖ = σₖ²/(σₖ² + λ²) for Tikhonov. The claim about conjugate gradients is that the mth iterate has the same form, with

fₖ  =  1 − Π_j (1 − σₖ²/θⱼ)

where the θⱼ are the Ritz values of AᵀA after m steps — a polynomial in σ² of degree m, with its roots where the iteration has converged.

There is an obvious way to check that and it proves nothing. The vₖ are an orthonormal basis of the whole space, so any vector can be written as a filtered sum: measure fₖ = σₖ(vₖᵀx_m)/(uₖᵀb), substitute it back, and the sum reproduces x_m exactly. That is a change of coordinates wearing the clothes of a theorem, and this file’s first version of the check did precisely it.

What makes it a claim is that the polynomial route never looks at the iterate. Conjugate gradients and Lanczos are the same process written twice, so the α and β of the recurrence are the entries of the Lanczos tridiagonal of AᵀA, and its eigenvalues are the θⱼ. The predicted factors are then a function of σ alone, determined by m numbers. The measured factors are sixty-four independent coordinates of a vector, constrained to be nothing at all.

What the shape says #

Two properties of the measured curve are not shared by any Tikhonov filter at any λ, and both follow from what the polynomial has to do.

It goes above one. The largest factor at step 16 is 1.2035. A filter factor above one means the method has overcorrected that component — put back more of it than the data contains. For Tikhonov that is impossible: σ²/(σ² + λ²) is below one for every positive λ, by construction.

It is not monotone. The measured factors change direction eight times. A polynomial that is one at the converged Ritz values and small far below them cannot descend steadily in between; it oscillates around one in the region it has resolved and falls off past it.

Neither is a defect. The overshoot is where the method is ahead of the smooth filter at the same effective cutoff, which is part of why a handful of steps competes with a factorisation. But it settles a question the field’s vocabulary invites: conjugate gradients is a spectral filter in the same sense Tikhonov is, and it is not the same filter, and no λ makes it one.

And the identity has an expiry date #

Now run the two routes further apart and watch them separate.

The polynomial description of conjugate gradients is exact while the recurrence stays orthogonal and false after it. That is not surprising once stated — the whole derivation runs through a Krylov basis that is orthogonal in exact arithmetic and is not in floating point, which is the ghosts essay’s subject in another field.

What is worth having is where it breaks. On this problem the basis loses orthogonality between steps 16 and 20, and the error is least at step 20. The textbook description of the method stops being true at exactly the step anybody would want to stop at. Both halves of that are asserted rather than reported, because an assertion that the routes always agree would be false and one that quietly stopped checking past step 16 would be hiding the interesting half.

The knob is an integer, and that changes what a mistake costs #

The discrepancy principle is the one parameter-choice rule that needs to be told the noise level, and the standard criticism is that nobody knows it. In the λ field the criticism has teeth: told a noise level ten times too small the rule returns λ = 10⁻⁸ and an error of 10,449 against a truthful 0.112 — five orders of magnitude, from a factor of ten.

Applied to a step count, the same rule and the same lie behave differently:

Overstating costs 17%. Understating costs a factor of forty — bad, and bounded by the run, because the rule cannot ask for more steps than are taken. A continuous knob has no such floor: λ can be made arbitrarily small, and the answer it produces is unbounded.

That is a genuine difference between the two parameters and it points the other way from the usual one. The integer is coarser, so it cannot be tuned as finely; and it is coarser, so a wrong noise estimate below a certain size changes nothing at all, because the stopping step is the same integer either way.

Twenty steps against a factorisation #

The comparison the whole essay is for. On this problem:

A ratio of 1.014. The λ needed a singular value decomposition, or a QR of a 2n×n stacked matrix; the step count needed twenty products with A and twenty with Aᵀ, and neither the matrix nor its factorisation was ever formed.

This is where the two fields stop being two fields. What the regularisation field measures as a choice about a penalty, the iterative field can produce as a choice about a budget — and on a problem where A is a convolution and its products cost n log n, the second is available at sizes where the first is not.

The other half of the deferral: a penalty with a null space #

Everything above penalises ‖x‖. The general form penalises ‖Lx‖ for some other matrix L, and with L a discrete derivative the change is not cosmetic: L₁ has a null space, and a vector in it is not penalised at all. assertTheNullSpaceIsTheDifference feeds it a constant vector and requires ‖L₁·(3.7…)‖ to be exactly zero, which it is.

That matters whenever the answer has a nonzero mean, and the size of it is measurable by raising the offset and watching the two forms diverge.

The advantage is not a fact about derivative penalties being better. It is the offset, arriving in the answer, because a penalty on ‖x‖ shrinks — it prefers small answers, and a signal with a large mean is not small. The measured shortfall says so directly: the norm penalty’s solution is short of the truth’s length at every offset, and the derivative penalty’s is not.

And it is the one place where the filter-factor reading of this whole field stops. The general-form solution is not a weighted sum over A’s singular vectors; it is a weighted sum over the generalised singular vectors of the pair (A, L), which are a different basis. A routine that reported measured filter factors for it would be reporting sixty-four numbers that reconstruct the vector and mean nothing, which is exactly the trap the two-route check above exists to avoid — and it is one of the refusals this file runs.

What the two knobs turn out to have in common #

Three things, and the third is what makes this a combination essay rather than a regularisation one.

Both have an interior optimum. Neither the smallest λ nor the largest step count is the right one, and in both cases the reason is the same trade: too little regularisation fits the noise, too much discards signal.

Neither optimum is computable from the data. The oracle in both fields requires the exact answer. Every practical rule is a heuristic, and the ones for the step count are the ones for λ transposed — the discrepancy principle, the L-curve, generalised cross-validation, each with the same weaknesses in the same places.

And the quantity that is easy to compute is monotone in both. The residual falls at every step and falls with every decrease in λ. A stopping rule that watches it and nothing else will always run to the end of whatever budget it is given, which is a correct implementation of a wrong idea — and it is the idea this essay’s refusal is fed.

What is left #

The other Krylov regularisers. LSQR is CGLS in a numerically better arrangement and would change the step at which the two routes above part company; GMRES applied to a square ill-posed system regularises differently again, because its Krylov space is built from A rather than AᵀA. The comparison would be about the bases, which is a phase’s work.

Hybrid methods, where a Tikhonov problem is solved inside the Krylov space at every step, so the two knobs are turned together. That is the obvious next thing to build from this essay and it needs a figure this site does not have: a two-dimensional sweep over λ and m with the oracle drawn on it.

And the noise model. Everything here adds Gaussian noise of a stated size to b. Correlated noise, noise in A rather than in b, and a right-hand side that is not in the range of A at all are three different problems, and only the first is what “1% noise” is usually taken to mean.