The overshoot was the lead

One arc, and what each filter pays to be on it put three regularised solutions of the same deconvolution on one axis — the effective dimension, the sum of the factors by which each filters the data’s singular components — and found them one curve over a stretch. From 0.7 of the answer’s dimension to its top, on six problems, Tikhonov’s error and truncated SVD’s were conjugate gradients’ at the same dimension to within 7.2 per cent. Outside that stretch the curves parted. Below it Tikhonov ran above the others by up to 68 per cent; above it both other filters ran above the iteration by up to a factor of two and a half.

The essay explained the second parting, and the explanation left a question it could not answer with the axis it had. Conjugate gradients’ implied filter factors overshoot one: at 1.2 times the answer’s dimension on the collection’s blur, its factors on directions 23 to 26 reach 1.81. A factor of 1.81 adds 1.81 to the sum, 0.81 more than admitting that direction outright, so at a given effective dimension the iteration has admitted fewer directions than the others and spent the difference amplifying ones it already had. The essay read that as the iteration placing its dimension where the data has content — the only one of the three that reads the right-hand side — and asked whether a count that does not credit overshoot would line the three curves up.

It does, above the top, completely. What it shows the lead was is the more interesting part.

Two counts that do not credit overshoot #

The effective dimension is $\sum_k f_k$. Two alternatives measure how many directions a filter has admitted without rewarding it for over-weighting one:

$$\text{clipped sum} = \sum_k \min(\max(f_k, 0), 1), \qquad \text{half count} = \#\{k : f_k > \tfrac12\}.$$

The first keeps partial credit and caps it; it also stops counting a factor that has swung negative, which conjugate gradients’ factors do past their best. The second gives no partial credit at all: a direction is in or out. For Tikhonov, whose factors lie strictly between zero and one, the clipped sum is the effective dimension and the half count is the number of singular values above λ. For truncation both are the number of components kept. Only the iteration moves.

The comparison is the one the arc essay ran. On each of six problems — Gaussian blurs 1.5, 2.5 and 4 grid points wide, at 1% and at 0.1% noise — and on twelve draws of each, every conjugate-gradients iterate is placed in the coordinate, the position of the best iterate is taken as the answer’s, and at each fraction of it from 0.3 to 1.3 the nearest iterate is compared with Tikhonov and truncation placed at the same position in the same coordinate. The medians over draws of their error divided by the iterate’s are the numbers below.

The band, on three axes #

With the dial on the sum of the factors, the figure is the arc essay’s ratio figure: pinched between 0.7 and 1.0, open on both sides, and above the top Tikhonov’s band reaching 2.35 at 1.3 and the truncation’s 2.63.

Turn it to the clipped sum. The left half of the picture does not move — at 0.3 Tikhonov’s band still runs from 1.04 to 1.69 — and the right half collapses onto the line. At 1.1 of the answer, Tikhonov’s band runs from 0.91 to 1.04; at 1.2, from 0.89 to 1.06; at 1.3, from 0.88 to 1.00. The truncation’s is 0.86 to 0.97 at 1.3. Every ratio above the top, on every problem and for both filters, is now within 0.17 of one, and most of them sit just below it.

Turn it to the half count and the right half stays closed, within 0.12 of one from 1.1 to 1.3, while the left half opens further: Tikhonov at 0.3 of the answer now runs from 1.12 to 2.00.

Drawn as the single worst ratio at each fraction, the three coordinates tell one story twice. Above the top the sum is wrong by 0.26, 0.79 and 1.63 at 1.1, 1.2 and 1.3; the clipped sum by 0.09, 0.17 and 0.14; the half count by 0.08, 0.12 and 0.11. Between 0.7 and 1.0 all three are within 0.12 of one — the sum at 0.072, the clipped sum at 0.089 and the half count at 0.117 — so the stretch where a stopping rule actually works is on one curve in every coordinate, and the sum is marginally the best of them there. Below half the answer the sum and the clipped sum agree to within two hundredths, 0.677 and 0.693 at 0.3, and the half count is worse at 1.005.

So the answer to the question is a clean split. The gap above the top was the overshoot: count directions rather than weight, and it is gone. The gap below half was something else, and no count of this kind touches it.

A few units of dimension, on a steep curve #

It is fair to be surprised that so small a bookkeeping change moves a ratio from 2.35 to 0.96, and the size of the overshoot says why it can.

At the answer the overshoot is small on every problem — between 0.13 and 0.76 of a dimension, out of between 15 and 45. Past the top it grows, unevenly: on the narrow blur at 0.1% noise it is 1.36 at 1.1 of the answer, 2.63 at 1.2 and 3.11 at 1.3, where the effective dimension is 59. Three units of 59 is five per cent. But the error past the top is steep in the dimension — on one draw of that problem Tikhonov’s error goes from 0.17 at a dimension of 51 to 2.1 at 59, a factor of twelve over eight units — so a five per cent displacement along the axis is a factor of two in the error at matched position. The overshoot does not have to be large to be the whole of the difference. It has to be on the steep part of the curve, and past the top is where the curve is steep.

That also explains why the stretch from 0.7 to 1.0 was pinched on every axis. There the overshoot is under one unit and the curve is nearly flat, so moving a point a fraction of a dimension along it moves the error by almost nothing.

One draw, redrawn #

Drawn against the clipped sum, the arc essay’s picture loses its most striking feature. There, past the top, the iteration’s curve rose visibly more slowly than either other filter’s — that was the picture of the iteration reading the data. Here the best iterate sits at 43.0 at an error of 0.0732, and past it the iteration’s error climbs as steeply as Tikhonov’s and slightly to the left of it: at a clipped sum of 51 it is already four times its best, at 0.293, where Tikhonov at the same position is 0.168, a little over twice its own best of 0.0725. The iterates also stop marching steadily to the right. Between steps 54 and 70 the clipped sum wanders back and forth between 43 and 44.6 while the error hardly moves, because the iteration is rearranging weight among directions it has already admitted rather than admitting new ones.

The noise, which reverses #

The arc essay’s second finding was that the curves agree near the top by a trade: at the answer’s dimension Tikhonov carried 1.22 to 1.42 times the iteration’s noise and slightly less bias, and the two differences netted out. That trade was read as part of the iteration’s advantage. The clipped sum moves it.

At the answer, matched on the clipped sum, Tikhonov’s noise is 1.02 to 1.26 times the iteration’s — still above, by less. Past the top the order reverses. At 1.3 of the answer, matched on the sum, Tikhonov carries 1.02 to 2.44 times the iteration’s noise; matched on the clipped sum, 0.85 to 0.99, below one on every problem. At a fixed number of directions admitted, Tikhonov is the quieter filter past the top, and its error there is a few per cent below the iteration’s rather than more than double it.

The account in terms of the filters is short. Conjugate gradients’ overshoot is a factor above one on directions whose data coefficient is part signal and part noise; a factor of 1.81 on such a direction amplifies its noise by 1.81 as well as its signal. On the sum’s axis that amplification is paid for out of the dimension budget, so the iteration looks as though it bought signal cheaply. On the clipped axis it is not paid for at all — the direction counts once however it is weighted — and the noise it adds is simply there. An expiry date the noise does not move measured the same polynomial’s factors swinging past one as the iteration proceeds; what this adds is that the swing is a cost, not a skill.

The same accounting, on the other axis #

The arc essay made its case for the iteration with an exact piece of bookkeeping on the collection’s blur at 1% noise. On one draw the exact data’s coefficient stays above the noise’s through direction 28, so weight placed on directions past 28 is weight placed mostly on noise. At 1.2 times the answer’s effective dimension — step 32, carrying 28.72 — the iteration put 0.28 of its factors past that crossing and Tikhonov at the same dimension put 1.30, four to five times as much.

Redo it on the clipped axis and the four-to-five becomes about one. The iterate at 1.2 times the answer’s clipped sum is step 43, carrying a clipped sum of 28.44 and an effective dimension of 29.14; its overshoot has grown to 0.70. Its factors past direction 28, clipped, sum to 1.00. Tikhonov at a clipped sum of 28.44 puts 1.14 there. At the answer itself the two figures are 0.02 and 0.05. So once the comparison is made at an equal count of directions admitted, the iteration places almost as much weight on the noise-dominated directions as Tikhonov does, and more on the directions it has already admitted — which is what the overshoot is. The sum made the first difference look like a skill by charging the iteration nothing for the second.

The step numbers are worth a sentence of their own, because they are what a user of the iteration sees. The iterate the effective dimension paired with Tikhonov at 1.2 of the answer was step 32; the one the clipped sum pairs with it is step 43. Eleven further steps of conjugate gradients change the clipped sum by as much as they change nothing else, because past the top most of what a step does is move weight around among admitted directions. That is also why the iteration’s error curve against the step count, which a parameter that counts steps drew, turns up so slowly past its best: many of those steps are rearranging rather than admitting.

Where the optima land, in each coordinate #

The parameter neither knob is began from a coincidence: Tikhonov’s optimum and the iteration’s optimum land at nearly the same effective dimension, 22.40 and 23.17 on the collection’s blur. The arc essay measured the same thing over six problems and twelve draws and found Tikhonov’s best at 0.95 to 0.98 of the iteration’s — close, and consistently below.

On the clipped axis the gap closes as well. The median ratio of Tikhonov’s best to the iteration’s best, over twelve draws, runs from 0.982 to 1.005 across the six problems, against 0.953 to 0.981 on the sum; and the worst single draw moves from 0.67 to 0.92. On the collection’s blur the iteration’s best has a clipped sum of 22.06, against Tikhonov’s 22.40. The consistent shortfall on the sum’s axis was the iteration’s overshoot at its optimum — half a dimension or so — added to its side of the comparison and to no other. Counted as directions admitted, the two optima are one number to within a couple of per cent.

That strengthens the parameter essay’s reading rather than weakening it. Its claim was that the quantity every method’s optimum shares is how much of the data it admits. The effective dimension was the first measure of that to hand, and it measures it with a small bias in favour of any method that overshoots. A count that does not credit overshoot is the same idea measured more cleanly, and the optima agree better in it.

What the lead was #

The arc essay’s reading was that of the three filters only conjugate gradients reads the right-hand side, so at a matched dimension it places its weight where the data has content. The first half is true: the iteration’s polynomial is built from the data’s residuals and the other two filters are fixed functions of the singular values. The second half was a statement about the coordinate. On the sum of the factors, over-weighting a direction the data supports costs dimension, and admitting a new, noisier direction costs the same; the iteration does more of the first and so appears to spend its budget well. Counted as directions admitted, both filters have the same budget, and the iteration spends part of it amplifying what it already has — which past the top is noise as well as signal.

So the lead past the top was the overshoot, and the overshoot is not an advantage. That matters less for practice than it sounds, because no stopping rule worth using stops at 1.3 of the answer, and between 0.7 and 1.0, where rules do stop, all three coordinates agree and all three filters agree. It matters for what the effective dimension is. The parameter neither knob is proposed it as the regularisation parameter of the whole field — the quantity every method’s optimum shares. Near the optimum it is, in any of these forms. Away from it the sum is not a neutral coordinate: it is one in which the method that overshoots looks better than it is.

What the count leaves, below half the answer #

Nothing above touched the left of the picture, and the reason is visible in what the clipped sum does there: nothing, because at a third of the answer the iteration’s factors have not begun to overshoot — its overshoot there is under a tenth of a dimension on every problem. The gap below half is a difference in the filters’ shape, which the bias part of the error records: on the narrow blur at 0.3 of the answer, Tikhonov’s bias is 1.68 times the iteration’s matched on the sum and 1.69 times matched on the clipped sum.

Tikhonov’s factor is $\sigma_k^2/(\sigma_k^2 + \lambda^2)$, a smooth roll-off two decades wide in σ. When its effective dimension is small, λ sits among the large singular values and the roll-off shaves a little off many directions that should be kept whole, which the iteration’s steeper polynomial does not. The half count makes this worse rather than better, because it places Tikhonov’s λ exactly at a singular value and so puts half-weight on a direction the iteration keeps nearly entire. That is a property of Tikhonov’s filter and of no coordinate. A second blur, narrower than the first drew each filter’s bias as a resolution kernel, and a kernel is where a roll-off’s shape shows.

What this does not settle #

Six problems, one operator family — Gaussian blurs of a 64-point signal — and conjugate gradients on the normal equations without a preconditioner. A preconditioned run clusters the divided directions near one and should overshoot less, which would make the sum and the clipped sum closer to each other along its whole path; it is not measured here, though the shift had an edge, and the approximation moved it found the preconditioned runs on the sum’s arc near the top, where the overshoot is small anyway.

Two counts that do not credit overshoot were tried, and they agree above the top and disagree below. Whether some other coordinate — one that weights a factor by the data’s own signal-to-noise ratio in that direction, say — lines the curves up on both sides at once is not asked. It would have to know the noise level, which the three coordinates here do not, and it would be a second thing to choose — the price a second penalty is not a second parameter found rarely worth paying.

Still open: a count for the stopping rules, and the half count’s own filter #

Stopping rules in the clipped coordinate. A count that marks the edge and not the pace used the number of directions a truncated preconditioner divides to mark the point where a run stops landing on the answer’s path. That count is a half count in all but name. Whether the edge it marks, measured on the clipped axis rather than the sum, sits at the same fraction of the answer on every blur — or whether its five per cent agreement was itself partly overshoot — is one recomputation of that sweep.

A Tikhonov with a sharper roll-off. The gap below half is Tikhonov’s shape. A filter that interpolates between Tikhonov and truncation — factors $\sigma_k^{2p}/(\sigma_k^{2p} + \lambda^{2p})$, sharper as $p$ grows — would move from the Tikhonov band towards the truncation band below half, and the value of $p$ at which it best matches the iteration there would say how steep the iteration’s polynomial effectively is. That is a one-parameter family on the same six problems, and it is the direct measurement of the shape difference this essay could only name.