The parameter neither knob is

A step that is not a unit of work settled a question of this kind once already, for a method with no preconditioner in it. Landweber’s iteration has a step length ω and a step count k, and it looks as though it has two parameters. It has one. Halve ω and the best step doubles: at ω = 0.5, 1, 1.5 and 1.9 over $\sigma_1^2$ the optimum sits at $\omega k$ = 1,724, 1,728, 1,733 and 1,742, and the error it reaches is the same to four figures. The regularisation parameter is the product, and the two knobs are a rate and a count of turns.

A truncated preconditioned run has the same shape of question and not the same answer to it. Its cutoff τ decides how many directions are divided by the approximation’s eigenvalue; its step count decides how far the iteration has got. What a cheap preconditioner has to leave alone measured the step counts and found them falling as τ falls — 20 steps with no preconditioner, 5 at τ = 10⁻², which is exactly the behaviour a rate would have. And then, below a certain τ, the run stops reaching the answer at all, which is not.

The obvious guess is therefore wrong in an interesting way: the two knobs behave like a rate and a count over part of their range and like something else over the rest. What separates the two regimes is measurable, and measuring it needs a quantity neither knob is.

The quantity an iterate has, rather than the one it took #

Every iterate of a Krylov method on an ill-posed problem is a filtered solution. In the operator’s singular basis it can be written as $\sum_k f_k (u_k^{\mathsf T}b / \sigma_k)\,v_k$ for weights $f_k$ that the iteration never computes and that exist all the same, and an expiry date the noise does not move measured them two ways on this problem and found the two routes agreeing until orthogonality goes.

The sum of those weights is a number, and it is the number wanted here. For Tikhonov at parameter λ it is $\Sigma \sigma_k^2/(\sigma_k^2 + \lambda^2)$, which runs smoothly from the rank of the operator down to zero as λ rises, and is the quantity a statistician would call the effective number of parameters the fit has spent. For truncation at index K it is exactly K. For a Krylov run it is neither of those and is still a number: what the iterate has committed to, measured in components rather than in steps.

Both routes to it agree here, and the check is worth having because the weights are not stored anywhere. Summed along the run as the iteration proceeds, and recomputed from scratch at one iterate from the filter factors themselves, the effective dimension at step 8 agrees to better than a part in 10⁹.

That is the axis to put a run on. The step count is an axis about the iteration; the effective dimension is an axis about the answer, and two runs at the same point of it have committed to the same amount of the data whatever it cost them to get there.

The arc, and who is on it #

The unpreconditioned run at 1% noise traces an arc. Its first countable iterate carries about 8 of effective dimension at an error of 0.285; it climbs to 23.95 at step 20 at an error of 0.1426, and that is its best. Everything worth having on this problem is on that arc, because past its top the error rises and below its bottom the iteration has barely started. Over twelve draws of the noise the arc ends at 23.2 and the run reaches it at 1.27 of dimension a step.

Now put the preconditioned runs on the same axes. At τ = 10⁻⁰·⁵, which preconditions 13 of the 64 directions, the run lies on that arc. Fifteen of its fifteen iterates land inside it, its best carries 23.69, and its error there is 0.1426 — the identical number, at step 15 instead of step 20. At τ = 10⁻¹, 18 directions preconditioned, nine of ten iterates are on the arc, the best carries 22.55 and reaches 0.1431. Over twelve draws the two of them sit at 1.001 and 1.009 times the unpreconditioned run’s own error at the same effective dimension.

That is a collapse, and it is the Landweber result in a different coordinate. The preconditioner is not producing different answers faster. It is producing the same sequence of answers, sampled more coarsely: 1.90 of dimension a step at the first cutoff and 2.32 at the second, against the plain run’s 1.27. The cutoff is a stride length. The regularisation parameter is the distance travelled, and the step count is how many strides it took.

Where a stride stops fitting #

Keep going down in τ and the stride keeps lengthening — 3.44 at τ = 10⁻¹·⁵, 3.53 at 10⁻² — and something else starts happening that a longer stride alone would not explain. The share of the run’s iterates that land on the arc at all falls: 98%, 88%, 46%, 27%, and then 0%.

Those are different quantities and they come apart at the edge. A run whose stride is 3.5 and whose arc is 15 long has four or five iterates on it — coarse sampling, and every sample in the right place. A run whose first stride is longer than the arc has none, and the first iterate it produces is already past the answer. At τ = 10⁻²·⁵ on the single draw drawn above, the run’s first two iterates have no countable effective dimension at all — the weights are wildly negative, which is conjugate gradients’ filter overshooting in the way the filter-factor measurement recorded — and its third carries 22.4. A stopping test is a race is the same limitation in a well-posed setting, where the test stops whichever iteration reaches the tolerance first and has no opinion about whether that is the one that should have. Its best carries 27.99 at an error of 0.2343, where the arc ended at 23.95 with an error of 0.1426.

So the edge is not a place where the stride becomes too long in the abstract. It is the place where one stride exceeds the distance that was left, and the measurement says so directly: the effective dimension at each run’s own best is 23.9, 23.7 and 24.3 for the three cutoffs above the edge — the top of the arc, three times over — and 28.3 and 32.1 for the two below it. Every run that works stops in the same place. Every run that does not has overshot it and is showing the least-bad iterate of a set that all overshot.

The method that cannot use a smooth answer found four regularisers reaching one floor and separating only when scored against answers of increasing smoothness; the arc is that floor drawn as a path rather than as a number. That is a sharper statement than the one the earlier measurements could make. A preconditioner that arrives past the answer was measured as “the best iterate is the first”; here the answer has a location, the run has a stride, and arriving past the answer is a stride longer than the distance to it.

At a tenth of the noise the arc is longer and the same cutoffs fit #

The arc’s length is set by the data, not by the method. Less noise means the data supports more components, so the unpreconditioned run climbs further before its error turns: at 0.1% noise the arc ends at 28.1 rather than 23.2, and it takes 43 steps to get there, which is 0.66 of dimension a step.

Every cutoff’s stride falls with it — 0.91, 1.18, 1.55, 1.98, 3.09 — because a stride is a distance per step and the step is the same step. So the arithmetic of what fits changes twice over, and in the same direction: a longer arc and shorter strides. Four cutoffs now land 72% or more of their iterates on the arc where two did at 1% noise, and the error at matched dimension stays between 1.001 and 1.020 across all five of them. The one that fails is τ = 10⁻³, at 23% and a ratio of 1.552.

The edge moves accordingly. What a cheap preconditioner has to leave alone located it by sweeping the best error against the truth and found it at a third to a half of the Tikhonov oracle’s λ. Located here, as the cutoff at which the share landing on the arc collapses, it is the same cutoff to within the quarter-decade this grid resolves — at both noise levels. Two independent constructions, one reading the answer and one reading the geometry of the run, agreeing on where a preconditioner stops being one.

The other method stops in the same place #

The arc has been treated so far as a property of the iteration — the sequence of answers conjugate gradients walks through on this problem. It is not. It is a property of the problem, and the evidence is that the other method measured here stops at the same point of it.

Tikhonov’s filter at parameter λ has an effective dimension of its own, $\sum_k \sigma_k^2/(\sigma_k^2 + \lambda^2)$, computed from the singular values and λ and from nothing about any iteration. The oracle λ — the one that actually minimises the error, which the first of these essays used as the reference every rule is scored against — carries 22.40 of it at 1% noise over twelve draws. The iteration’s own oracle step carries 23.17. At a tenth of the noise the two are 27.97 and 28.09.

Nothing arranged that. The two optima are found by different searches over different objects: one minimises over a continuum of filters indexed by a positive real number, the other over a nested sequence of Krylov spaces indexed by an integer, and neither computes an effective dimension at any point. They agree to 3% and to 0.4%.

This is the sense in which the quantity is the field’s parameter rather than an artefact of putting preconditioned runs on a common axis. The first of these essays set the two knobs beside each other — best step 20 against best λ = 0.025, reaching 0.1426 and 0.1406 — and asked what they had in common beyond both being called a regularisation parameter. They have this in common: each is a way of specifying how much of the data the answer is allowed to contain, and the amount they both settle on is the same amount. λ specifies it by a threshold on the singular values, the step count by a number of Krylov directions, the cutoff by a stride, and all three are addressing one number that none of them names.

It also sharpens what the preconditioner is for. A preconditioner does not change where the answer is — the arc’s top is fixed by the data — and it does not change what is there when the run arrives. It changes the number of matrix– vector products spent getting there, and the measurement above says it does that by lengthening the stride rather than by any change in the sequence of answers. A construction whose whole effect is to coarsen the sampling of a fixed arc is a construction whose failure mode is completely determined: it fails when the sampling is coarser than the arc is long, and at no other time.

Why the collapse is not a tautology #

There is a version of all this that would be empty. If the effective dimension were simply a relabelling of the step count — if every run gained the same dimension per step — then plotting error against dimension rather than against steps would rescale the horizontal axis and prove nothing.

It is not, and the stride numbers are the evidence: 1.27, 1.90, 2.32, 3.44, 3.53 at one noise level and 0.66, 0.91, 1.18, 1.55, 1.98 at another. The seven runs are at seven different rates, so putting them on one axis is a genuine change of coordinate and their landing on one curve is a genuine fact about them. It is also a fact that fails: two of the seven do not land on it, and the ratio at matched dimension for those two is 2.675 and 7.746 rather than 1.01.

A second way it could have been empty is if the arc were merely where the error is small, so that anything reaching a good answer would be on it by definition. That is not what is measured either. The ratio compares a preconditioned iterate against the plain run’s error at the same dimension, so a run that reached the same error at a different dimension would read far from one — and one does: at τ = 10⁻², over the four draws of twelve that put any iterate on the arc, the ratio is 1.107 while the run’s median best error is 0.1502 against the floor’s 0.1352. That run is slightly off the curve and slightly worse, and the two are the same observation.

What one number buys, and what it does not #

The pair is one parameter, and the parameter is a distance. That answers the question the earlier measurement left and it does not hand anybody a rule, because the effective dimension cannot be computed without the singular value decomposition — the object an iterative method exists to avoid. It is an instrument, not a knob, and every number above was computed with an answer in hand — the same standing the oracle λ has in the parameter-choice essays, where it exists to score rules and is not one.

What it does buy is a statement about what a stopping rule on this construction is choosing between. A rule that stops by the residual is not choosing a step count; it is choosing a point on the arc, and its accuracy depends on how coarsely the run samples the arc. A stopping rule that follows the run it is given measured that accuracy directly and found the rule doing better on the preconditioned run than on the plain one despite a window a quarter as wide — which reads oddly in step counts and reads naturally here. The window is narrow in steps because the strides are long, and the rule is not stopping at a step, it is stopping when the residual reaches the noise, which is a place on the arc. A longer stride does not move that place; it changes how near a stride’s end lands to it. On this problem the strides are short enough relative to the arc that it lands near, and the reason the plain run does slightly worse is that its arc is traversed so slowly that the residual is still falling after the error has turned.

And past the edge it explains what the rule cannot see. There is no point on the arc at which the run past the edge is stopped, because it never lands on the arc. The residual reaches the noise level all the same, at an iterate carrying 32 of effective dimension against an arc that ends at 23. The rule is not failing to find the right stride; there is no stride to find.

What this does not settle #

One operator, one signal, one approximation, two noise levels. The stride numbers above are properties of this blur’s spectrum and this signal’s Picard coefficients, and nothing here says how a stride scales with either.

The effective dimension is measured on a filter that is only approximately the filter the iterate carries. Past the step where orthogonality is lost the recurrence and the iterate disagree about the weights, and the expiry-date measurement put that step at 17 or 18 on this operator. Every run above stops at its own best, which on the plain run at 1% noise is step 20 — just past it. The sum is computed off the iterate rather than off the recurrence, so it is the iterate’s own dimension either way; what is unmeasured is whether the arc’s top moves when the iterate’s weights have stopped being a polynomial in the operator.

The two regimes are separated by a quarter-decade grid in τ, which is not enough to say whether the share landing on the arc falls smoothly or drops. Twelve draws are twelve draws, and the ratios at the two failing cutoffs are medians over the subset of draws that put any iterate on the arc at all — four of twelve at one of them, which is a median of four numbers and is reported as such.

Still open: the stride without the decomposition, and the same question for the shift #

A stride a code can see. The effective dimension needs the singular values. The number of directions the preconditioner acts on does not — it is counted when the preconditioner is built — and it moves the same way: 13, 18, 22, 25, 28, 31 against strides of 1.90, 2.32, 3.44, 3.53, 3.02, 3.04. Whether the count predicts the stride well enough to be used in its place, and whether the prediction survives a change of operator, is the measurement that would turn an instrument into a rule.

The shifted construction, which has no edge. Every measurement here is on the truncated preconditioner. The shifted one never reaches the unpreconditioned floor at any parameter, so it has no edge to find — and if the argument above is right, its runs should sit off the arc at every shift rather than leaving it at one. That is a prediction with a cheap test and it has not been run.

Whether the arc is the same arc for Tikhonov, or only the same top. The two methods stop at the same effective dimension, which is measured above; whether a λ sweep’s whole curve of error against dimension lies on the arc the iteration climbs, or merely crosses it at the optimum, is not. The two predictions differ everywhere except at the point where the measurement was taken, and separating them needs the error at matched dimension along both, which is one sweep.

A stopping rule stated in the right coordinate. If the parameter is a distance and the residual test is a test on the distance, then a rule that reads the residual’s rate of fall per step would be reading the stride, which is the quantity the plain discrepancy principle is blind to. Whether such a rule separates a run before its edge from one past it — the question the earlier measurement could not answer with the residual alone — is where the two questions meet.