The first step's filter, kept for the whole run

A tail from Tikhonov and a corner from truncation went looking for the iteration’s sharpness and found that it does not have one. It placed a family of filters between Tikhonov and truncation, $1/(1 + (\lambda/\sigma)^{2p})$, at the same clipped sum of factors as each conjugate-gradients iterate on six deconvolutions, and found that any p from two to four brings the family within about a tenth of the iteration below half the answer where Tikhonov, at $p = 1$, misses by 69 per cent. But no single p described the iteration’s own factors. Its local sharpness was Tikhonov’s in its tail and two to five on its shoulder, and the reason was in an identity: after k steps the iteration’s filter is $1 - \prod_j (1 - \sigma^2/\theta_j)$ over its Ritz values $\theta_j$, and below all of them that is $\sigma^2 \sum_j 1/\theta_j$ to first order — Tikhonov’s slope, with a corner where the smallest Ritz value sits.

At the first step there is one Ritz value and the filter is exactly $\sigma^2/\theta_1$: a ramp. The essay ended by proposing it as a method in its own right. “The first step’s filter, $\min(1, \sigma^2/\lambda^2)$, has the iteration’s tail and a corner, and one parameter.” The prediction with a sign was that it would match the iteration below half the answer better than every member of the family — under the 0.106 that $p = 3$ reached — and that “it loses the match near the answer, where the iteration’s corner has softened.”

A ramp, placed like every other filter #

The comparison is the one the last three essays have made, so that each of them can be read against this one. Six problems — Gaussian blurs 1.5, 2.5 and 4 grid points wide on a 64-point signal, at 1% and 0.1% noise — and twelve draws of each. Every iterate of conjugate gradients on the normal equations is placed by the sum of its filter factors with each clipped to lie between zero and one, the coordinate the overshoot was the lead settled on because it does not count a factor above one as more than one direction. The best iterate’s position is the answer’s. At each fraction of it from 0.3 to 1.3 the nearest iterate is taken, and a filter is placed at the same clipped sum by solving for its parameter. The number reported is the median over draws of the filter’s error divided by the iterate’s, and the figure at the top of the page is the widest departure from one over six problems on three stretches: below half the answer, from 0.7 to the answer, and past it.

The ramp’s factors are already clipped, so its clipped sum is its sum, and placing it is a bisection on λ exactly as it was for the family. Nothing about the coordinate favours it. At the first step it is not just like the iteration: it is the iteration with its factors above one cut back to one, and the ratio there is between 0.986 and 0.999.

The second filter needs no placing at all, and the reason to add it is the other half of the identity. After one step the iteration’s tail and its corner are two numbers. The tail is $\sigma^2 \sum_j 1/\theta_j$ and the corner, where the factors first reach one, is the smallest Ritz value. The filter

$$f(\sigma) = 1 - \left(1 - \frac{\sigma^2}{\theta_{\min}}\right)^{m}, \qquad m = \theta_{\min}\sum_j \frac{1}{\theta_j},$$

taken as one past the corner, has exactly that tail — its first-order term is $m\sigma^2/\theta_{\min}$ — and exactly that corner. It replaces the product over every Ritz value with a power of the smallest one’s factor. At the first step $m = 1$ and it is the ramp. It is built from the iterate’s own Ritz values and is not fitted to anything, so it asks the question the earlier essay could only gesture at: whether two numbers carry the iteration’s behaviour, or whether the rest of its polynomial does work too.

Below half the answer: closer than any sharpened Tikhonov #

The rows at the top of the hero figure are the earlier family, and the two shaded rows are the filters this essay adds. Below half the answer the ramp’s widest departure from the iteration is 0.044. The best member of the family was $p = 3$ at 0.106, the second power 0.113, truncation 0.335 and Tikhonov 0.693. The prediction’s first half holds, and by more than it asked: the ramp is not just inside 0.106, it is less than half of it.

That is not a surprise once the stretch is described in steps rather than fractions. The earlier essay counted them: on every problem the iterate nearest 0.3 of the answer is the first one, and by 0.5 the iteration has taken between two and five steps. The ramp is the first step’s filter exactly, and the stretch below half is mostly the first step. A member of the family can approximate a ramp’s shoulder; the ramp is the shoulder.

By the second step the two have already parted. The figure is one draw of the middle problem at half the answer. The iteration’s factors are the dots, the power ramp built from its two Ritz values is the solid curve under them, and the ramp is the dashed one. The power read off the Ritz values is 1.53: the iteration’s tail is half as heavy again as a ramp with the same corner would have. Placed at the same clipped sum, the ramp compensates by moving its corner — it reaches one at 1.45 times the iterate’s half-point where the iteration reaches it at 1.64 — so it sits a little to the right of the iteration in its tail and a little to the left on its shoulder. Both differences are a few hundredths of a factor. Across six problems at this fraction they move the error by at most four per cent, which is the 0.044.

Near the answer: the corner softens, and it costs nothing #

The second half of the prediction is where the measurement disagrees. From 0.7 of the answer to the answer itself, the ramp’s widest departure from the iteration on any problem is 0.016. That is closer than the family’s best member there, the second power at 0.018, than Tikhonov at 0.031 and than truncation at 0.089. It is the closest any fixed filter in this sequence of comparisons has come to the iteration on that stretch.

The band is the whole run at once. Below half it wanders between 0.956 and 1.034 as the first few steps leave the ramp’s shape. From 0.7 to the answer it lies between 0.998 and 1.016 on every problem, a ribbon two hundredths wide pressed against one. Past the answer it falls away to between 0.85 and 0.95, as every fixed filter does. Turn the dial to the second power and the ribbon near the answer is about as narrow, which is the earlier essay’s finding that near the answer the choice hardly matters; what the dial shows is that below half the second power is wider than the ramp on both sides.

The prediction reasoned from the shape of the factors. By the answer the iteration’s corner has indeed softened: the power ramp’s m, which is one at the first step, is between 1.4 and 2.0 near the answer on every problem, so the iteration’s filter is no longer a ramp. What the measurement says is that the change in shape does not reach the error. At a matched clipped sum, the directions where the ramp and the iteration differ are the ones near the corner, and near the answer those are the directions whose data coefficients are around the noise level — where the answer stops being in the data, in the Picard plot’s terms. Letting a few hundredths more or less of such a direction through trades a few hundredths of signal against the same amount of noise, and the two very nearly cancel. A filter’s shape matters in proportion to how unequal signal and noise are at the place where the shapes differ, and at the answer’s corner they are as equal as they get. That is also why one arc, and what each filter pays to be on it found every filter on the same curve there.

The same draw at the answer shows what has and has not changed. Seventeen steps in, the power read off the Ritz values is 1.37, and the power ramp still lies on the iterate’s factors from the tail to the corner. The ramp, placed at the same clipped sum of 21.9, now reaches one a little further out than the iteration does — 1.62 times the half-point against 1.58 — and runs a few hundredths under it in the tail. The one visible disagreement is somewhere else entirely: two directions well past the corner, at three and five times the half-point, where the iteration has let a factor fall to 0.92 and 0.70 among neighbours at one. Neither filter here can do that. It is the iteration skipping a direction whose data coefficient happens to be small, and it does not show in the comparison: over the twelve draws of this problem the ramp’s median error at the answer is within half a per cent of the iteration’s.

What the iteration’s polynomial does along the run #

The power m is the one number that says how the iteration’s filter differs from a ramp, and reading it along the run gives the shape a history. It is exactly one at the first step, on all six problems — the only step at which the iteration is a ramp. From the second step it rises, to between 1.6 and 2.4 by the middle of the run, and then settles to between 1.27 and 1.50 at 1.3 of the answer. Its least value past the first step is 1.27 and its greatest is 2.36.

In terms of the filter, m above one means the tail is m times heavier than a ramp with the same corner would give, or — read the other way — that the corner is $\sqrt{m}$ further out than a ramp with the same tail would put it. The rise to two in the middle of the run is the iteration’s polynomial putting its smallest Ritz value well past the half-point while the rest of its Ritz values keep the tail heavy. That is the shoulder the earlier essay measured as a local sharpness of two to five. The settling past the answer is the smallest Ritz value coming down into the noise-dominated directions, where conjugate gradients starts to fit noise and its error begins to rise.

None of this is a property the error ratios can see below the answer, as the previous section found. It becomes visible past the top, and there the two filters this essay adds behave in opposite ways.

Past the top, two numbers follow the iteration #

The third column of the hero figure is the stretch from 1.1 to 1.3 of the answer. Every fixed filter in the earlier family sat between 0.116 and 0.172 from the iteration there, and the ramp joins them at 0.155. All of them are below one, which is the reversal the overshoot was the lead found once directions were counted by the clipped sum: at an equal number of admitted directions past the top, a fixed filter carries less noise than the iteration. The power ramp does not join them. It stays within 0.056 of the iteration past the top, as it did below half (0.035) and near the answer (0.022).

The power ramp has no overshoot. Every one of its factors is at most one. It is a fixed shape — a power of one linear factor — set by two numbers the iteration hands over at every step, and it follows the iteration’s error through the stretch where the iteration is losing to every other fixed shape. So whatever the iteration is doing wrong past the top, two numbers carry most of it, and neither of them is the overshoot.

The figure splits the gap directly. The ramp’s bar is what a fixed shape gains over the iteration at 1.3 of the answer: between 0.05 and 0.15 of its error. The top bar is the iterate itself with its overshoot removed, every factor above one cut back to one. That recovers between 28 and 58 per cent of the ramp’s gain — on the narrowest blur at 1% noise 0.042 of 0.149, on the widest at 0.1% noise 0.028 of 0.049 — and less than half on four of the six problems. The middle bar, the power ramp, sits only two to six per cent below the iteration, because it reproduces the part of the iteration that is not overshoot.

So the iteration’s deficit past the top has two parts and the overshoot is usually the smaller. The larger is the weight of its tail against its corner. At a matched clipped sum a ramp, with $m = 1$, puts less weight in its tail than an iteration with $m = 1.4$ and makes up the count on its shoulder; the iteration’s heavier tail lets through more of the small singular values’ noise, and that is what it loses on. The earlier claim that overshoot was the iteration’s whole difference past the top was made in a coordinate built to neutralise it, and it was half right: the clipped count removed the overshoot’s bookkeeping, and what remained was this.

Two numbers, and what they settle #

The measurements close the question the earlier essay asked about the iteration’s shape, with a qualification. A filter defined by the tail’s slope and the corner’s position — the smallest Ritz value and the sum of all the reciprocals — reproduces the iteration’s error to within six per cent everywhere from the first step to well past the answer, on six problems over twelve draws each. That is the earlier essay’s account made quantitative: the iteration is a Tikhonov tail and a corner, and the rest of its polynomial — the Ritz values between the smallest and the largest, the exact product rather than a power — moves the error by a few per cent.

The qualification is that the two numbers are the iteration’s own. The power ramp is a fixed shape only in form; its two parameters come from the Krylov process at each step and nothing that does not run the iteration can supply them. A method that wanted the iteration’s results without the iteration would have to predict $\theta_{\min}$ and $m$ from the problem, and $m$ wanders between 1.3 and 2.4 in a way that depends on the run.

The ramp is the opposite trade. It is a single parameter, placed by the same clipped count as every other filter, and it needs nothing from the iteration at all. It matches the iteration up to the answer more closely than anything else measured, and past the answer it is better than the iteration by the ten to fifteen per cent every fixed filter is. As a method it is Tikhonov with its tail kept and its shoulder replaced by a corner, and on these problems it is never worse than the iteration it was taken from.

That makes the iteration’s whole advantage over fixed filters, on this evidence, a matter of where the corner is put rather than how the filter gets there. A count that marks the edge and not the pace found the stopping rules keyed to the number of directions past a threshold. For a ramp that number is exactly the count of singular values above its corner, which makes the ramp the one filter in this comparison whose parameter and whose count are the same thing.

What six problems do not show #

Six blurs of one 64-point signal, at two noise levels, all with smoothly decaying singular values and no gaps. A spectrum with a gap would put the ramp’s corner either side of it with nothing between, which is where the family’s sharper members and the iteration’s polynomial would differ most, and none of these problems has one. The iteration is conjugate gradients on the normal equations in double precision for at most 150 steps, before the loss of orthogonality a parameter that counts steps found disturbing the Ritz values on longer runs; on a run long enough to lose it, the Ritz values the power ramp is read from would include copies, the sum of reciprocals would double-count them, and the power ramp would no longer be the iteration’s. And the comparison is at a matched clipped sum throughout. That is the coordinate in which the ramp and the iteration were found to agree; a comparison at the best error of each, rather than at a matched count, would ask a different question and is the one the overshoot was the lead already answered.

Still open: a corner chosen by a rule, and the directions the data skips #

The ramp’s own stopping rule. Every comparison here placed the ramp at the iterate’s position, which requires the iteration. Placed instead by the rules the iteration uses — the discrepancy principle, generalised cross-validation, the corner of an L-curve — the ramp would be a method with no iteration at all. Its corner is a singular value, so each rule becomes a search over a sorted list. The prediction with a sign is that it stops within the same ten per cent of the best error that the iteration’s own stopping rules do, and earlier, because a ramp’s residual falls more smoothly past its corner than the iteration’s does.

The skipped directions. The factors in the figures above show the iteration passing over a direction now and then — a factor of 0.7 among neighbours at one. Neither filter here can skip anything. Whether the skipped directions are always ones whose data coefficients are below the noise, so that the iteration is reading the data correctly, is a count over the same runs, and it is the one place the iteration could be doing something neither a ramp nor a power ramp can.

A predicted power. The power m settles between 1.27 and 1.50 past the answer on all six problems. If it settles at a value set by the decay rate of the singular values — and for a Gaussian blur that rate is known — the power ramp could be built without the iteration from a predicted m and a corner chosen by a rule, and would then be a fixed filter that keeps the iteration’s behaviour past the top as well as before it.