The rule that is wrong in the right direction

What a cheap preconditioner has to leave alone built a preconditioner a real deconvolution can afford and left one thing unusable about it. The construction is a blur approximated by a matrix the cosine transform diagonalises, inverted only in the directions whose eigenvalue in that approximation is at least τ. Above a certain τ the preconditioned run reaches the unpreconditioned floor in a quarter of the steps. Below it the run reaches a worse answer, and there is no step at which stopping recovers it. The τ at which that changes was found by sweeping against the truth, and a real problem has no truth to sweep against.

A stopping rule that follows the run it is given named two candidates for reading τ off the data and measured neither. The first was the approximation’s coefficients of the data read as a Picard plot — the diagnostic that says, in the operator’s own singular basis, where the data stops carrying signal. The second was the size of the first preconditioned step, on the reasoning that a run past its edge has already fitted the noise by the time it has taken one step, and something about that step should say so.

Both fail here, and they fail in ways worth having. The third thing tried is not a new rule at all.

The reading that says where the data runs out, and not where the cutoff is #

The Picard reading is the obvious one because it is the reading this field already trusts. In the operator’s singular basis it compares the data’s coefficients against the singular values and finds the index past which the coefficients have stopped falling: past that index the data is noise, and a filter that admits those components admits noise. Where the answer stops being in the data measured it on this problem and found it a real detector with a systematic overshoot.

The preconditioner has its own basis — the cosine basis, in which its approximation of the blur is diagonal — so the same reading can be taken there. Order the basis by the size of the eigenvalue, largest first. Plot the data’s coefficient in each direction. Smooth it, and take the index at which the smoothed curve is least, which is the rule the parameter-choice essays settled on and settled on for a recorded reason: the first index at which the coefficients stop falling is a feature of this signal’s shoulder rather than of its noise floor, and returns the same answer at every noise level. Then take τ to be the eigenvalue at that index.

At 1% noise the smoothed coefficients are least at position 50 of 64. The eigenvalue there is 6.7·10⁻⁹. Preconditioning every direction above that means preconditioning 51 of the 64, and the run it produces has a best iterate of 40.2 against the unpreconditioned run’s 0.1426 — two hundred and eighty-two times worse, and its best iterate is its first. The cutoff that keeps the floor sits at position 22.

The reason is visible on the same axes and is not a defect of the smoothing. The two curves fall at wildly different rates. The eigenvalue falls from 1 to 10⁻¹³ across the ordering; the coefficient falls perhaps four decades and then flattens onto the noise floor. The index where the coefficient flattens is a statement about the data — there is no more signal past here — and τ is a threshold on the eigenvalue. Converting one to the other through the ordering means reading a position on a curve that falls by thirteen decades against a position on a curve that falls by four, and thirty positions of disagreement is eight decades of τ.

Put the other way: the Picard reading is asking how many components the data supports, and the answer is about fifty, because a blurred signal at 1% noise really does have measurable content in fifty directions of a well-chosen basis. The cutoff is asking something else — which directions the approximation is right about, so that dividing by its eigenvalue does not divide by a number the operator does not have. The two questions have different answers and the Picard reading answers the wrong one. At a tenth of the noise it answers the wrong one a little less wrongly: position 45, τ = 2.4·10⁻⁷, a best iterate of 25.2 against 0.1054.

The step that never says anything #

The second candidate is cheaper to test and fails more completely. The reasoning behind it was sound: a preconditioner past its edge produces a first iterate that has already fitted the noise, and an iterate that has fitted the noise has a residual at the noise level. So walk τ down from large to small, and stop at the last τ whose first preconditioned step still leaves a residual above ‖e‖. That is the discrepancy principle applied to the cutoff instead of to the step, which is a pleasing symmetry and would have needed no new quantity at all.

Swept over thirty-three cutoffs from 10⁻⁰·²⁵ to 10⁻⁸·²⁵ at 1% noise, the rule never fires. The first preconditioned step’s residual stays above the noise norm at every cutoff on the grid, including the ones whose runs are ruinous. The rule walks to the bottom of the grid and returns 5.6·10⁻⁹, which is the Picard reading’s answer by a different route and is the bottom of the grid by construction.

The reason is worth stating because it says something about the first step that the earlier measurements did not. A preconditioned first step is not the Tikhonov solution — a preconditioner that arrives past the answer showed that it is, exactly, for the shifted construction, where the preconditioner is AᵀA shifted by α, and the first step is the Tikhonov solution at $\lambda^2 = \alpha$ times a scalar. The truncated construction is not that. It leaves the small directions at a factor of one rather than dividing them, so its first step is a weighted combination that reaches well down the spectrum in the preconditioned directions and barely at all in the others. What that produces is an iterate that is badly wrong in a way the residual does not report: it has overshot in some directions and not started in others, and the two errors do not cancel in the residual because the operator maps them to different places. At 10% noise, where the noise floor is high enough that any overshoot reaches it, the rule does fire. At every level a real problem would be at, it does not.

That is the same shape as the limitation the earlier measurement ended on — the residual reports that something has been fitted to the noise level; it cannot say what — arriving one step earlier. A residual is one number, the run has sixty-four directions to be wrong in, and the rule needs to know which.

The cutoff was already chosen #

The third thing tried is not a rule for τ. It is the observation that the earlier measurement already measured the answer and did not notice: the smallest τ that keeps the floor sits at a third to a half of the Tikhonov oracle’s λ, at three noise levels. That sentence was written as a calibration — a way of saying where the edge is in units a reader has — and it is a rule, because λ is the one parameter this field has spent decades learning to choose from data.

So: take any rule that chooses λ, and set τ = λ/2. Nothing else. The half is the top of the measured range rather than its middle, which is a choice that has to be justified and is justified below.

The justification is that the two mistakes are not the same mistake. Sweep the multiple c in τ = c·λ across three decades, and the curve is flat on one side and a cliff on the other. From about c = 0.4 upward the median run reaches within 2% of the unpreconditioned floor, and stays there at c = 32. Below c = 0.2 it starts to lose the floor, and at c = 0.032 it reaches 2.73 times it.

What the plateau costs is visible on the same sweep and is not the error. The median best step rises with c: 6 at c = 0.27, 9 at c = 1, 13 at c = 3.7, and 19 at c = 13, where the unpreconditioned run’s own best is at 19. A cutoff far above the right one leaves almost every direction unpreconditioned, so the preconditioner has quietly stopped being a preconditioner and the run is the plain run again, with the plain run’s answer and the plain run’s step count. That is the whole penalty for erring high: the speed is given back and the answer is kept. Erring low gives back the answer and keeps the speed — the run at c = 0.032 reaches its best at step 7 or 8, briskly, and what it reaches is nearly three times worse.

An asymmetry that steep is what lets a single constant serve at all. The plateau is two decades wide. A rule whose λ is within a factor of three of the right one lands on it from anywhere in that range, and the constant only has to put the typical rule somewhere in the middle.

The rule with the wrong habit #

Which turns the question into: which λ rule. The three that choosing without knowing scored — the discrepancy principle, generalised cross-validation and the L-curve — disagree about λ in a way that is well known and well measured. The discrepancy principle needs to be told ‖e‖ and habitually overshoots: its λ sits a factor of 2.2 above the oracle’s at 1% noise and 3.0 above at 0.1%. GCV needs nothing but the data and lands at 0.71 and 0.89 of the oracle’s. The L-curve lands at 0.25 and 0.19.

As λ rules the ranking is the expected one. Over twenty-four draws at 1% noise the median Tikhonov error is 1.034 times the oracle’s for GCV, 1.041 for the discrepancy principle and 1.444 for the L-curve. GCV wins, narrowly, which is what it is supposed to do and is why it is the rule that needs no noise level.

Read as cutoffs the ranking inverts, and not by a little. The discrepancy principle’s median run reaches 1.008 times the unpreconditioned floor and its worst draw of twenty-four reaches 1.12. GCV’s median run reaches 1.066 and its worst reaches 198. The L-curve’s median is 1.890 and it has no good draws to hide behind.

The oracle λ itself — the λ that actually minimises the Tikhonov error, which no rule can have — gives a median run of 1.076 and a worst of 1.49. It is beaten, as a cutoff rule, by a rule whose λ is more than twice as large as its own. That is the sentence this essay exists for. There is no sense in which the discrepancy principle is a better rule; it is a rule with a bias, the bias is in the direction the plateau lies, and a cutoff rule is scored on where it lands rather than on how close it is.

At a tenth of the noise the same thing is true with the numbers further apart. The discrepancy principle’s λ is 3.0 times the oracle’s, its median run is 1.006 of the floor and its worst is 1.04. GCV’s λ is 0.89 of the oracle’s, its median run is 1.017, and its worst draw is 272 times the floor.

Whose tail it is #

It would be convenient to say that the map from λ to τ manufactures GCV’s tail, and it does not. GCV has a known and unpleasant failure mode as a λ rule — on some draws its criterion is nearly flat and its minimiser runs away to a λ far below anything sensible — and the same twenty-four draws show it: GCV’s worst Tikhonov error is 10⁵ times the oracle’s at 1% noise and 1.4·10⁴ at 0.1%. Its median of 1.034 is an honest median of a distribution with a very long tail, and every statement above about the median is a statement about the middle of that distribution.

The basis decides what a filter is is the same observation about a different pair of objects: a quantity read in one basis is not the same quantity read in another, and the cutoff lives in the preconditioner’s basis while λ lives in the operator’s. So the cutoff does not create the tail. What it does is remove the protection. A Tikhonov solve at a λ ten thousand times too small is a bad answer and a bounded one: the filter admits components it should not and the solution is noisy, and the damage is whatever those components contain. A preconditioned run at a cutoff ten thousand times too small does not merely admit those directions; it divides by the approximation’s eigenvalue in directions where the approximation is wrong about the operator, which multiplies the error the approximation was already making. That is the 198 rather than the 10⁵ — it is smaller than GCV’s own λ tail, because the run is stopped early and the truncation leaves the very smallest directions alone. The point is that the two failures are not the same failure and the ordering between them is not preserved.

Which is why the right way to state the finding is not use the discrepancy principle. It is: a cutoff rule is a bet on a plateau, and the property to look for in a candidate is not accuracy but which way it is wrong. The discrepancy principle has to be told ‖e‖ and the standard criticism of it is exactly that; thirty-two coefficients instead of a noise level measured what it costs to be told a wrong one and found a cliff at a definite understatement. Every one of those criticisms still stands, and noise that spares the answer and fools the rules adds another by breaking two rules with correlated noise while improving the best answer available. What is added here is that its remaining defect — a λ too large by a factor of two or three — is worth nothing at all in this application, and the rule that does not have that defect is worse for it.

Moving the constant, and what stops mattering #

The half can be moved and the ranking does not move with it. At τ = λ/4 all three rules slide a quarter-decade down the curve; the discrepancy principle is still on the plateau, GCV is closer to its edge, and the L-curve is further off.

This is the practical content of the asymmetry and it is why the constant is not a fourth parameter to tune. A quantity that has to be right to within a factor of two is a parameter, and the step that stops mattering is the construction that removes one by making a late stop harmless rather than by choosing well. A quantity whose useful range spans two decades, whose cost for being too large is steps rather than accuracy, and which a standard λ rule places inside that range without being asked, is a calibration. The distinction matters because the whole object of this exercise is to end up with a preconditioner a code can use, and a preconditioner with a knob that has to be tuned against the answer is not one.

What a code would actually do #

Assemble the cosine approximation of the blur, which costs a transform. Run a λ sweep on the Tikhonov problem, which needs the SVD and is therefore exactly the thing the iterative method exists to avoid — so in practice run the discrepancy principle on the iteration’s own residual history, which is the construction a parameter that counts steps started from, and take the λ implied by the step it stops at through the filter-factor correspondence. That last step is not measured here and is the obvious next thing to measure: the whole argument above uses a λ obtained from a dense sweep, and a code that could afford the dense sweep would not need the preconditioner.

What is measured is that the quantity the cutoff needs is the regularisation parameter, that a rule’s bias matters more than its accuracy in supplying it, and that two readings which seemed more natural — one from the data’s own coefficients, one from the first step’s residual — fail by two orders of magnitude and by never firing at all.

What this does not settle #

One operator, one signal, one approximation. The Fourier approximation is not swept here, and a stopping rule that follows the run it is given found it failing differently past its edge; whether τ = λ/2 puts it on a plateau of the same width is unmeasured.

Twenty-four draws are twenty-four draws, and the whole argument turns on a worst case. A worst of 198 over twenty-four draws is a statement that the tail is reached at that rate and nothing about how far it goes. The medians settle well inside twenty-four; the maxima do not settle at all, and the only honest reading of them is as a lower bound on how bad the tail is.

The noise is white and its norm is known exactly wherever the discrepancy principle is used. Both of those are the assumptions the rule is most often criticised for, and neither is relaxed here.

Still open: the λ the iteration already knows, and the shape of the plateau #

The λ from the run rather than from a sweep. The cutoff is read off a λ that costs an SVD to obtain, which is the cost the method exists to avoid. A run’s own discrepancy stop corresponds to a filter, and that filter corresponds to a λ; whether the λ read off the plain run’s stopping step lands on the plateau as reliably as the swept λ does is the measurement that would make the whole construction self-contained, and it is one dense reference solve away.

Where the plateau’s left edge is, in units the rule can see. The cliff sits near c = 0.2 at both noise levels measured, and c is a ratio to a λ that itself moves by two decades across those levels. Whether the left edge is at a fixed c, or at a fixed number of preconditioned directions, or at a fixed fraction of the operator’s own spectrum, is three different predictions that the two levels measured here cannot separate — and the third would say the plateau’s edge is a property of the operator rather than of the noise.

A rule with the bias built in. If what a cutoff rule needs is a rule biased upward, GCV plus a deliberate factor would serve as well as the discrepancy principle and would need no noise level. What factor makes GCV’s worst draw bounded, and whether that factor is stable across noise levels or merely across these two, is the direct test of whether the finding is about the discrepancy principle or about the direction of the bias.

The pair as one parameter. The cutoff is now chosen and the step count is not, and the run has both. Whether the two are two parameters at all is the question the next essay asks, and the answer changes what a stopping rule on this construction is even choosing between.