A better discretisation is a weaker filter

The grid was the first filter solved a continuous deconvolution on grids of 12 to 48 points with no regularisation at all and found that the grid regularised it: the best grid sat beside the best truncation of a 64-point operator at three noise levels, within 4, 11 and 16 per cent of its error. It named the gap and could not account for it. Left of the optimum, where noise does not reach the answer, the error had two sources the experiment did not separate. One is the operator: the row-normalised sampled kernel is a quadrature rule for an integral, and on a coarse grid a poor one. The other is the representation: a piecewise-linear function through n values cannot follow a step or the top of a narrow bump.

Both sources can be removed one at a time, on the same unknowns and the same data, and that is what this essay does. The expectation they invite is simple. A discretisation that approximates the integral more faithfully and represents the answer more faithfully should give a better answer, and should close the gap to the truncation that the grid essay left open.

It closes the gap where the noise is small enough to afford it, to 0.3 per cent at 0.1% noise per sample. At 1% it does the opposite, and the reason is the same fact seen from the other side. A more faithful discretisation is a sharper filter and a worse-conditioned matrix, because what it represents more faithfully is exactly the part of the answer that a noisy measurement cannot pay for.

Three ways to write down the same blur on n points #

The problem is the grid essay’s. A Gaussian blur of fixed width in the continuous variable acts on a signal of two bumps and a step on [0, 1]; the data at each grid point are the blur of the continuous signal computed on two thousand quadrature points; the noise per sample is a fixed fraction of the data’s root mean square, drawn from the same seeds on every grid; and every answer is scored against the continuous signal rather than against its own samples.

The unknowns in all three discretisations are the same n numbers, the values at the grid points. What differs is what function those numbers are taken to describe and how the blur of that function is computed.

Sampled. The grid essay’s operator: the kernel sampled at the grid points, each row divided by its sum, with the answer read as the piecewise-linear function through the values. It is what anybody would write down first, and on a coarse grid its rows are nearly spikes, because at 12 points the grid spacing is wider than the blur.

Integrated. The answer is still read as the piecewise-linear function, but the operator is computed honestly for that reading: the (i, j) entry is the blur at grid point i of the j-th hat function, integrated on the two thousand quadrature points and normalised by the kernel’s integral. For any answer that is piecewise linear on the grid, this operator reproduces the data the instrument would have measured, to quadrature accuracy.

Spline. The same integral against each cardinal cubic spline — the natural cubic spline through a one at node j and zeros elsewhere — with the answer read as the spline through the values. The operator is exact for every cubic spline on the grid, and a cubic spline follows a smooth bump far better than a broken line does.

The second and third are what a numerical analyst would call consistent discretisations: the discrete equations are satisfied exactly by the discrete version of any function the reading can represent. The first is not, and the grid essay’s coarse-side error was partly that inconsistency. A different equation on every grid is the general warning about comparing solutions of discretised equations that are not the same problem at every n; here the three discretisations are three different problems at the same n, and the comparison is the point.

Separating the operator from the representation #

With no noise, the three errors isolate the two sources the grid essay could not.

At 12 points the sampled kernel’s noise-free error is 0.2664. Integrating the kernel against the same hat functions brings it to 0.2139, a fifth less, with the representation unchanged, so a fifth of the coarsest grid’s error was the operator. Reading the answer as a spline brings it to 0.1809, a further 15 per cent, with the operator now exact for what is read, so that much was the representation. At 26 points the same three numbers are 0.1299, 0.1183 and 0.1149: the operator’s share has fallen to 9 per cent and the representation’s to 3, because a finer grid is both a better quadrature and a better interpolant. At 40 points they are 0.0997, 0.0889 and 0.0910, and the spline has stopped being the more accurate reading of the two integrated ones.

The integrated hat functions are not uniformly better than the sampled kernel. At 30 and 32 points they are slightly worse — 0.1345 against 0.1341, and 0.1374 against 0.1345 — which is the grid essay’s observation about where the step’s corner falls between samples, now arriving in a second discretisation at a different place. The spline discretisation is better than the sampled one on every grid from 12 to 40 points, by between 8 and 32 per cent, and that is the comparison the rest of this essay uses.

So the coarse side of the grid essay’s curve had a composition after all, and it was mostly operator at the coarsest grids and mostly representation, in what little of it survives, by 26 points. Neither part was noise.

A sharper filter on the same nodes #

The grid essay measured what a grid does as filter factors — for each singular vector of the 64-point operator, the fraction of it a function on n nodes can represent — and found them summing to n exactly, softer than a truncation below n and leaking back above it. The same measurement with the answer read as a spline shows what the better representation changes.

Both readings keep exactly 24 components in total, because both are projections onto 24-dimensional spaces and a projection’s trace is its rank. They distribute them differently. Just below the grid’s size the spline keeps 0.935, 0.894, 0.833 and 0.785 of indices 20 to 23, where hat functions keep 0.805, 0.758, 0.713 and 0.709. Summed over every index below 20, the spline gives up 0.11 of a component and the hat functions 0.58. Above the grid’s size the spline folds back less: index 25 keeps 0.26 of itself against 0.33, and everything past index 25 adds up to 0.62 of a component against 1.56.

In the vocabulary the regularisation field uses for every filter, the spline reading is closer to a truncation at K = 24 on both sides of the cut. It keeps what a truncation keeps more nearly whole, and it lets through less of what a truncation drops. A sharper filter on the same number of unknowns is exactly what a better representation ought to be, and it is also, as the next two figures show, the thing that decides what the noise does.

What the sharper filter costs in conditioning #

A discretisation that keeps more of the smooth singular vectors whole keeps more of the small singular values they carry, and the condition number records that directly.

On every grid from 12 to 40 points both integrated operators are between 1.95 and 2.49 times worse conditioned than the sampled kernel. At 26 points the sampled kernel’s condition number is 60.6, the integrated hat functions’ 149 and the spline’s 124; at 40 points 5.6·10⁴, 1.4·10⁵ and 1.1·10⁵. The ordering never changes, and the ratio does not shrink as the grid is refined.

The sampled kernel’s better conditioning is not a virtue it earned. On a coarse grid each of its rows is nearly a spike — the renormalisation piles most of a row’s weight onto its own point because the kernel is narrower than the spacing — so the matrix is close to the identity and nearly as easy to invert. It is well conditioned because it is a poor quadrature of a blur, and a poor quadrature of a blur does not blur as much as the blur does. The integrated operators blur as much as the instrument did, and their smallest singular values are correspondingly small. That reading fits the ratios and the coarse-grid rows; the condition number is a statement about the extremes of a spectrum, and the condition number as an amplifier is the reminder that the noise does not arrange itself along the worst direction.

At a tenth of a per cent the gap to the truncation closes #

The hero figure is the payoff where the noise is small enough for accuracy to be worth having.

At 0.1% noise per sample the three discretisations share a best grid, 26 points, and reach 0.1300, 0.1205 and 0.1170. The best truncation of a 64-point sampled operator, which the grid essay put at 0.1167, is now 0.3 per cent away from an unregularised solve on 26 points. The grid essay’s gap at this noise level was 11 per cent, and it is gone.

The drawn answer shows why nothing is left to gain at this noise level from choosing a filter. The noise adds a thousandth to the error: 0.116 against 0.115 for the same grid with noise-free data. The rest is the spline’s inability to make a corner — it rounds the step and rings slightly beside it, which a truncation of smooth singular vectors does too — and at 26 points that inability costs the same amount for the spline as for the best truncation of a much finer grid. A second blur, narrower than the first would describe the two answers as the same truth seen through two averaging kernels of about the same width, and the numbers say the widths are about the same.

At one per cent the crude grid wins #

At ten times the noise the ordering of the three discretisations reverses.

The sampled kernel’s best grid is 24 points, at 0.1472. The spline discretisation’s best grid is 20 points, at 0.1527, and the integrated hat functions’ is 20 points at 0.1580. The discretisation that is more accurate on every grid with no noise, and closer to the truncation at 0.1%, is 4 per cent worse than the crude one here, and 8 per cent worse than the truncation where the crude grid is 4.

The mechanism is in the two preceding figures together. At 1% noise the right number of components is about 24, and the components near index 24 are the ones in which a noisy measurement is marginal. The sampled grid on 24 points keeps them at about 0.7 of themselves — a softer filter, which damps the marginal components the noise was about to corrupt — and its matrix is conditioned at 29. The spline on 24 points keeps the same components at 0.8 to 0.9 and has a condition number of 60, so the noise in those components reaches the answer almost undamped. On this problem its error at 24 points is 0.1630 against the sampled grid’s 0.1472. It has to retreat to 20 points to keep the noise out, and on 20 points the step is spread over two spacings of a twentieth of the interval: 0.147 of error with no noise at all.

So the soft filter the grid essay found in hat functions — the part of a grid’s behaviour that made it lose to the truncation at low noise — is what made it win at high noise. The better discretisation removed the softness and, with it, the protection.

At a hundredth of a per cent the better discretisation needs fewer points #

The third noise level shows the other half of the trade in the grid sizes rather than the errors.

At 0.01% noise the sampled kernel’s best grid moves to 34 points, at 0.1288, 16 per cent above the truncation’s 0.1114. The spline’s best grid stays at 26 points, at 0.1149, 3 per cent above it. The better discretisation reaches a better answer on a coarser grid, for the same reason it lost at 1%: its condition number grows faster with n, so the grid at which noise starts to cost comes sooner, and its representation is good enough that it does not need the extra points the crude grid needs to follow the step.

Across the three noise levels the spline discretisation’s gap to the truncation is 8, 0.3 and 3 per cent, against the sampled grid’s 4, 11 and 16. The crude discretisation’s gap grows steadily as the noise falls, because the noise stops being the limit and its crude representation becomes one. The better discretisation’s gap has a minimum, at the noise level where its sharper filter’s cut falls where the truncation’s does.

What improving a discretisation does to an ill-posed problem #

A discretisation is chosen for accuracy, and on a well-posed problem accuracy is all it needs to be judged on: a better quadrature and a better interpolant give a better answer, and the condition number of a well-posed problem converges as the grid is refined. On an ill-posed problem the same choice is also a filter, and improving the discretisation sharpens the filter and worsens the conditioning together.

Improving a discretisation is a regularisation decision. The spline discretisation keeps more of each component below the grid’s size and less above it, and that is a change of filter factors as surely as a change of λ is. Whether it helps depends on whether the noise can pay for the components it now keeps, which is the question where the answer stops being in the data answers for singular components and a Picard plot.

The crude grid’s softness was protective. A soft filter damps the marginal components whatever they contain; a sharp one keeps them whole. At 1% noise the marginal components were noise, and the softness was worth four per cent of error.

That is the same trade every explicit regulariser here has shown, arriving through a door nobody labelled as regularisation. Four knobs and one floor found a truncation, a Tikhonov penalty, a step count and a randomised rank reaching one floor because each is a different shape of the same filter; a parameter that counts steps found the general-form penalty preferring smooth answers by charging for derivatives. A discretisation belongs in that list with a shape of its own. The hat-function grid is a soft, slightly leaky truncation; the spline grid is a sharper, less leaky one; and which is better is decided by the noise level exactly as the choice between a truncation and a penalty is, because at a fixed number of kept components a sharp filter wins when the marginal components are signal and a soft one when they are noise. What distinguishes the discretisation from the other knobs is only that it is chosen first, for reasons of accuracy, and that a person choosing it seldom knows it is a filter at all.

The two ways of improving the answer are not independent. A better discretisation does not reduce discretisation error and leave the regularisation alone. It moves the best grid, coarser at low noise and finer than it can afford at high noise, and it moves the point at which a λ starts to matter — which is what where the grid hands over to λ measures for the sampled kernel, and has not been measured for this one.

What was not measured #

Only unregularised solves were compared. The spline discretisation with its own best λ on every grid is the obvious combination and it is not drawn: if the fine-grid-with-λ result holds for it, the better discretisation’s advantage at low noise and its disadvantage at high noise might both disappear into a λ, leaving only a difference in cost.

The step in the signal is the feature a cubic spline represents worst, because a spline through samples of a jump overshoots on both sides of it, and the comparison would probably favour the spline by more on a smooth signal and by less on a signal with several jumps. Only one signal was used. The readings are hat functions and cubic splines; a basis adapted to the kernel, or a higher-order element, is the continuation the grid essay proposed and remains unmeasured. And the noise is independent per sample on every grid, which, as the grid essay pointed out, is not the same physical noise at every n.

Still open: does λ undo the difference between discretisations, and what would a basis adapted to the step do? #

The better discretisation with its own λ. The grid-and-λ measurement found the best λ on fine sampled grids to be one number and the fine grid with that λ to be the best answer available. The same sweep on the spline discretisation would say whether a λ recovers the 4 per cent the spline lost at 1% noise, and whether, with a λ, the two discretisations converge to the same answer on fine grids — in which case the choice between them is a choice of cost rather than of accuracy.

A reading that can make a corner. Both readings here are continuous functions and neither can represent the step. A reading with a breakpoint placed at the step, or a basis of smooth functions and one jump, would change the representation’s share of the error without changing the operator’s; the measurement is whether the gap to the truncation then closes at 1% noise as well, where the smooth readings could not afford the components the step needs.

Correlated noise under refinement. Noise with a fixed correlation length in the continuous variable becomes more correlated per sample as the grid is refined. Noise that spares the answer and fools the rules found slow noise to be cheap at a fixed grid, and a sharper filter may be worth more when the noise it lets through is slow.