The shift had an edge, and the approximation moved it

A fast-transform preconditioner for a deconvolution starts from an approximation of the blur that a cosine transform diagonalises exactly, and it has to be made invertible, because the approximation’s eigenvalues run down to rounding. There are two ways to do it. A truncation divides every direction whose eigenvalue μ is at or above a cutoff τ by $\mu^2$ and leaves the rest alone. A shift divides every direction by $\mu^2 + \alpha$.

What a cheap preconditioner has to leave alone measured both, and the shift came off badly: at α = 10⁻³ its best iterate was 0.749 against the unpreconditioned run’s 0.143, and the essay’s title records the moral — a cheap preconditioner has to leave the small directions alone, which is what a truncation does and a shift does not. The parameter neither knob is then put the truncation’s failure on a map. Every iterate carries an effective dimension, the sum of the filter factors it is implicitly applying; the unpreconditioned run climbs an arc of them to its best answer; and a truncated run either samples that same arc more coarsely or, below an edge, misses it entirely. That essay ended with a prediction for the other construction: the shift “never reaches the unpreconditioned floor at any parameter, so it has no edge to find”, and its runs “should sit off the arc at every shift”.

The prediction is wrong on both counts, and the way it is wrong locates the shift’s trouble much more exactly than “a shift does not leave the small directions alone”.

At a large shift, the shift works #

The earlier measurements of the fast shift started at α = 10⁻³ and went down. Start higher and the picture is different.

On the collection’s usual problem — 64 samples, a Gaussian blur 2.5 grid points wide, 1% noise — and over eight draws of the noise, the fast shift with a square root of 1, $10^{-0.25}$ and $10^{-0.5}$ reaches 1.001, 1.001 and 1.013 times the unpreconditioned floor. It reaches them in 19, 16.5 and 12 steps, against the unpreconditioned run’s 19 or 20. At the middle of those three settings 97% of the run’s iterates lie on the unpreconditioned arc. There is nothing to distinguish that run from a truncated one doing the same job: it is on the path, it is faster, and it ends at the answer.

Below that the fast shift falls off something. At $10^{-0.75}$ it reaches 1.084 times the floor; at 10⁻¹, 1.51; at $10^{-1.5}$, 5.9; at 10⁻², 22.7; and by $10^{-2.5}$ it is 69 times the floor. The truncation, on the same axis, is within two per cent of the floor down to $10^{-1.75}$ and reaches 5.7 times it only at 10⁻³. The same shift applied to the exact operator — $(A^{\mathsf T}A + \alpha I)^{-1}$, computed through the singular value decomposition with no approximation in it — tracks the truncation closely and ends at 8.0 times the floor at 10⁻³.

So the shift has an edge. It is a very sharp one, it is a quarter-decade from where the shift stops being useful at all, and past it the failure is ten times worse than either of the other two constructions’. That last fact is the source of the reputation, and all of the earlier measurements were made on the far side of it.

The edge in the units of the answer #

The count essay put the truncation’s edge in the right units. A truncation divides some number of directions, and the number can be compared directly with the effective dimension of the answer — the dimension the unpreconditioned run’s best iterate carries. A count that marks the edge and not the pace found the truncated runs leaving the arc when the count reaches that dimension, on three blurs and at two noise levels.

A shift divides every direction partly, so it has no count, but it has the same quantity measured continuously: its own effective dimension, $\sum_k \mu_k^2/(\mu_k^2 + \alpha)$, which counts a direction far above $\sqrt{\alpha}$ as one, a direction far below it as nothing, and a direction at it as a half. For the exact shift the sum is taken over the operator’s singular values rather than the approximation’s eigenvalues, and it is then exactly the effective dimension of the Tikhonov solution at $\lambda^2 = \alpha$.

On this axis two of the three constructions fall through a half at the same place. On the collection’s blur the truncation’s share of the run on the arc drops through 50% at 0.96 of the answer’s dimension and the exact shift’s at 1.05. The fast shift’s drops through it at 0.66. Turned to the narrow blur, 1.5 points wide, the three are 1.03, 1.02 and 0.77; turned to the wide one, 4 points, they are 0.89, 1.05 and 0.49.

The exact shift’s curve has a feature the others lack, and it is worth reading before it is mistaken for noise. Its share climbs back to 100% just before the edge, at 0.97. That is the point where its best iterate is its first step — and a run whose best is its first step has exactly one iterate up to its best, which is either on the arc or not. It is: the first step of conjugate gradients preconditioned by $(A^{\mathsf T}A + \alpha I)^{-1}$ is the Tikhonov solution at $\lambda^2 = \alpha$, and at this α that solution carries 22.0 of effective dimension against an arc that ends at 22.8. A preconditioner that arrives past the answer proved the identity and measured what happens below it:

Past that point the exact shift’s first step is a Tikhonov solution under-regularised by a little more each time, and no later step can undo it. So the exact shift’s edge is not a coincidence of the arc’s geometry: it is the Tikhonov solution’s own dimension crossing the answer’s, and the measured edge, 1.02 to 1.05 of the answer’s dimension, says so.

Six problems, three constructions #

One blur might have been arranged. The six problems of the count measurement — three blurs at 1% and at 0.1% noise, answers carrying from 15.7 to 45.2 of effective dimension — are the test.

The exact shift leaves the arc at 1.02, 1.05, 1.05, 1.03, 1.02 and 1.04 of the answer’s dimension. The truncation leaves it at between 0.89 and 1.03, a spread that is the quarter-decade grid’s resolution on the short arcs of the wide blur. The fast shift leaves at 0.77, 0.66, 0.49, 0.64, 0.70 and 0.57 — never above four-fifths of the answer, and lowest of all on the wide blur at 1% noise, where it gives up when its dimension is half the answer’s.

Two constructions obey one law and the third does not, and of the two that obey it one is a shift. The law is not “truncate rather than shift”. A shift whose dimension is measured against the operator it is actually shifting leaves the arc exactly where the count says it should. What moves the fast shift’s edge is the thing the exact shift does not have and the fast truncation has in the same amount: an approximation of the operator.

Where the error appears first #

The approximation is not wrong everywhere. The blur on a finite interval has to decide what happens near the ends, and the cosine transform’s approximation decides it by reflecting the signal. The operator itself cuts the kernel off at the ends and rescales each row to sum to one. The two agree in every row but the first and last seven, and their difference $A^{\mathsf T}A - M^{\mathsf T}M$ has a norm of 0.115 and a rank of 20 on the collection’s blur — a small, low-rank error, living near the two ends.

If that error is the cause, the fast shift’s answer should go wrong at the ends of the signal before it goes wrong anywhere else.

It does, and the separation is clean. At a square root of the shift of $10^{-0.25}$ the two shifts’ best iterates differ at the ends by less than a tenth: 0.0268 of the signal’s size for the fast shift against 0.0248 for the exact one, and 0.1311 between the ends for both. At $10^{-0.75}$, the fast shift’s edge, the error at the ends has grown to 0.0588 against the exact shift’s 0.0232 — two and a half times as much — while between the ends the two are 0.1315 and 0.1313. The whole of the fast shift’s loss at its edge is in sixteen samples.

A quarter-decade further the error at the ends is 0.1355, four and a half times the exact shift’s, and the interior has begun to follow: 0.1487 against 0.1314. By $10^{-1.5}$ the ends carry 0.69 and the interior 0.40 against the exact shift’s 0.022 and 0.131. The failure starts where the approximation is wrong and spreads inward, which is the order in which it would happen if the iteration were fitting something that exists only at the ends.

What the shift does to the error it does not divide #

The ends explain where. The remaining question is why the shift and not the truncation, since both use the same approximation, and the truncation’s edge sits where the count says.

The answer is in the directions each construction declines to divide. Every preconditioner here is built in the cosine basis, and in that basis the preconditioned operator is the approximation’s own part — nearly the identity on the divided directions — plus the approximation’s error, multiplied by the preconditioner. In the directions whose μ is below the parameter, a truncation multiplies by one. A shift multiplies by $1/(\mu^2 + \alpha)$, which for μ well below $\sqrt{\alpha}$ is nearly $1/\alpha$.

In those directions the truncation leaves the error at 0.074 of the operator’s scale when τ is $10^{-0.5}$ and at 0.025 when τ is 10⁻² — it shrinks, because fewer directions are left undivided as τ falls. The shift scales the same error to 0.61 at $10^{-0.5}$, 4.0 at 10⁻¹, 28 at $10^{-1.5}$ and 209 at 10⁻², rising by a factor of seven or so for every decade α falls. On the narrow and wide blurs the numbers are within a factor of two of these, and the lines nearly coincide: this is a property of shifting an approximation that is wrong at the ends, not of any particular blur.

The undivided directions are exactly the ones a regularising iteration relies on being small. They are the directions where the data is mostly noise, and a preconditioned run reaches the right answer only because conjugate gradients sees them as tiny eigenvalues and leaves them for later. On the exact operator a shift keeps them tiny — their preconditioned eigenvalues are $\sigma^2/(\sigma^2 + \alpha)$, far below one. On the fast approximation the shift adds to each of them an error term of size up to 209 in these units, which is not tiny at all. The iteration sees a handful of large eigenvalues that belong to no feature of the signal, fits them in its first steps, and what it fits is the noise in the sixteen samples where the approximation and the operator disagree.

The truncation never does this, because it never scales the undivided directions. It has an error term there too, but at a factor of one it stays at a few hundredths — below the level at which conjugate gradients notices it before the answer is reached.

The rule that serves the other two #

The count essay ended with a rule for the truncation that survives a change of operator: set the cutoff at the discrepancy principle’s own λ. It survives because the count at that λ is the effective dimension of the discrepancy principle’s Tikhonov answer, and that answer carries slightly fewer dimensions than the best one — the margin the rule that is wrong in the right direction found and named. A shift invites the same rule in its natural form, $\alpha = \lambda^2$, because on the exact operator that makes the first step the discrepancy principle’s Tikhonov answer outright.

On the exact operator the rule does exactly what the identity promises. Over twenty-four draws on each of the six problems the exact shift’s best iterate is within 7.1% of the unpreconditioned floor on its worst draw, and it gets there in a median of one to four steps — it is a Tikhonov solve with a stopping test attached. The truncation at the same λ has a worst draw of 1.063 and takes six to fifteen steps. The fast shift at the same α has a median draw of 1.96 times the floor on the narrow blur at 1% noise, 2.29 on the collection’s blur and 4.01 on the wide one; at a tenth of the noise its medians are 5.3, 10.3 and 10.7, and its worst draw is 16.4 times the floor. It also takes longer than the truncation to get there, fourteen steps to eight and a half on the collection’s blur.

The reason is the one the edges predict. At α = $\lambda^2$ the fast shift’s own effective dimension is the Tikhonov answer’s — 19.3 on the collection’s blur at 1% noise, 0.85 of the answer’s 22.8 — which is inside the band where the exact shift and the truncation are safe and well outside the band, below 0.49 to 0.77, where the fast shift is. A parameter rule is a statement about where in the answer’s dimension to stand; the fast shift has a smaller safe region than the rule was calibrated for, and the rule puts it past its edge on every problem measured.

So the same λ, taken from the same data by the same rule, is the best of the three settings for the exact shift and a safe one for the truncation, and it multiplies the error of the third by two to eleven. Nothing about the rule’s choice of λ differs between the three rows of the figure. The whole difference is what the approximation’s error does in the directions each preconditioner leaves undivided, which is the previous section’s measurement arriving in the units a user would notice.

What the reputation should have been #

“A cheap preconditioner has to leave the small directions alone” was the right conclusion from the wrong measurement. The small directions matter not because a shift divides them — the exact shift divides them identically and has the ideal edge — but because a shift divides the approximation’s error in them, and a cheap preconditioner is cheap precisely because it is an approximation.

That restatement has three consequences a code can use. A shift on a fast approximation is safe while its own effective dimension is below about half the answer’s, and there it reaches the floor in two-thirds of the unpreconditioned steps; a truncation on the same approximation is safe to nearly the whole of the answer’s dimension and reaches the floor in under half. A shift on an approximation that is exact at the boundary — a problem whose own boundary condition is the reflection the cosine transform assumes — should behave like the exact shift. And the edge of any preconditioner built from an approximation depends on where the approximation is wrong as well as on how much it divides, so the count law of the truncated construction is a law about the truncation keeping the approximation’s error out of the undivided directions, not only a law about counts.

What this does not settle #

Three Gaussian blurs of one family, one signal, one fast transform, and eight draws of the noise per setting. The approximation’s error here lives at the ends of the signal because the blur’s boundary is the only place a Gaussian on a uniform grid departs from its reflected approximation; a spatially varying blur would put the error everywhere, and there the split between ends and interior would say nothing.

The fast shift’s edge is located on the same quarter-decade grid as the truncation’s, and at 0.49 to 0.77 of the answer its spread is larger than the grid can explain. Why the wide blur loses soonest is not measured: its arc is the shortest, so each undivided direction’s error is a larger share of what the run has to reach, and that is a plausible reason rather than a measured one.

The scaled error in the undivided directions is a statement about the preconditioned operator, and the link between its size and the step at which conjugate gradients picks it up is argued, not computed. The Ritz values of the preconditioned run would show the large spurious eigenvalues arriving, and they are not drawn here.

Still open: a shift that knows where the approximation is wrong, and the same arc for Tikhonov #

A shift corrected at the ends. The approximation’s error is rank 20 and known before the first step: it is the difference between two matrices, both of which are in hand. A preconditioner that shifts the approximation and then applies a rank-20 correction for the boundary — the construction the circulant the problem did not contain used to solve through a wrap — would remove the term that moves the edge. Whether it restores the exact shift’s edge, and what the correction’s own conditioning does as α falls, is a measurement with every ingredient already built.

Whether the arc is the same arc for Tikhonov. The exact shift’s first step is a Tikhonov solution, and along its edge its runs sit on the iteration’s arc. That suggests the whole Tikhonov curve of error against dimension lies on the arc, not only its top — which the regularisation parameter’s own measurement has never been asked. A sweep of λ scored at matched effective dimension against the unpreconditioned run answers it directly, and the exact shift’s first steps are already that sweep, sampled at the α grid here.

The Ritz values of the failing run. If the fast shift fails by fitting large spurious eigenvalues first, the Ritz values of its early steps should show them, one or two at a time, well above the approximation’s cluster at one. That would turn the mechanism above from an argument into a measurement, and the ghost-eigenvalue measurements already have the instruments to draw it.