A corner the penalty can afford

The grid on which the discretisation stops mattering ended with a number it could not take apart. The deconvolution these essays keep returning to — a Gaussian blur of a signal with a narrow bump, a step on 0.45 to 0.58, and a wide bump, measured on a grid and inverted with Tikhonov regularisation — needed about forty grid points before it stopped improving at 0.01% noise, whichever of three discretisations it was given and whatever λ each chose. On ninety-six points all three agreed to a fifth of a per cent, at an error of 0.111. The step was named as the likely reason, because no continuous function on a grid can make a corner, and the proposal was to test it with a reading that could: a spline with a knot at the step, or hat functions plus a jump.

That test has been run, four ways, and the four do not agree with each other. Which of them works, and why the one that represents the step best is the worst of them, is the finding.

Four readings of the same unknowns #

A grid of n points hands the solver n unknowns, and a reading is how those n numbers are turned into a function. The reading the earlier measurements used is the natural one: hat functions, so the unknowns are the function’s values at the grid points and it is linear in between, with the blur integrated against each hat on a fine quadrature. Three readings with a breakpoint spend the same n unknowns differently.

The first keeps n − 2 hat functions and adds two jump functions, one at each edge of the step, each 0 to the left of its edge and 1 to the right, running to the end of the interval. The second keeps the piecewise-linear reading but doubles the node at each edge — a left value and a right value — so that the function may jump there and nowhere else, which is the spline-with-a-knot construction in its linear form. The third keeps n − 1 hat functions and adds one box, equal to 1 on the step and 0 off it.

All four are given their own best λ on every grid, from the same sixteen seeded draws the earlier grid measurements used, and are scored against the continuous signal on the same two thousand fine points.

At 0.1% noise, on 96 points, the four reach 0.1178 with no breakpoint, 0.0502 with two jumps, 0.1295 with doubled knots and 0.0132 with one box. The box is at 0.0070 on 48 points. It beats the smooth reading’s 96-point answer from 16 points on, where it is 0.0504.

Turn the dial and the order holds at every noise level: box, then jumps, then no breakpoint, then doubled knots. At 1% noise the box on 48 points is 0.0207 against the smooth reading’s 0.1376 on 96; at 0.01% it is 0.0050 against 0.1113. And the box beats that 96-point smooth answer with 16 points at both of those levels too.

So the first question has an answer, and the answer is nearly all of it. On the finest grid measured, with its best λ, the smooth reading’s error is between seven and twenty-two times what the same budget of unknowns reaches when one of them is spent on the step. The bumps are not what needed forty points. The step was.

Representation is not recovery #

The obvious explanation is representation: a reading that can make a corner holds the signal better, and a better approximation space gives a better answer. It can be measured on its own, by fitting each reading directly to the true signal on the fine points — no blur, no noise, no λ — and seeing how close it can get. The method that cannot use a smooth answer found the other half of the same relation from the answer’s side: how well a regulariser does depends on how smooth the answer is in the operator’s own basis, and a step is about as unsmooth as a signal gets.

With no breakpoint, the fit on 96 points cannot get below 0.0691 of the signal’s size: that is the cost of drawing a vertical edge with straight segments a grid spacing wide, and it barely falls with the grid, because a finer grid makes the ramp narrower and not vertical. The other three readings all make the corner exactly, and their floors fall steadily — to 0.0114, 0.0126 and 0.0155 on 26 points for the box, the jumps and the knots, and to 0.0007 for all three on 96. By representation alone the three breakpoint readings are indistinguishable, and all three are a hundred times better than the smooth reading on the finest grid.

Set that beside the recovered errors. The box, at 0.0132 on 96 points, is eighteen times its floor. The jumps, at 0.0502, are seventy times theirs. The knots, at 0.1295, are a hundred and eighty times theirs, and above the smooth reading, whose own floor is a hundred times worse. The reading that represents the signal to 0.07% is recovered worse than the reading that cannot represent it to better than 7%.

A better discretisation is a weaker filter found the first version of this effect with no breakpoints involved: a spline reading represents the answer better than a hat reading and makes the operator worse conditioned, so without regularisation it was better at one noise level and worse at another. Here the same trade is not close. Two readings with identical floors differ by a factor of ten in what the regularised solve returns, and something other than representation is deciding.

Two draws, four answers #

What the difference looks like on the signal itself is worth a picture before it is explained.

The answer with no breakpoint follows both bumps and misses the step the way a smooth function must: it ramps up across the left edge, overshoots to 1.3 inside the step, and swings down to 0.35 after the right edge, with oscillations through the flat part on either side. Its error on this draw is 0.1194. The answer with the box lies on the signal almost everywhere; the step comes back with vertical edges, the box’s coefficient at 1.003, and the error is 0.0080.

The two-jump answer makes the left edge as a jump, its coefficient at 0.936, and the right one only in part: the jump there comes back at −0.377, and the rest of the fall is made as a ramp across the next grid interval, which is a shape the blur can barely tell from a jump. Its error is 0.0584. The doubled-knot answer opens both corners and opens them badly — it reaches 1.5 just before the right edge and drops to 0.13 just after it, with a spike of the same kind at the left — and away from the step it is the smooth answer. Its error is 0.1209, a little above the smooth reading’s.

What the penalty is charged for a corner #

Tikhonov regularisation minimises the misfit plus $\lambda^2$ times the squared norm of the unknowns. It does not know what the unknowns mean. A coefficient that buys a whole step and a coefficient that buys a sliver of one are charged the same, and the blurred operator sees them very differently. Those two facts together rank the readings, and both can be measured.

The box’s single coefficient buys a function of size 0.36 in the L2 sense — the whole step — at a penalty cost of one. The blurred operator passes that function almost entirely: the gain of the box column is 0.85 to 0.95 of the operator’s largest singular value on 26 to 96 points, so the box direction is, on every grid, one of the directions the data see most clearly. The regulariser’s job is to suppress directions the data cannot see, and it has no reason to suppress this one. When the answer is a choice put the field’s whole premise in those terms: the data determine the answer in the directions the operator passes and something outside the data has to choose the rest. The box moves the step out of the second group and into the first.

A doubled knot’s corner is a different object. Opening the knot — moving the left value down and the right value up — changes the function only in the two half-intervals beside the edge, so a coefficient change of norm 1.41 buys a sliver of size 0.06 to 0.13. The operator passes that sliver at 0.035 to 0.089 of its largest singular value, eighteenth to twentieth among the directions it can see. The corner is therefore expensive in the penalty’s units and nearly invisible in the data’s, which is precisely the kind of direction Tikhonov exists to damp — and at the λ that serves the rest of the signal it is damped too little to stay shut and seen too poorly to open to the right height. What opens at each knot is as much noise as step, which is the pair of spikes in the picture, and it is why the knots come in below the smooth reading rather than equal to it.

The two jumps sit between, and for a reason specific to how they were built. Each jump function runs from its edge to the end of the interval, so the pair represents the step as a rise of 1 at 0.45 and a fall of 1 at 0.58 — and the fall is a constant offset over the whole right-hand part of the signal, which the hat functions there can equally represent. The penalty prefers to share an offset between one jump coefficient and many small nodal changes rather than put all of it on the jump. On 96 points at 1% noise the rising edge comes back at a coefficient of 1.03 and the falling one at −0.47. The box has no tail to share and comes back at 1.000 on 48 points at every noise level.

So what a breakpoint needs, in a penalised solve, is not only to be representable but to be cheap: one coefficient, not several, for the whole feature, and a direction the operator passes strongly. This is the same lesson the grid was the first filter drew about grids — that a discretisation is a choice of filter before any λ is chosen — with a sharper edge. The basis is a choice of what the penalty charges for, and a basis that makes the answer cheap to say is a basis that the penalty lets through.

The box has to be in the right place #

Everything so far placed the breakpoints at the step’s true edges, which is knowledge the data were never given. How exact that knowledge has to be is the next measurement, and the answer is uncomfortable.

Move the box’s edges by 0.005 of the interval — a quarter of the 48-point grid’s spacing, an eighth of the blur’s width — and at 0.1% noise the error goes from 0.0070 to 0.1288. At 1% it goes from 0.0207 to 0.1335, and at 0.01% from 0.0050 to 0.1268. With no box at all on the same grid the errors are 0.1427, 0.1192 and 0.1128. A box 0.005 off keeps almost none of its advantage at 1% noise and is worse than no box at the two lower levels.

The dashed curve says most of that is not the regularisation’s fault. A box misplaced by 0.005 cannot represent the signal to better than 0.085, even fitted directly to it: two slivers, each 0.005 wide and 1 high, are wrong by the full height of the step, and in an L2 measure a misplaced edge costs roughly the square root of the width it is misplaced by. The smooth reading spreads the edge over a grid spacing and pays for it gradually; a box concentrates the bet, wins everything when it is right and pays in full when it is not. At a shift of 0.0025, an eighth of a grid spacing, the error is already 0.0945.

Can the data say where the step is? #

A code that wants the box’s gain needs the step’s position from somewhere, and the obvious place is the data. Scan the box across candidate positions, fit each, and keep the position whose fit has the smallest residual. The residual is a quantity a solver can compute; the measurement is whether it points at the step. It is also a different use of the residual from the one the parameter-choice essays score: there the residual is compared with the noise to choose λ, and here it is compared across models at one λ to choose the model.

It does, on two conditions. At 0.1% noise on 48 points the scan, fitting at λ = 10^−1.5, puts the box exactly on the step on fifteen of sixteen draws and a quarter-step of the scan off on the sixteenth, and the median error with the box where it was put is 0.0070 — the hand-placed box’s, to four figures. At 0.01% it is on the step on all sixteen, at an error of 0.0050. The residual’s minimum on the figure is sharp: the fit at the right position is about 1.2 times the noise, and 0.02 either side it is two to three times it.

The first condition is the noise. At 1% on the same grid the scan is on the step on two draws of sixteen and up to 0.0175 off on the others, and the median error with the box where it was put is 0.1346 — within six per cent of having no box. The data at 1% cannot tell the step’s edge to a quarter of a grid spacing, and a quarter of a grid spacing is what the box needs.

The second condition is the λ at which the scan fits, and it is the kind of detail that decides whether the method works at all. Run the same scan at λ = 10⁻⁴ and every shifted box can fit the data to a thousandth of the noise: the scan is comparing overfits, the residual’s minimum is set by which misfit elsewhere is easiest to absorb, and at 0.01% noise it puts the box on the step on two draws of sixteen, with an error of 0.1508 — worse than no box. A scan at a λ that regularises nothing measures the model’s flexibility rather than the data, and read naively it would say the data do not contain the step’s position. They do; the scan was not asking them.

What the forty points were #

The question inherited from the grid essays was how much of the forty points the step needed and how much the bumps did. With the step given one coefficient of its own the bumps are represented to 1.1% on 26 points and recovered to 0.012 at 0.01% noise on 26 points — so the bumps need twenty-odd points, and the rest of the forty was the step’s, spent approximating a corner with ramps.

That is an answer about this signal, and it carries a warning about signals in general that the grid essays could not have given. A regularised inverse problem whose answer has a few sharp features will look, measured by grid refinement, as though it needs a fine grid, and will converge to an error that is mostly those features. The error does not indicate that the grid is too coarse. It indicates that the reading is wrong for the answer, and the repair is a basis the penalty can afford — one cheap, strongly observed coefficient per feature — placed where the feature is, which the data can supply when the noise is low enough and the search is done at a λ that regularises.

What this does not settle #

One signal with one step, one blur, and three noise levels. The box works as well as it does because the step here is exactly a box added to a smooth signal — vertical at both ends, of one height throughout — and the reading was built for it. A step with a ramp, or a feature whose shape is not known, would need a basis whose shape can vary, and every extra shape parameter is an extra cost to the penalty and an extra dimension to the search.

The penalty is the plain norm of the unknowns throughout. A penalty that charged the box’s coefficient differently from the nodal values — less, because the data see it well — would change every ranking above, and weighting the penalty is a second parameter of exactly the kind where the grid hands over to λ found the grid and λ do not trade against.

The locator scans the box’s position with its width fixed at the true width, on a quarter-step grid of positions, and the true position is on that grid. A step whose edges fall between scan points, or whose width is also unknown, is a two-parameter search with a floor set by the scan’s own spacing, and the misplacement measurement says that floor has to be below an eighth of a grid spacing before the box pays.

Still open: a rule for the grid as well as λ, and a penalty that knows which coefficient is cheap #

The grid from the data. The grid essays and this one all chose the grid with the answer in hand. Where the answer stops being in the data asked what the data alone can say about λ. Whether any data-driven rule can see the difference between a 26-point and a 40-point smooth grid at 0.1% noise — which the grid essay measured as a 1.8 per cent difference in the error — is the same question asked of the grid, and the answer decides whether the grid is a parameter a user can choose or one that has to be fixed by experience.

A penalty weighted by visibility. The box works because the operator sees it at 0.9 of its largest singular value and the penalty charges it one unit. A penalty weighted by each column’s visibility would charge the knots’ corner less and might make them work; whether that recovers the knots’ floor, or merely moves the noise into the corner, is one sweep with a diagonal weight.

The scan’s own λ as a rule. The scan works at λ = 10^−1.5 and fails at 10⁻⁴, and the box’s best λ on 48 points is 10^−1.5 at 0.1% noise. Whether the right scanning λ is simply the discrepancy principle’s — so that the whole procedure, position and λ together, is chosen from the data — is the measurement that would turn the box into a method.