The corner reads the norm it is drawn in

The L-curve has been the worst rule in every measurement of parameter choice so far. Choosing without knowing found its corner costing 2.29 times the oracle’s error on the draw it drew and a median of 58% over sixteen. One draw in twenty found a median of 1.62 over a thousand draws at 0.1% noise and more than twice the oracle on 224 of them. It never fails catastrophically, and it is never close.

The first of those essays ended by naming the thing it had not measured. Everything in it penalised ‖x‖, and “penalising ‖Lx‖ for a derivative operator L is what a real deconvolution does” — with the remark that the L-curve “in particular changes shape, because ‖Lx‖ and ‖x‖ have different arms”. A parameter that counts steps then measured the general form’s main consequence for the answer: a derivative penalty has a null space, the constants cost it nothing, and on a signal with an offset its best error is up to 1.85 times better. It did not ask what the penalty does to the choice.

That is this essay’s question, and the answer is larger than a change of shape.

The same draws in a different norm #

The general-form problem minimises ‖Ax − b‖² + λ²‖Lx‖². With L the identity it is the standard form; with L₁ the first difference or L₂ the second, it penalises slope or curvature instead of size. The L-curve for each plots ‖Lx‖ against the residual, and its corner is found by the same three-point curvature on the same sixty-one values of λ.

Sixty draws of the step signal at 0.1% noise, the same draws under each penalty, every rule scored against that penalty’s own oracle:

The penalty did not make a better answer available. The best achievable errors are 0.1057, 0.1054 and 0.1054 — the same to three parts in a thousand. On this signal, which is zero at both ends and has no offset for a null space to absorb, the three penalties can reach the same answer.

It made the corner find it. Under ‖x‖ the corner’s median λ is a fifth of the oracle’s and its error is half as much again. Under ‖L₁x‖ the median corner is the oracle’s grid point and the cost is three parts in a thousand. The rule that was the worst of five has become, on this signal, as good as cross-validation’s median without cross-validation’s tail.

The same comparison at other noise levels says the effect is not a coincidence of 0.1%. At 1% noise the corner of ‖x‖ costs 1.37 and the corner of ‖L₁x‖ 1.03; at 0.01% they are 1.95 and 1.01. The standard corner gets worse as the noise falls and the derivative corner does not.

What the corner was reading #

The corner is a property of the curve, and the curve has two arms that come from two different places.

Split a regularised solution into the part that comes from the exact data and the part that comes from the noise, x(λ) = R(λ)b₀ + R(λ)e with b₀ the exact data, which is exact because the solution is linear in b. As λ falls, the first part approaches the truth and its norm levels off; the second is the noise amplified by ever-smaller singular values and its norm grows without limit. The vertical arm of the L-curve is the plotted norm being taken over by the second part. The corner is where that takeover becomes visible on logarithmic axes.

So the natural measurement is the noise share of the plotted norm: ‖L R(λ)e‖ divided by ‖L R(λ)b₀‖, at every λ. It is computable here because the problem was constructed and both parts of b are known, which is the same privilege the oracle rests on.

On this draw, under ‖x‖, the corner sits where the noise is 23% of the signal’s contribution to the norm. The oracle — the λ that actually minimises the error — sits where it is 2.6%. They are a factor of three apart in λ, and every component between them is a component the corner lets in that the oracle would not.

Under ‖L₁x‖ the same draw puts the corner at a share of 17% and the oracle at 17%. They are the same point.

The reason the two norms differ is in what each emphasises. The step signal’s own ‖x‖ is 5.75, and nearly all of it is the two smooth bumps, carried by the leading singular vectors. The amplified noise lives in the trailing ones, which oscillate. ‖x‖ weighs every component equally, so the noise has to grow until it rivals the bumps before the curve turns — and by then the answer is under-smoothed. A first difference weighs an oscillating component by up to two and a smooth one by nearly nothing, so the bumps shrink to a ‖L₁x‖ of 1.55 and the noise is doubled; the curve turns when the noise is a much smaller fraction of the answer, which on this signal is the right fraction.

Fifteen pairings, one share #

If that reading is right, it should hold for signals and penalties other than the pairing it was found on, and it should predict when the corner fails rather than only explain one success. So the measurement was repeated on five signals — the step signal; the same raised by one; the two bumps without the step; seven oscillations about a small mean; and four isolated spikes — under all three penalties, sixty draws each.

Every corner sits at the same share. Across all fifteen pairings the median noise share at the corner is between 0.115 and 0.207 — within a factor of two, while the pairings’ best errors run from 0.0026 to 0.57 and their oracles’ shares span more than two decades.

The oracle’s share decides the cost, and it sorts the pairings into three groups with nothing between them:

Each cell is the oracle’s noise share, then the corner’s median cost.

Where the oracle’s share is below 5%, the corner comes too late — at a λ less than half the oracle’s — and costs between 1.53 and 29 times the best error. Seven of the fifteen pairings are there. Where it is between 12% and 25%, near the corner’s own share, the corner costs at most 1.01: three pairings, and they are the three bold entries. Where it is above 30%, the corner comes early, at 1.85 to 4.6 times the oracle’s λ, and costs between 1.02 and 1.12: five pairings.

No pairing falls between the groups, and the check that runs this measurement refuses to state a class for one that does, rather than stretching a boundary to fit it.

A smooth signal hides its noise longest #

The worst pairing is the one that looks easiest: two smooth bumps, penalised by their size.

A signal made only of smooth bumps is represented almost entirely by the first few singular vectors, so its oracle can keep far more components than the step signal’s can without letting in noise that matters — its best error is 0.0045, against 0.106 for the step signal. That makes the oracle’s tolerance for noise tiny, a third of a per cent of the norm. The corner does not know that. It turns where noise is a fifth of the norm, as it does everywhere, which on this signal is sixty times more noise than the best answer contains.

The derivative penalties help and do not rescue it: 4.45 under ‖L₁x‖ and 2.38 under ‖L₂x‖, with oracle shares of 1.5% and 3.1%. A smooth signal is small under a derivative too, but not small enough to move the oracle into the corner’s band. Seven oscillations behave the same way for the opposite reason: their energy is at a frequency the blur attenuates, so the oracle has to keep components whose noise is already large, and it sits at a share of 1% to 3% under every penalty.

Spikes need no derivative #

The best pairing is the opposite case.

A signal of isolated spikes is small in ‖x‖ and enormous in any derivative norm, because a spike is nothing but slope and curvature. Under ‖L₂x‖ its own contribution dominates so completely that the noise share at the oracle is 42% at the median, and the corner, turning at a fifth, arrives before the oracle does. Under ‖x‖ the spikes’ norm is modest, the oracle sits at 17%, and the corner finds it.

So the claim that a derivative penalty is what makes the corner reliable is false in both directions. It helps a signal whose size is dominated by smooth structure, and it harms a signal whose size is dominated by jumps. What the corner needs is a norm in which the best answer happens to contain about a fifth as much noise as signal, and which norm that is depends on the answer.

Too late costs more than too early #

The table has an asymmetry that the three groups do not state. A corner that comes late — at too small a λ — costs between 1.53 and 29. A corner that comes early costs between 1.02 and 1.12, even when it is four and a half times the oracle’s λ.

It is the same asymmetry thirty-two coefficients instead of a noise level measured for the discrepancy principle and choosing without knowing found first: over-smoothing loses signal the answer was entitled to and does so slowly, and under-smoothing admits noise divided by singular values that fall exponentially and does so fast. Every rule in this field that errs, errs more cheaply towards larger λ. The L-curve under ‖x‖ errs the other way on the collection’s signal, which is the whole of its bad record.

The rules that read a residual barely notice #

The discrepancy principle reads only a residual, and a residual is a property of the data and the solution, not of how the solution is penalised. On the step signal it costs 1.064, 1.083 and 1.090 under the three penalties — slightly worse under a derivative, because each penalty’s oracle sits at a different residual and the principle’s target does not move with it.

Cross-validation reads a residual and a trace, and the trace does depend on the penalty. On the step signal its medians are 1.005, 1.006 and 1.011, and its worst draw among the sixty is about 25,000 times the oracle under every penalty: the second answer one draw in twenty measured comes along unchanged.

On the smooth signal all three rules improve under a derivative penalty, and not equally. The principle goes from 1.65 to 1.00, cross-validation from 2.87 to 1.27, the corner from 29 to 4.45. The penalty is a better description of that signal and every rule benefits; the corner benefits least, because it was never estimating the error in the first place.

What the penalty lets the answer be, and what it lets the rule find #

A parameter that counts steps measured the first half of this on a signal with an offset.

That figure is about the answer, and on the offset signal here the answer barely changes with the penalty — best errors of 0.0504, 0.0500 and 0.0500 at an offset of one and 0.1% noise. The choice changes enormously. The corner of ‖x‖ costs 2.81 on the offset signal, worse than on the signal without the offset, because the offset adds to ‖x‖ and makes the signal’s share of the norm larger still and the noise’s share at the oracle smaller: 1.6%. The corner of ‖L₁x‖ costs 1.01, because a constant is in the first difference’s null space and does not appear in the plotted norm at all.

So a null space matters twice. It lets the answer carry a component for free, which is what the earlier essay measured, and it removes that component from the norm the corner reads, which is what moves the choice. On this problem the second effect is the larger one.

What the corner is #

The L-curve’s corner is usually described as the balance point between fitting the data and controlling the solution. Measured, it is something narrower and more mechanical: a detector for the λ at which amplified noise has grown to about a sixth of the plotted norm — medians between 12% and 21% over fifteen pairings.

That is not an estimate of the error-minimising λ, and it was never going to be one, because the error-minimising λ is where the noise share of the answer balances the signal it loses, and the answer’s error is measured in ‖x − x★‖ against the true answer x★, not in the plotted norm. The two coincide only when the plotted norm and the error happen to weigh signal and noise alike at the best λ. Choosing a penalty for the L-curve is therefore choosing a prior about the answer that the corner will then read, and a wrong prior is read as faithfully as a right one.

Three things about this are measured and not derived, and are worth stating as such.

The band is an observation. Why the corner sits at a share of about a sixth, rather than a half or a twentieth, has not been derived here. It depends on how the curvature is estimated — three consecutive points on a grid of 7.5 values a decade, with no smoothing — and choosing without knowing already recorded that the smoothing is a parameter of the rule. A differently smoothed curvature would very likely move the band.

The groups are measured at 0.1% noise. At 1% noise the first-difference oracle on the step signal sits at a share of 30% and its corner still costs only 1.03; at 0.01% the oracle’s share is 7% and the cost 1.01. Near the band the error curve is flat enough that a factor of two in share costs little, so the boundaries in the table are sharper than the behaviour they summarise.

And every signal here was built. The share needs the exact data to compute and so is never available in practice. What is available is its consequence: a caller who knows only that the answer is dominated by smooth structure has reason to distrust a corner drawn in ‖x‖, and one who knows the answer is sparse has reason to distrust a corner drawn in a derivative.

Where this goes from here #

A rule built from the band. If the corner is a detector for a noise share, a rule could aim at the share directly: estimate ‖R(λ)e‖ from the noise level — which thirty-two coefficients instead of a noise level reads from the data — and choose the λ at which it reaches a target fraction of ‖L x(λ)‖. Whether the right target is a property of the signal, as the table suggests, or can be read from the data as well, is the measurement that would say whether the corner can be repaired or only replaced.

The corner inside a Krylov method. A parameter chosen on a smaller problem found the projected L-curve’s corner missing at twenty-four steps because the vertical arm had not yet been built. Under a derivative penalty the arm is built from different components, and whether it arrives earlier in the iteration is unmeasured.

Two penalties at once. A problem regularised in both ‖x‖ and ‖L₁x‖ has an L-surface rather than a curve, and on this evidence each of its two directions would read its own share; whether a surface has a corner at all, and what it would be a corner of, is where the L-curve’s reading runs out.

And the basis the penalty works in. The basis decides what a filter is showed that the spectral vocabulary of this field depends on the basis; under a derivative penalty the natural basis is the generalised singular vectors of the pair (A, L), and the share measured here in the ordinary basis may be simpler to state there.