The floor is the part the noise buried

A third penalty on a flat floor penalised a deconvolution’s answer in three ways at once — its size $\|x\|$, its slope $\|L_1x\|$ and its curvature $\|L_2x\|$ — and tuned all three parameters over a cube of fourteen values each. On five signals the third penalty bought a median of exactly nothing, and the minimum of the cube sat on a floor so flat that hundreds of cells were within a per cent of it. Choosing the right single penalty was worth a factor of two; mixing them was worth nothing.

It left a prediction about where mixing might pay after all. “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.”

The prediction fails, and nearly completely. What replaces it is an account of the floor itself: how high it is, what sets that height, and the single kind of penalty measured here that gets under it.

An arch joined to a staircase #

The signal is built to be as heterogeneous as the prediction wanted. On the first part of the interval it is a smooth arch, half a sine wave of height 1.2; on the rest it is a staircase of three levels, 0.4, 1.3 and 0.7, with jumps of 0.9 and 0.6 between them and a jump of 0.4 where the arch meets the first stair. The join sits at a quarter, a half or three quarters of the interval. Everything else is the cube’s: the same 64-point Gaussian blur, noise at $10^{-3}$ of the data’s norm, eight seeded draws per join, and the best of all $14^3 - 1$ combinations of the three parameters — zero and thirteen values from $10^{-6}$ to one for each.

The first two rows of each block are the prediction’s test, and both sit on the dashed line at one. The best pair beats the best single penalty by a median of 0.12%, 0.07% and 0.06% at the three joins, and by 0.76% on its best draw of twenty-four. The third penalty buys a median of nothing at every join and 0.23% at most. The signal with two structures behaves exactly like the five signals with one. Worse for the prediction, the choice of single penalty barely matters either: on the first draw with the join at a half, the norm, the first difference and the second difference reach 0.0785, 0.0786 and 0.0787. The decision the earlier essay found worth a factor of two on the smooth and oscillating signals is worth a tenth of a per cent here.

The third row of each block is a different penalty, and it comes later.

The prediction was not unreasonable. A second penalty is not a second parameter had found that the best pair sat on an edge of its square on most draws — one parameter zero — and the natural reading was that each of the five signals had one structure and one penalty suited it. A signal with two structures would then need two, and the pair’s advantage would appear exactly where the single penalty was wrong for half the interval. What that reading left out is that the penalties being mixed are all the same kind of object, and the mixture is one more of them.

A mixture of penalties is a penalty #

The three penalties enter the problem only through the matrix of the regularised normal equations, $\Sigma^2 + \lambda_0^2 I + \lambda_1^2 G_1 + \lambda_2^2 G_2$, where $G_k$ is the Gram matrix of the $k$-th difference operator in the blur’s coordinates. Any choice of the three parameters gives one symmetric positive semidefinite matrix $P = \lambda_0^2 I + \lambda_1^2 G_1 + \lambda_2^2 G_2$, and the regularised answer is the same as if a single penalty $\|Mx\|^2$ with $M^{\mathsf T}M = P$ had been used. So the cube of three parameters is not three ways of looking at the answer; it is a three-dimensional family of single quadratic penalties, each of them the same at every point of the interval, each of them a fixed linear rule for turning the data into an answer.

What such a rule can do with a buried coefficient is limited. The data there are noise, so a linear rule that took them seriously would amplify the noise; a good rule nearly ignores them and fills the coefficient from its neighbours through $P$’s off-diagonal coupling — which is the penalty’s guess about how the answer continues past what was measured. For a smooth answer that guess is good, because a smooth answer’s high coefficients really are determined by its low ones. For an answer with a jump it is poor, because the jump’s high coefficients encode where the jump is and how tall, and a penalty that treats every point alike has no way of knowing either. Mixing more such penalties moves the guess around inside the same family. It cannot make the guess depend on where the jump is.

What the data cannot say #

The reason the choice of penalty stops mattering has nothing to do with penalties. Write the blur through its singular value decomposition, $A = U\Sigma V^{\mathsf T}$. The data’s $k$-th coefficient is $u_k^{\mathsf T}b = \sigma_k\, v_k^{\mathsf T}x + u_k^{\mathsf T}e$: the answer’s $k$-th coefficient shrunk by the $k$-th singular value, plus that coefficient of the noise. The noise contributes about $\delta/\sqrt{n}$ to every coefficient, where $\delta$ is its norm; the answer’s contribution falls with $\sigma_k$, which for a Gaussian blur falls faster than any power.

On the joined signal’s first draw the noise level is $8.3 \times 10^{-4}$ per coefficient. Twenty-six of the sixty-four exact coefficients stand above it; the other thirty-eight are buried, and the measured values there are pure noise — the dots scatter around the dashed line whatever the answer is. No method that sees only the data can recover those thirty-eight coefficients from them. What a regularised solution puts there comes from its penalty: a guess about what a plausible answer does in directions the data are silent on.

The share of the answer that lives in buried coefficients is a number computable from the answer and the noise level alone:

$$\beta = \frac{\big\|\,(v_k^{\mathsf T}x)_{k:\ \sigma_k |v_k^{\mathsf T}x| < \delta/\sqrt n}\,\big\|}{\|x\|}.$$

For the joined signal it is 7.8%. For the step signal of the earlier essays it is 10.3%; for four isolated spikes, 57%; for the smooth signal, 0.21%. It is not a bound from a theorem — a penalty that guesses the buried coefficients well can beat it, and a later section shows one that does — but it is what the Picard condition looks like when it is counted rather than plotted: the coefficients past the point where the data’s decay meets the noise are the ones the problem has given up.

The floor has this height #

The figure at the top of the page is the comparison, and the dots lie on the diagonal. On the step signal the best of the whole cube is between 1.002 and 1.079 times the buried share; on the offset step, 0.958 to 1.089; on the spikes, 0.974 to 1.042; on the joined signal, 0.986 to 1.027. Across four signals with nothing in common but a discontinuity, the floor the earlier essay found flat is the buried share to within nine per cent, on every one of thirty-two draws.

The smooth and oscillating signals sit above the line, the best error between 0.96 and 1.57 times the buried share. On them the buried part is small — 0.21% and 1.0% — and the error that remains is dominated by how well the kept coefficients are filtered, which is where the choice of penalty does its work. That is why the choice was worth a factor of two there and is worth nothing on a signal with a jump: a jump puts a tenth of its norm in coefficients the noise has buried, every quadratic penalty guesses them as roughly zero, and the error is that tenth whichever penalty did the guessing.

The account also explains four knobs and one floor, which found a truncation, a Tikhonov parameter, a step count and a randomised rank reaching best errors within 3% of each other on the step signal at one per cent noise — 0.1406 to 0.1449. The buried share of that very draw — the same signal, seed and noise — is 0.137. Four methods that share no arithmetic were not converging on each other; they were each reaching the part of the answer the data still held, and stopping where the data stopped.

Under the floor, once #

A quadratic penalty treats every point of the interval alike, and that is what the third row of the strip figure tests against. The split pair penalises the second difference on the rows left of the join and the first difference on the rows right of it, each with its own parameter, and it is told exactly where the join is — information no method has without being given it.

With the join at a quarter or a half it gains nothing: 0.979 to 1.010 times the uniform pair’s error, on all sixteen draws. With the join at three quarters it gains between 10% and 31% on every draw, and reaches errors of 0.059 to 0.073 against a buried share of 0.081 — under the floor on all eight. The dial shows why. On the long arch the split pair puts a strength of 0.03 to 1 on the second difference, ten to three hundred times what it puts on the staircase’s first difference; the uniform pair cannot do that, because the same strength applied to the steps would smear them, so it settles at $10^{-2}$ on the norm and $3 \times 10^{-3}$ on the curvature and lets the arch wobble. The long arch has low curvature everywhere — a ninth of the short arch’s — so a heavy curvature penalty costs it almost nothing and fills its buried coefficients with what a smooth curve would put there, which is nearly right.

The short arch has nine times the curvature, a heavy penalty on it would flatten it, and the split pair chooses the same modest strength on both sides as the uniform one does. What decides whether the split pays is not that the signal has two structures; it is whether one of them is smooth enough to accept a strength the other cannot.

The floor against the noise #

If the floor is the buried share, it should move with the noise the way the buried share does, and it does. On the step signal the buried share falls from 0.137 at one per cent noise to 0.092 at $10^{-5}$, and the best single penalty’s error falls from 0.138 to 0.093 beside it. The fall is slow — a thousandfold reduction in noise buys a third off the error — because a jump’s coefficients decay slowly while the blur’s singular values fall like a Gaussian, so each decade of noise uncovers only a couple of coefficients. On the spikes, whose coefficients do not decay at all, the floor falls from 0.63 to 0.46. On the smooth signal, whose coefficients decay as fast as the blur’s, the buried share falls by a factor of twenty-seven and the error by forty-two.

On every signal with a jump or a spike, at every noise level, the best single penalty’s median error is between 0.97 and 1.10 times the median buried share. Thirty-two coefficients instead of a noise level estimated the noise from the data’s last coefficients, which are the buried ones; the same coefficients, read against the answer rather than the data, say how good any answer can be.

What the rules were being asked to find #

Every rule this field has scored — the discrepancy principle, generalised cross-validation and the L-curve, the corner read in different norms, the share target, two penalties and three — chose a point on this floor. The parameter-choice question has two parts that the measurements so far have run together. Which coefficients to keep is decided by the noise, and every good rule gets it right to within a grid step; what to put in the coefficients that cannot be kept is decided by the penalty, and on a signal with jumps every uniform quadratic penalty puts roughly nothing there.

A rule that has to be told how good its answer will be found that the best parameter sits where the amplified noise is a third to four-fifths of the relative error that parameter achieves, and needed that error in advance. On a signal with a jump the buried share is that error to within a few per cent, and the buried share needs the answer’s coefficients, which are unknown — but their decay rate, for a signal known to have jumps, is not. That is the nearest any parameter rule here has come to a rule that knows its own target.

It also says why some failures in this field were cheap and others were not. One draw in twenty found generalised cross-validation choosing a catastrophically small parameter on four to six draws in a hundred: a parameter that small stops ignoring the buried coefficients and amplifies them, which takes the error off the floor entirely. A rule that errs the other way, choosing a parameter too large, discards a few coefficients that were above the noise and costs a few per cent, which is what every rule’s typical draw cost. And a parameter chosen on a smaller problem found the residual-reading rule transferring exactly from a projected problem to the full one: the projection keeps the coefficients above the noise, and the rule is a statement about where they end.

What sixty-four points and one blur do not show #

Every measurement here is on one Gaussian blur of width 2.5 at 64 points, whose singular values fall fast enough that the boundary between kept and buried coefficients is sharp; on a milder operator the boundary would be gradual and the buried share a cruder summary. The noise level per coefficient is taken as $\delta/\sqrt n$, the average for white noise; a single draw’s noise coefficients scatter about it by their own factor. The split pair was given the join’s position exactly, and nothing here measures what it costs to estimate it. And the penalties are all quadratic: a total-variation penalty, which is not, guesses buried coefficients for a step very differently, and nothing here says whether it beats the floor.

Still open: total variation, and a join that must be found #

A penalty that is not quadratic. Total variation penalises $\|L_1x\|_1$ rather than its square, and on a piecewise-constant signal it puts the buried coefficients of a jump close to where the jump’s own decay would put them. The prediction with a sign is that on the step signal total variation’s best error falls below the buried share by more than the split pair’s best margin here — more than a third — while on the smooth signal it does worse than the second difference, so that the choice between a quadratic and a non-quadratic penalty, not the number of penalties, is the next decision worth a factor.

Finding the join. The split pair paid only when told where the join was. A rule that tries every join position on the 64-point grid and keeps the one with the smallest generalised cross-validation value would cost sixty-four solves; the prediction is that it finds the join to within two grid points on all eight draws at three quarters and keeps at least two thirds of the split pair’s gain, and that at a quarter and a half, where splitting buys nothing, it chooses a position that costs less than a per cent.