A corner chosen without the iteration

The first step’s filter, kept for the whole run took the filter that conjugate gradients applies at its first step — $f(\sigma) = \min(1, \sigma^2/\lambda^2)$, a ramp with Tikhonov’s slope in its tail and a corner at $\sigma = \lambda$ — and used it as a method in its own right. On six deconvolutions it matched the iteration’s error to within 0.044 below half the answer and within 0.016 near it, closer than Tikhonov or any sharpened variant of it. But every one of those comparisons placed the ramp at the clipped position of the iterate it was compared with. A method that has to run the iteration to know where to put itself is a description of the iteration, not a replacement for it.

The essay’s last section asked for the replacement. “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 prediction is right for the one rule that reads only the residual. For the two that read something else, the ramp and the iteration part company — and in opposite directions.

Three filters, four rules, one oracle #

The problems are the earlier essay’s: a signal of 64 samples blurred by a Gaussian of width 1.5, 2.5 or 4 samples, with noise of one per cent or a tenth of one per cent of the data’s norm, and twelve noise draws of each. Three filters are placed on every draw. Tikhonov and the ramp are each evaluated at 161 values of their parameter, from $10^{-8}$ to one; the iteration runs 150 steps. Everything is computed in the blurring operator’s singular basis, so for each candidate the residual, the solution norm, the error against the known answer and the trace of $I -$ the influence matrix — the number of directions the solution discards, $\sum_k (1 - f_k)$ — are exact. For the iteration the factors are the ones its iterate implies, $f_k = \sigma_k c_k / (u_k^{\mathsf T} b)$.

Four rules place each filter. The discrepancy principle takes the most regularised candidate whose residual is within 1.01 times the noise’s norm. Generalised cross-validation minimises the residual squared over the trace squared. Its repaired form, which the minimum on the right arrived at for Tikhonov on fine grids, takes the first local minimum of the same function walking in from the regularised end. The L-curve takes the point of greatest curvature of the solution norm against the residual on log axes. GCV and the L-curve are not defined at a candidate that discards nothing, so both consider only candidates discarding at least half a direction.

Every placement is scored against the best error its own filter reaches on that draw — the oracle, which requires the answer and is not a method. The three oracles barely differ: the ramp’s best is between 0.95 and 1.02 of the iteration’s on every draw, which is the earlier essay’s finding restated as a minimum. So a difference in a rule’s score is a difference in how well the rule reads its filter, and not in what the filter could have reached.

The figure at the top of the page is the whole table. Read down a group to compare filters under one rule; read across the groups to compare rules on one filter.

The residual’s rule: the same price, a little earlier #

The discrepancy principle reads only the residual, and on the residual the ramp and the iteration are nearly the same object. Over seventy-two draws its placement of the ramp costs a median of 1.087 times the ramp’s best and at worst 1.30; its stop of the iteration costs 1.063 and at worst 1.27. On every one of the six problems the two medians are within three hundredths of each other.

Both halves of the prediction can be read off that figure and the next. The ramp is placed earlier than the iteration stops on 61 draws of 72, at a median of 0.84 of its best position against the iteration’s 0.86 — positions measured, as in the earlier essays, by the clipped sum of filter factors. And the ramp’s placement costs more than the iteration’s stop on 71 of 72 draws, always by a few hundredths. The “same ten per cent” holds as a median and not as a share: 40 of the ramp’s placements are within a tenth of its best against 47 of the iteration’s, and 59 of Tikhonov’s.

The reason it is earlier is the reason the prediction gave, made precise. The discrepancy principle stops at the first candidate whose residual reaches the noise. The ramp’s residual is $\sum_{\sigma_k < \lambda} (1 - \sigma_k^2/\lambda^2)^2 (u_k^{\mathsf T} b)^2$, and it falls smoothly as the corner moves down through the singular values. The iteration’s residual falls fast at the first few steps and then slowly, and its iterates take bigger strides in position per unit of residual near the answer. So the same residual threshold is crossed by the ramp at a slightly more regularised position. Most of the few hundredths is that placement. Put the ramp at the position where the discrepancy principle stops the iteration, instead of where it places the ramp, and its median cost falls from 1.087 to 1.071 against the iteration’s 1.063: two thirds of the difference was where the ramp stood, and the third left over is the shape of its filter at the same position, the residue of the 0.016 by which the two filters differed near the answer in the earlier comparison. Being earlier is not a virtue here: on these problems both filters’ best positions sit beyond where the discrepancy principle stops — the rule’s familiar lean towards over-regularising, which costs a few per cent on the iteration, as a stopping rule that follows the run it is given measured over forty draws, and carries over to the ramp unchanged.

The curvature’s rule: the ramp is a filter again #

The L-curve reads the shape of a curve, and here the ramp and the iteration are not the same object at all.

At blur width 4 the two curves lie on top of each other, and the iterates are a sequence of points whose spacing collapses: the first dozen steps cover the descent of the vertical arm, and the next hundred and thirty pile up along the horizontal one. A curvature computed from three neighbouring points at that spacing finds its maximum in the clustering, not in the bend. The iteration’s corner on this draw is step 133, where its best is step 13, and the error there is 547 times the best. The ramp’s corner, on the same curve drawn at evenly spaced values of its one parameter, is 1.35 times the ramp’s best.

Across all seventy-two draws the iterates’ corner is more than twice the iteration’s best on 44 and within a tenth on two, with a worst of 896 times. The ramp’s corner is more than twice its best on 26, within a tenth on thirteen, worst 15.9 — and Tikhonov’s is more than twice on 24, within a tenth on eight, worst 9.9. The L-curve is not a good rule on these problems for any filter; the corner reads the norm it is drawn in found why, for Tikhonov, and found it costing 1.53 times the oracle at its median exactly as here. What the ramp changes is which kind of bad. On the ramp the L-curve fails as it fails on Tikhonov, by a factor of one and a half; on the iteration it fails by the spacing of the points, by a factor of hundreds.

The dial shows the boundary of that. At the two narrower blurs the iterates spread more evenly along the curve and their corner is no worse than the ramp’s on this draw: 2.28 against 4.44 at width 1.5, and 2.96 against 2.93 at 2.5. The catastrophes are on the widest blur, where the singular values fall fastest and the iteration reaches the bend in the fewest steps.

The trace’s rule: two different failures #

GCV reads the residual and the trace, and on the trace the ramp and the iteration differ in kind.

The ramp is a linear filter: for a fixed corner its solution is a fixed matrix times the data, and its influence matrix is diagonal in the singular basis with the ramp’s factors on the diagonal. Its trace is exact and means exactly what GCV assumes. The iteration is not linear in the data — its polynomial is built from the data — and the factors its iterate implies reproduce that iterate for this right-hand side only. Their sum is a number, not the trace of anything; late in the run, where the iterate is mostly amplified noise, some factors run far above one or below zero and the “trace” reaches 105, 165 and 787 on draws of a 64-sample problem. That is where the iteration’s GCV failures all are: 26 draws of 72 more than twice its best, every one of them placed between step 21 and step 150, the worst at 102 times.

The ramp’s GCV has none of those failures on the two wider blurs — never worse than 2.3 there — and a different one on the narrowest.

The ramp’s curve has a dip at about 33 directions discarded, where its best solution is and where the iteration’s GCV minimum also falls. And it has a second, lower value at its left end, where the ramp discards 0.76 of one direction. The ramp’s factors reach exactly one: once its corner falls below a singular value, that direction is kept whole. At width 1.5 the smallest singular value is $3 \cdot 10^{-5}$, inside the range of corners searched, so the ramp passes through a stage at which it discards a fraction of the last one or two directions and nothing else. There the GCV function is that fraction squared, times those directions’ data coefficients squared, divided by the same fraction squared — the last coefficients themselves, squared, which are pure noise. When the noise in those one or two directions happens to be small, that value is below the genuine dip, and GCV picks a solution that divides the noise by $3 \cdot 10^{-5}$.

It happens on four draws of the twenty-four at width 1.5, at 83, 100, 607 and 696 times the ramp’s best, and a fifth draw stops at six directions discarded at 16.5 times. The four are the same two noise draws at both noise levels, which is what a property of one or two noise coefficients should do. Four in twenty-four is the same order of rarity one draw in twenty found for GCV’s second answer on Tikhonov — four to six in every hundred — concentrated here on the one blur whose far end can be reached. On the wider blurs the smallest singular value is $10^{-13}$ or below, the ramp never reaches it within the corners searched, and the far end is not on the curve. More samples take the floor and leave the dip traced exactly this minimum for Tikhonov on square systems, where the residual and the trace reach zero together as λ does; Tikhonov reaches that end only in the limit, the ramp at a finite corner, which is why it shows on a 64-sample problem here.

The repair is the one the minimum on the right found. Walking in from the regularised end and taking GCV’s first local minimum skips the far-end value on the ramp, because the genuine dip comes first; and it skips the iteration’s late-run dips for the same reason. With that rule the ramp’s worst draw is 1.25 times its best and 64 of 72 are within a tenth; the iteration’s are 1.19 and 63. No other rule on any of the three filters lands within a tenth more often.

What the prediction got right, and what it could not see #

The prediction reasoned about the residual, and about the residual it was right: the ramp’s falls smoothly past its corner, the discrepancy principle places it slightly earlier, and the price is the iteration’s price give or take three hundredths. It treated GCV and the L-curve as residual rules too, and they are not. Each reads a second quantity, and on that quantity the ramp is a different object from the iteration.

On the curvature it is a better one, because it is a curve drawn at a parameter its user controls rather than a sequence of points at a spacing the iteration chooses. On the trace it is a more honest one, because a linear filter has a trace and an iteration does not — and the honesty exposes it to GCV’s oldest failure, the far end of the scale, which the iteration’s dishonesty happened to hide behind its own. The ramp’s catastrophes and the iteration’s have nothing in common except the rule that repairs both.

The result for a code is short. The ramp needs the singular values and the data’s coefficients, which are the price of a dense deconvolution and not of an iterative one; given those, the ramp placed by GCV’s first minimum from the regularised end is within a tenth of the best error the iteration can reach on 64 of 72 draws and never more than a quarter off — and a quarter off the iteration’s best is a better worst case than any rule here achieves on the iteration itself without the same repair. Choosing without knowing scored GCV as landing on the oracle’s λ exactly on one Tikhonov problem. On the ramp it lands within a tenth on nine draws in ten, and the tenth draw is where the repair was needed.

What seventy-two draws do not show #

The comparison is the one a parameter that counts steps set up between the iteration’s integer knob and Tikhonov’s real one, with a third filter whose knob is real but whose shape is the iteration’s. Six problems of one kind: a smooth blur of a piecewise-smooth signal, sixty-four samples, white noise. A problem whose singular values level off rather than decaying — an operator with a floor — would put the ramp’s far end inside the searched range on every problem and make the repair necessary everywhere rather than on the mildest blur. The ramp is evaluated at 161 corners; a search over the sorted singular values themselves, as the earlier essay proposed, would hit the far end exactly at the last singular value and make the unrepaired GCV’s failure certain on any draw whose last coefficient is small. The discrepancy principle is told the noise’s norm exactly, which no code knows; a rule that has to be told how good its answer will be measured what a wrong noise level costs, and nothing here changes that. The iteration is plain conjugate gradients on the normal equations with no preconditioner and no restarts.

Still open: the directions the data skips, and a power read off the decay #

The skipped directions. The factors the iterate implies show it passing over a direction now and then, a factor of 0.7 among neighbours at one. The ramp cannot skip anything, and on the residual and the corner it now does what the iteration does. If the skipped directions are always ones whose data coefficients sit below the noise, the iteration is reading its data correctly where the ramp cannot, and that is where its small advantage in the discrepancy principle’s price — three hundredths — would come from. The prediction with a sign is that on every draw the directions with factors below 0.8 among neighbours above 0.95 have coefficients below the noise level, and that zeroing them in the ramp recovers at least half of the iteration’s three-hundredth advantage.

A power read off the decay. The power ramp $1 - (1 - \sigma^2/\theta)^m$ settled at $m$ between 1.27 and 1.50 past the answer on all six problems. If $m$ is set by the decay rate of the singular values — which for a Gaussian blur is known in closed form — the power ramp can be built from a predicted $m$ and a corner placed by GCV’s first minimum, and would then be a fixed filter that keeps the iteration’s behaviour past the top as well as before it. The prediction is that $m$ predicted from the blur width alone lands within 0.1 of the iteration’s on every problem, and that the power ramp placed this way is within a tenth of its best on as many draws as the ramp.