A third penalty on a flat floor

A second penalty is not a second parameter regularised a deconvolution with two penalties at once, $\lambda_1^2\|x\|^2 + \lambda_2^2\|L_1x\|^2$, and measured the surface of the error over both parameters. The best pair beat the better single penalty by between nothing and 3.1% over ten draws on five signals; one of its two parameters was exactly zero on 30 to 70 per cent of draws; and choosing the wrong one of the two penalties cost up to 54%. The surface, it concluded, was “a choice between two curves with a knob nobody needs”.

It also proposed the cheapest test of its own explanation. If mixing is worth little because whichever penalty suits the signal already does the work, a third penalty should buy less than the second did, and the optimum should sit on a face of the cube — one of its three parameters at zero — a larger share of the time. “That is a prediction with a sign, and it is the cheapest test of whether the mechanism proposed here is the mechanism.”

The first half of the prediction holds more completely than it asked. The second half fails, and the way it fails is the more useful finding.

Three penalties, one cube #

The problem is the one the whole field has used: a 64-point signal blurred by a Gaussian kernel of width 2.5 points, noise of $10^{-3}$ relative to the data, and five signals — a step, a step on an offset, two smooth bumps, an oscillation and four spikes — with eight seeded noise draws of each. The penalties are the norm itself, the first difference $L_1$ and the second difference $L_2$, so the regularised solution minimises

$$\|Ax - b\|^2 + \lambda_0^2\|x\|^2 + \lambda_1^2\|L_1x\|^2 + \lambda_2^2\|L_2x\|^2 .$$

Each parameter takes fourteen values, zero and thirteen spaced half a decade apart from $10^{-6}$ to 1, and every one of the 2,743 cells of the cube is solved for every draw; the error is the distance from the true signal relative to its size. A cell with one parameter zero lies on a face of the cube, with two zero on an edge, and the best single penalty, best pair and best triple are the best cells on the edges, the faces and the whole cube.

What each decision is worth #

Three decisions can be priced separately, and they are worth very different amounts.

Which penalty. For the smooth bumps and the oscillation, the worst of the three single penalties costs a median of 2.07 times the error of the best, and up to 2.82. For the step, the offset and the spikes it costs 1.01 to 1.04 — on those signals the three penalties are interchangeable. This is the decision the earlier essay found costing 54% with two candidates; with the second difference among the candidates it costs a factor of two on the signals whose curvature the second difference measures.

Whether to mix two. The best single penalty over the best pair is a median of 1.0002 to 1.0136 across the signals, and at most 1.074 on any draw. Adding the second difference to the candidates has made mixing a little more valuable than it was — 1.4% on the smooth signal’s median draw against the earlier study’s 3.1% worst case — but it is still small beside the choice.

Whether to add a third. The best pair over the best triple is 1.0000 on the median draw of every one of the five signals. Its largest value on any of the forty draws is 1.0066, two thirds of a per cent, on the offset step. The prediction’s first half — the third buys less than the second — holds on every signal, and not narrowly: the third penalty is worth nothing measurable at all.

The face that is not where the minimum is #

The second half of the prediction was that the best triple would sit on a face. On twenty-eight of the forty draws it does: one or two of its parameters are zero. On the other twelve — four each on the step, the offset and the spikes — the best cell in the cube has all three parameters nonzero. Taken at face value that is the prediction failing: more than a quarter of the time the optimum is in the interior.

It is not a failure of the mechanism, and the measurement that shows it is how much the interior minimum is worth. On every one of the twelve draws where the best triple uses all three penalties, the best cell with one parameter zero is worse by at most 0.66 per cent, and on most of them by a few hundredths of a per cent. The interior minimum beats the face by less than the difference between neighbouring cells of the grid. Where it lands is decided by which of many nearly equal cells happens to be a hair lower on this draw’s noise.

The count of cells on the floor says the same thing directly. Within one per cent of the best error lie a median of 160 cells for the step, 97 for the offset, 73 for the spikes, 56 for the oscillation and 18 for the smooth signal. The three signals whose best triples wander into the interior are exactly the three with the widest floors, and the smooth signal, whose floor is eighteen cells, never leaves a face. On a floor of a hundred and sixty cells, asking whether the argmin has a zero coordinate is asking about a tie.

So the right form of the prediction is not “the optimum sits on a face” but “a face is always as good as the optimum”, and that holds on every draw: within one per cent on all forty, within 0.66% at worst. The earlier essay’s edge share — 30 to 70 per cent of best pairs with a zero parameter — was the same kind of statistic, and on this evidence it measured the width of the floor as much as the mechanism.

Where the floor is #

A slice through the cube at the best triple’s norm parameter shows the floor’s shape, and the shape is the same on every signal: the cells within a per cent of the best form a line. One parameter is pinned to a single grid value and the other is free, from zero up to a threshold past which it starts to hurt. On the first draw of the step, with the norm parameter at $10^{-3}$, nine cells lie within a per cent: the second-difference parameter at $10^{-2.5}$ and the first-difference parameter anywhere from zero to $10^{-2.5}$. On the offset the roles swap — the first difference pinned near $10^{-2.5}$, the second free from zero to $10^{-3}$. On the spikes the line bends into an L. On the smooth signal it is a single cell, at a first-difference parameter of $10^{-1.5}$ and a second-difference parameter of $10^{-1}$.

That line is the whole mechanism in one picture. A penalty whose parameter is below its threshold changes the solution by less than the noise does, so it is invisible; a cube with one penalty doing the work has a floor that extends along every other penalty’s axis down to zero, and the far end of that line is a face. Whether the grid’s minimum lands at the far end, on the face, or somewhere along the line depends on differences smaller than a per cent, which is why twelve best triples are in the interior and why none of them is worth anything.

What differs between signals is how much of the rest of the slice is close. On the step 36 of the 196 cells are within ten per cent and 133 within fifty; on the offset 36 and 182; on the spikes 50 and 172. On the smooth signal only 11 are within ten per cent and 15 within fifty, and on the oscillation 8 and 18. Where one penalty matches the signal’s structure — curvature, for the bumps and the oscillation — the slice climbs steeply away from the line, choosing that penalty matters a factor of two, and neither of the others can substitute for it. Where no penalty matches especially well, the slice is a broad shallow basin, the choice hardly matters, and every penalty is a passable substitute for every other. Neither shape leaves room for a third.

What a penalty is, component by component #

A reason the floor is so flat can be read off what each penalty does to the blurred signal’s components. In the singular basis of the blur, a Tikhonov solution damps each component by a filter factor, and the three penalties differ only in how that damping is weighted across components: the norm damps every component by the same rule, while the first and second differences weight the damping by roughly the square and the fourth power of the component’s frequency, damping the rough components harder than the smooth ones. Choosing without knowing drew the single-penalty filter as the whole of the method; three penalties give a filter whose weight is a positive combination of three profiles.

That family is not much richer than its members. The blur’s singular values fall off sharply, so above the point where noise swamps signal every penalty damps the components almost completely and below it almost not at all; what the penalties change is the shape of a transition a few components wide. A combination of profiles can move that transition and soften or sharpen it slightly, and the error is decided by where it sits far more than by its shape. A second parameter lets the transition’s shape change a little; a third lets it change a little more, in a direction the first two already nearly cover. The measured gains — a per cent for the second, nothing for the third — are the size of what the shape is worth once the position is right.

The contrast with choosing a polynomial’s degree is instructive. The degree that is safe to overshoot found a valley steep on one side and shallow on the other, so rules erring in one direction were safe. Here the valley along a penalty’s own parameter is steep enough — the second-difference parameter has to be within a half-decade step on the smooth signal — but the directions across other penalties are flat to the point of not being directions at all. A parameter rule on such a cube would be choosing a point on a line of ties, and a parameter chosen on a smaller problem is the reminder that even one parameter’s rule carries a bias; more parameters would give it more ties to choose among and nothing to gain.

Which penalty, measured separately #

The single-penalty errors put numbers on the valley. On the smooth signal the norm alone costs a median of 2.15 times the best triple and the first difference 1.61, while the second difference alone is within one per cent of it. On the oscillation the first difference is worst at 2.12, the norm 1.47, and the second difference again within one per cent. On the step, the offset and the spikes all three are within two per cent. The second difference alone is within about one per cent of the best triple on the median draw of every signal. The corner reads the norm it is drawn in found an L-curve’s corner depending on which penalty’s norm was plotted; here the choice of norm is the whole of the decision’s value, and the L-curve is the instrument that would have to make it.

The route that squares the problem #

The earlier essay solved its two-penalty problems by a factorisation that never forms the squared matrix, and left open whether the care was visible: “whether the factorisation route is measurably more accurate than the normal-equations route at the λ these sweeps actually visit — or whether the regularisation has already made the difference invisible.”

The cube here is solved by the normal equations — the symmetric matrix $\Sigma^2 + \lambda_0^2 I + \lambda_1^2G_1 + \lambda_2^2G_2$ in the blur’s singular coordinates, factored by Cholesky — because it is much cheaper per cell and there are a hundred and ten thousand cells. On the two-penalty cells of one draw per signal, the error the two routes report differs by at most $1.7\cdot 10^{-13}$ relative, and by at most $1.2\cdot 10^{-13}$ where the error is within twice the best. The road that squares the problem is a real road — forming $A^{\mathsf T}A$ squares the condition number — but here the regularisation term is added before anything is solved, and at $\lambda \ge 10^{-6}$ it lifts the smallest eigenvalue of the normal matrix far enough that the squaring costs nothing the error can see. The answer to the earlier question is the second of its two options.

What the mechanism has now survived #

The mechanism proposed was that one penalty already does the work. It has been tested twice now, with a sign each time, and passed where the prediction was sharp: a third penalty buys nothing measurable, less than a second did. The part of the prediction that failed — the argmin’s location — failed because the argmin is not well defined on a floor of a hundred cells, and the replacement statement, that a face is always within a per cent, is the one a user can rely on. Four knobs and one floor found several parameters sharing a floor below which none of them could push the error; three penalties are three more knobs on one floor.

What survives as advice is short. Choose the penalty that matches the signal’s structure; do not mix. On signals with curvature the choice is worth a factor of two, and the second difference is the one that wins; on signals without it the choice barely matters. Mixing two is worth a per cent at best, and a third is worth nothing. And a parameter rule for several penalties at once would be optimising over a floor, which is the setting in which one draw in twenty found rules landing far from the best on a single parameter.

What forty draws of one blur do not show #

One blur, one size, one noise level, five signals and three penalties; all errors are against the truth, which no rule knows. The grid is half a decade in each parameter, so differences smaller than a neighbouring cell’s are not resolved — which is the point of the floor measurement and also its limit. A signal built to need two penalties — curvature in one region and a jump in another — would reward mixing in a way these five do not, and it is the case that would test whether “one penalty does the work” is a law or a property of signals with one kind of structure.

Still open: a signal made of two structures, and choosing the penalty by rule #

A signal with a jump and a curve. A smooth bump joined to a step asks for the second difference in one half and something tolerant of jumps in the other. The prediction with a sign is that on such a signal the best pair beats the best single penalty by more than the ten per cent no signal here reached, and the third penalty still buys nothing — which would locate the value of mixing in the signal’s heterogeneity rather than in the number of penalties.

A rule for the choice. The decision worth a factor of two is which penalty, and no rule here made it; the oracle did. Whether the discrepancy principle applied to each single penalty in turn, with the penalty whose discrepancy stop has the smaller residual chosen, recovers the right one on the smooth and oscillating signals is one sweep over the same draws.

A floor measured instead of an argmin. Every rule in the field reports a point. A rule that reported the set of parameters within a per cent of its own criterion’s minimum, and whose output was judged by whether that set contains the oracle, would ask of a rule only what the floor makes possible.