The method that cannot use a smooth answer

Four knobs and one floor put a truncation, a Tikhonov parameter, a conjugate gradient step count and a randomised rank on one 64-point deconvolution and found their best errors at 0.1445, 0.1406, 0.1426 and 0.1449. Four methods that share no arithmetic, three per cent apart. It read that as one obstruction met four times: the problem’s ill-posedness sets the floor, and the choice of knob moves a reader around on it by a few per cent.

The comparison held one thing fixed that it did not name. Every error in it was scored against the same answer — two smooth bumps and a step — and a single answer is a single point in a space the theory of regularisation divides very finely. The theory’s division is by smoothness, and it predicts that the four methods agree on some answers and part company on others, by an amount that grows without limit as the measurements improve.

That prediction is testable on the same operator with nothing changed but the answer. The test separates the four, and it separates them in the way the theory says: one method stops being able to convert a smoother answer into a smaller error, and the others keep going.

Smoothness written as a condition a vector meets #

“Smooth” has to mean something a vector can be checked against, and for a linear inverse problem the useful meaning is in terms of the operator itself. An answer is said to satisfy a source condition of order ν when it can be written as

x = (AᵀA)^ν w

for some vector w of modest size. The singular value decomposition makes that concrete. The component of x along the kth right singular vector is σₖ to the power 2ν times the component of w, so a larger ν is an answer made more and more of the directions the blur transmits well and less and less of the directions it destroys. At ν = 0 the condition says nothing. At ν = 4 the answer is almost entirely in the leading handful of singular vectors, because σ⁸ falls through eight orders of magnitude for every one that σ itself falls through.

It is the natural definition for a reason that is not obvious from the formula. The whole difficulty of an ill-posed problem is that the data carry the leading components of the answer and not the trailing ones; an answer smooth in this sense is one whose trailing components were small to begin with, so less is lost when a method gives them up. The Picard picture is the same statement read off the right-hand side: the coefficients uₖᵀb of a smooth answer fall faster than the singular values do, and the faster they fall the less the noise floor costs.

The convergence theory of every regulariser is stated in exactly these terms. With noise of relative size δ, the best error any method can guarantee over all answers of smoothness ν falls like δ raised to the power 2ν/(2ν + 1). That exponent is the optimal rate: one half at ν = ½, two thirds at ν = 1, four fifths at ν = 2, eight ninths at ν = 4, and approaching one as the answer becomes arbitrarily smooth. A method whose error falls at that rate is called order-optimal, and the interesting question about any method is how far up the ν scale it stays order-optimal.

Here the answers are constructed: the operator is the collection’s 64-point Gaussian blur, w is a fixed vector, and x is formed exactly from the decomposition. So every error below is a forward error against a truth that is known, which is the only reason a rate can be fitted at all.

The collection’s signal has no rate to report #

Before the smooth answers, the answer the floor essay used, run through the same measurement: six noise levels from 10% to 10⁻⁶, four noise draws at each, the geometric mean of the best error each method reaches, and a straight line fitted to its logarithm against the logarithm of the noise.

Three slopes under a tenth. A million-fold improvement in the measurement moves the best error by about a factor of two, which is what where the answer stops being in the data found for the truncation alone — 0.1630 at 10% noise and 0.0764 at 10⁻⁶ — and it is now the finding for all three.

The reason is the step. A discontinuity has components all the way down the spectrum, with coefficients that fall roughly like a power of the index rather than like a power of σ, so the signal is not (AᵀA)^ν w for any ν worth the name. Every method loses the same trailing components, because the noise hides them from every method equally, and none of the methods has any smoothness to exploit that the others lack. The floor essay’s agreement was therefore not a coincidence of four methods; it was a property of the answer. On an answer with no smoothness there is nothing for a method’s ceiling to bind against, and the floor is the problem’s alone.

That is also why the agreement survived every noise level the floor essay drew. Its spread moved between 0.7% and 15.4% as the noise changed, which the essay reported as a function that is not monotone; measured here, none of those numbers was ever going to diverge, because the rates they were differences of were all zero to within a tenth.

Six decades of noise, and one slope that stops #

Now the same measurement on answers that do have smoothness, starting at the top of the scale.

The slopes, all four smoothness orders, against the rate the theory calls optimal:

Read the columns rather than the rows. Truncation’s slope climbs with the smoothness at every step: 0.52, 0.72, 0.83, 0.94. Conjugate gradients’ climbs with it: 0.53, 0.73, 0.84, 0.89. Tikhonov’s climbs once, from 0.53 to 0.70 between ν = ½ and ν = 1, and then does not move again — 0.701, 0.705, 0.704, three numbers identical to within the noise of a fit over six points.

The saturation is visible without a fit. Tikhonov’s best errors at ν = 2 and at ν = 4 agree to two figures at every one of the six noise levels: 3.44·10⁻⁵ and 3.40·10⁻⁵ at 10⁻⁶, and the same pairing all the way up. Doubling the smoothness of the answer, which makes its trailing components smaller by many orders of magnitude, buys the penalty method nothing whatever. It buys truncation a factor of 3.5 at the same noise.

Two numbers in the table need a word so they are not read as more than they are. Tikhonov’s plateau is 0.70, not the two thirds the theory predicts for it. That is the finite range: a slope fitted from 10% noise down to 10⁻⁶ includes a noisy end where no method is yet in its asymptotic regime, and the overshoot is the same 0.04 at ν = 1, 2 and 4, which is why the check behind the figure places Tikhonov’s slope within 0.06 of two thirds rather than on it. And truncation’s 0.941 at ν = 4 is above the optimal 0.889. The optimal rate is a guarantee over every answer of that smoothness, the worst of them included; one particular w can do better than the worst case, and this one does. It is not a violation and it is not claimed as a finding about truncation.

Where the ceiling comes from: a bias that is always λ² #

The mechanism is short enough to state entirely, and it is a statement about the filter factors when the answer is a choice introduced.

Tikhonov keeps the fraction σ²/(σ² + λ²) of each component and throws away the fraction λ²/(σ² + λ²). The error of the regularised answer has two parts. The part caused by the noise is the noise divided by σ and multiplied by the filter, and it is largest where σ is near λ, at about δ/λ. The part caused by the filtering — the bias — is the discarded fraction of each of the answer’s own components, λ²/(σ² + λ²) times σ to the power 2ν times the component of w.

Where that bias is largest depends on ν. For ν at most 1 it peaks at the components with σ near λ, and its size there is λ to the power 2ν; balancing that against δ/λ puts the best λ at δ to the power 1/(2ν + 1) and the error at the optimal rate. For ν above 1 the peak moves to the top of the spectrum. The leading components are the ones a smooth answer is made of, and on every one of them the filter still discards λ²/σ² of what it keeps — a small fraction of a large number. The bias is then of order λ² whatever ν is. Balancing λ² against δ/λ puts the best λ at δ to the third and the error at δ to the two thirds, and no smoothness can change either, because the smoothness has stopped appearing in the balance.

That ceiling is called the qualification of the method, and Tikhonov’s is ν = 1. It is not a statement about how accurately the method is implemented or how well λ is chosen: the rates above use the λ that actually minimises the error, which no rule can beat. It is a statement about the shape of a rational filter, which never lets go of the largest components entirely.

Truncation has no such shape. It keeps its leading components whole, so its bias is made only of the components it discards, and those are small in exactly proportion to the smoothness. Conjugate gradients chooses its filter polynomial adaptively and can make it as flat near the top of the spectrum as the answer rewards. Landweber’s filter, 1 − (1 − ωσ²)ᵏ, releases the leading components exponentially fast in the step count. None of the three has a qualification, and on the table above none of them stops.

The best λ stops listening to the smoothness #

The mechanism makes a second prediction, and it is a sharper test than the error slopes because it is about the parameter rather than the outcome. Below the qualification the best λ should fall like δ to the power 1/(2ν + 1), so it depends on the answer’s smoothness. Past it, the balance is λ² against δ/λ whatever ν is, so the best λ should fall like δ to the third at ν = 2 and at ν = 4 alike.

Fitted over the same six noise levels and four draws, the exponent of the best λ is 0.503 at ν = ½, where the theory says one half; 0.354 at ν = 2 and 0.353 at ν = 4, where it says a third for both. The parameter follows the smoothness below the qualification and ignores it past it, to three figures.

That is a fingerprint worth having, because it can be read without the answer. A practitioner never has the true error, so a slope of best error against noise is not something a real data set offers. The trajectory of a chosen λ across repeated measurements at different precisions is available, and if it falls like the cube root of the noise across problems of very different character, that is evidence the penalty method is sitting on its ceiling.

The constructed signal, run through the same fit, gives an exponent of 0.917 — nearly proportional to the noise, and matching no smoothness order at all. That number is recorded and not explained. A step is not a source condition of any order, and nothing here says what the best λ ought to do on an answer that has none.

At the qualification, a constant rather than a rate #

ν = 1 is the boundary, and it is where the distinction between a rate and a constant is easiest to see.

At the boundary Tikhonov is still order-optimal, and its error is twice truncation’s at every noise level. A factor of two that does not grow is a constant: a method that costs twice as much data for the same accuracy is worse, but it is worse by a fixed exchange rate, and any improvement in the measurement benefits it in the same proportion. Past the boundary the factor grows without bound, and a method on its ceiling benefits less from every improvement than the method beside it.

The ratio of Tikhonov’s best error to truncation’s, drawn against the digits of measurement accuracy, is the single picture that makes the two cases different shapes.

Below and at the qualification the curves are horizontal: 0.96, 1.42, 2.03, fixed exchange rates. Past it they are straight lines on a logarithmic axis, rising by the difference between the two slopes for every decade of noise removed. At ν = 4 that difference is 0.94 minus 0.70, so each extra digit of measurement makes Tikhonov about 1.7 times worse relative to truncation; six digits of that compound to a factor of about 27, and the rest of the 38 is the ratio the curve already had at the noisy end.

The signal’s ratio of 0.96 is the floor essay’s result from the other side. On that answer Tikhonov is four per cent better than truncation at six digits, which matches the essay’s observation that the penalty was the best of the four at low noise. Both facts hold. They are facts about different answers.

Applying the penalty again raises the ceiling one order #

If the ceiling is the shape of the filter, a filter with a different shape should have a different ceiling, and there is a standard way to change the shape without changing the method’s character. Iterated Tikhonov solves the penalised problem, computes the residual of the result, solves the penalised problem again for a correction, and adds it. Two passes leave the fraction (λ²/(σ² + λ²))² of each component undone rather than λ²/(σ² + λ²); p passes leave its pth power. The bias on the leading components becomes λ to the power 2p, and the ceiling rises to the rate 2p/(2p + 1) — two thirds, four fifths, six sevenths.

At ν = 4, where the optimal rate of eight ninths is above all three ceilings, each penalty method sits at its own: 0.704, 0.826 and 0.861 against 0.667, 0.800 and 0.857, with the same small overshoot the single penalty showed. The ordering is the claim as much as the numbers, because an ordering is what a filter shape predicts and a noisy fit might not preserve. It is preserved at both smoothness orders past the first ceiling that the rate table measures, ν = 2 and ν = 4. Landweber, which has no ceiling, reaches 0.876 — above all three penalties and just below the optimal rate — and at ν = 2, where the optimal rate is four fifths, every method except the single penalty sits at or above it: truncation 0.826, twice-iterated Tikhonov 0.823, three times 0.841, Landweber 0.838, conjugate gradients 0.839.

So the qualification is not an accident of Tikhonov’s implementation and not a mystery. Each additional pass buys exactly one more order of smoothness the method can use, at the cost of one more penalised solve, and the measured slopes step up by the amounts the filter algebra says they should. A step that is not a unit of work found Landweber reaching conjugate gradients’ answer at a hundred times the products on the collection’s signal; on a smooth answer the slow iteration earns something the penalty cannot, and the comparison of cost has to be made again answer by answer.

What the four knobs were measuring #

With the rates in hand the floor essay can be re-read, and its central sentence needs one clause added rather than withdrawing. “The choice of knob is worth a few per cent” is true of an answer with no smoothness, and false by an amount that grows with the data’s accuracy on an answer that has some.

The spread of the four knobs at ν = 2 moves from 1.9 times at 10% noise to 3.1 at 1% and 4.2 at 0.1%; at ν = 4 and 10⁻⁴ it is 13.3. It widens as the measurement improves, which is the rate difference seen as a spread, and it widens fastest for Tikhonov. The truncation and the conjugate gradient step stay within about a third of each other throughout — 13% apart at ν = 2 and 1% noise, 31% at ν = 4 and 10⁻⁴ — as the rate table says they should.

The randomised rank is the fourth knob and it has not been fitted here. It lags truncation by 5.1 times at ν = 4 and 10⁻⁴ noise, so it too is losing something the truncation keeps. A sketch of a fixed number of random vectors approximates the leading subspace with an error that depends on how fast the spectrum decays beyond the rank kept — a bound that holds with probability measures that error — and on a smooth answer that small subspace error is multiplied by components that are not small. Whether the randomised rank has a qualification of its own, and what sets it, is not measured.

There is also a caution about what “better” means here. The comparison uses each method’s best parameter, found against the truth. Choosing without knowing measured what each practical rule costs against that oracle, and those costs are separate from the ceilings above. A penalty method with a well-chosen λ still sits on its ceiling; a truncation with a badly chosen K may land far above its floor. The rates say what each method could reach, which is the property that belongs to the method rather than to the rule used with it.

What the rates do and do not establish #

The measurement is one operator, one family of answers built from one w, four draws of noise at each of six levels, and a straight-line fit. Four things follow from it with confidence and three do not.

It establishes that on this operator Tikhonov’s rate stops rising at ν = 1 while truncation’s, conjugate gradients’ and Landweber’s do not, and that the stop is visible directly in errors that agree to two figures at ν = 2 and ν = 4. It establishes that the best λ’s exponent changes from one half to one third at the qualification, as the filter algebra predicts. It establishes that iterating the penalty raises the ceiling by one order per pass, in the predicted order. And it establishes that the constructed signal has no smoothness to separate the methods by, which is why an earlier comparison on that signal saw a single floor.

It does not establish the asymptotic constants: the fitted plateau of 0.70 against the theoretical two thirds is attributed to the finite range and has not been checked by extending the range, and the slope’s convergence to its limit with the range is itself unmeasured. It does not establish that the ceiling binds on answers that are smooth in some other sense — a function with bounded derivatives in the continuous problem corresponds to a source condition only under assumptions about the kernel that this measurement did not test. And it does not say how common smooth answers are in practice. A deblurred photograph with edges is closer to the collection’s signal than to ν = 4, and on it the penalty loses little; a smooth temperature profile recovered from boundary data is closer to ν = 4, and on it the penalty loses most of what the data offer.

Truncation is the best approximation there is in the sense of the singular value decomposition, and the table above is that optimality showing up in a rate. The penalty’s attraction has always been that it needs no decomposition — one sparse solve with a shifted matrix — and on a problem too large to decompose that remains decisive. What the rates add is the price of the convenience: nothing at all on a rough answer, and a factor that grows with every digit of measurement on a smooth one.

Where this goes from here #

A preconditioner, which changes the filter of an iteration rather than its speed. Conjugate gradients reached its optimal rate here by choosing its polynomial adaptively. A preconditioner changes the operator that polynomial is built on, and on a problem regularised by stopping, that changes where every step lands. A preconditioner that arrives past the answer measures what a preconditioner that is good by the usual standard does to the step worth stopping at, and finds the first preconditioned step is itself a Tikhonov solution — so it inherits this essay’s ceiling.

The parameter rule on a smooth answer. Every rate above uses the oracle’s parameter. The discrepancy principle is known in the theory to lose order-optimality for the single penalty earlier than the oracle does, and whether that shows on this operator, at which ν, and by how much, is a measurement the smooth answers now make possible.

And the randomised rank’s rate, which lagged truncation by a factor of five at ν = 4 and has not been fitted against the noise at all.