The grid on which the discretisation stops mattering

A better discretisation is a weaker filter discretised one blur three ways on the same nodal unknowns: sampling the kernel and reading the answer as hat functions, integrating the kernel against the hat functions, and integrating it against cubic splines with the answer read as a spline. It solved each with no regularisation at all and found the better discretisation better only where the noise could afford it. At 0.1% noise per sample the spline discretisation’s best grid reached within 0.3% of the best truncation of a fine grid; at 1% its best grid was worse than the crude one’s, 0.1527 against 0.1472, because a sharper operator is a worse-conditioned matrix and lets more of the noise through.

It closed on a question it could not answer from unregularised solves. Where the grid hands over to λ had found, for the sampled kernel alone, that on grids fine enough to need a regulariser the best λ is one number and the fine grid with it is the best answer available. If the same holds for the other two, then with a λ the three discretisations might converge — and the choice between them would stop being about accuracy.

They do converge, and where they do not is the useful part.

At 1% noise, the lost ground comes back #

The unregularised result was that the spline discretisation lost at high noise. With a λ it does not lose anywhere past the coarsest grids. On 34 points it reaches 0.1415 against the sampled kernel’s 0.1451; on 30, 0.1471 against 0.1514; on 96, 0.1374 against 0.1375. The dashed curve shows what it was being compared with before — the spline discretisation’s own unregularised error, 0.1527 at 20 points and above 0.2 from 26 — and the solid curve shows that the whole of that disadvantage was noise a λ removes.

The sampled kernel behaves differently on the coarse grids and the difference is instructive. Up to 24 points no λ helps it at all: its best λ is the smallest the sweep tries, 10⁻⁸, and its error is its unregularised error — 0.1830, 0.1636 and 0.1472 on 16, 20 and 24 points. That is the grid essay’s finding for this discretisation: a coarse sampled grid is already its own filter, and there is nothing left for a λ to do. The integrated discretisations are better on the coarsest grids with or without a λ — 0.1611 and 0.1560 unregularised on 16 points, against the sampled 0.1830 — and that 12 to 15 per cent is representation, not regularisation. But they stop being their own filter sooner. On 24 points their unregularised errors have already risen to 0.164 and 0.163 while the sampled kernel’s is still falling, and each needs a λ of 10⁻¹·⁷⁵ to come back to 0.1466 and 0.1478.

The picture of one solution is the reason the numbers converge. With a λ of 10⁻¹·⁵ the answer is smooth whatever the discretisation — the two bumps are rounded, the step is a ramp, and the ringing an unregularised spline solve shows at this noise level is gone. At that point what distinguishes the three discretisations is how well they represent a smooth function, and on a grid of 34 points all three represent smooth functions well. A second blur, narrower than the first measured the width of that smoothing: the regularised answer is the truth seen through a kernel a few grid points wide, and a grid fine enough to resolve that kernel is fine enough for any of the three readings.

Why a faithful grid needs its λ sooner #

That the sampled kernel on 24 points wants no λ while the integrated kernels on 24 points want a large one is worth a section, because it says what the unregularised comparison was actually comparing.

The grid was the first filter explained the sampled kernel’s case: its filter factors on n points sum to n and fall through a half at the n-th component of the fine operator, so a coarse grid simply cannot hold the components the noise would be amplified in. The integrated discretisations hold the same number of components but hold them differently. Integrating the kernel against a basis function rather than sampling it at a node keeps more of each component’s weight — that is what makes the discretisation more faithful — and so the smallest singular values of the matrix are smaller: the earlier essay measured the condition number roughly doubling on every grid. A component that was cut off by the sampled grid is merely attenuated by the integrated one, and an attenuated component is one the noise can be amplified in.

So a faithful discretisation moves part of the regularisation out of the grid and into the matrix, and on any grid past the coarsest a λ has to put it back. That is the reason the unregularised comparison misled at 1% noise: it measured one discretisation that arrived pre-filtered against two that did not, and supplied no filter to the two. With the filter supplied, the comparison is between representations, and the more faithful representation is ahead, or within about one per cent, on every grid measured.

The same thing has been seen before in a different field. A different equation on every grid found upwinding to be the exact discretisation of a problem with more diffusion than the one posed, with the added diffusion set by the mesh. A sampled kernel on a coarse grid is the discrete analogue: exact for a blurrier problem than the one measured, and blurrier by an amount the grid chooses. The integrated discretisations are exact for something closer to the problem posed, and so need the extra blur supplied explicitly.

At 0.1% noise, the advantage is a grid size #

At a tenth of the noise the unregularised spline discretisation was already the best of the three on coarse grids, and a λ does not change that ordering where it held. On 26 points the spline discretisation reaches 0.1169 with a λ of 10⁻²·⁷⁵ — its unregularised error was 0.1170, so the λ is doing almost nothing — the integrated hat discretisation 0.1201, and the sampled kernel 0.1300 with no λ helping. On 96 points the three read 0.1178, 0.1178 and 0.1181.

So at this noise level the two integrated discretisations on 26 points are already at the answer the fine grids reach, and the sampled kernel is not there until 40. That is the whole of what the better discretisation buys once λ is chosen well: the same answer on a grid two thirds the size. On a one-dimensional blur of this size the saving is a few milliseconds. On a two- or three-dimensional problem, where the unknowns go as the square or cube of the points per direction, a grid two thirds as fine in each direction is a half or a third of the unknowns.

All three curves rise together at 30 points and fall again at 40, where the integrated hat discretisation reaches 0.1133, below every finer grid. The bump and the dip are properties of where the signal’s step lands relative to the nodes: a grid that puts a node on the step represents it better than the grids either side. They appear under all three discretisations at the same grids, which is how to tell a property of the grid from a property of the discretisation.

How far apart the three are, and how the gap closes #

The spread figure puts the three noise levels on one scale. With each discretisation’s own λ, the three differ by 17 to 18.5 per cent on 16 points at every noise level. At 0.1% and 0.01% they stay 8 to 13 per cent apart between 20 and 34 points; at 1% the gap has already closed to between 1 and 3 per cent by 24. At 40 and 48 points they are 0.6 to 5 per cent apart, and on 96 points 0.17, 0.28 and 0.20 per cent. The gap closes sixty- to a hundredfold from the coarsest grid to the finest at every noise level, and it closes soonest where the noise is largest, because that is where the λ is largest and the answer smoothest.

Without a λ the dashed curves do the opposite. They agree with the solid ones on the coarsest grids, where nothing is ill conditioned and λ does nothing, and then leave upward at the grid where each noise level starts to be amplified — 26 points at 1%, 34 at 0.1%, 40 at 0.01% — until on 96 points the unregularised errors differ by a factor of fifteen to seventeen. That is the three matrices’ condition numbers being different, and it is what the earlier essay was measuring when it found the spline discretisation worse at high noise: not a worse discretisation but a worse-conditioned one, compared without the tool that makes conditioning irrelevant.

One λ, whatever the discretisation #

The λ each discretisation picks is the other half of the convergence. On grids of 34 points and more at 0.1% noise every choice is 10⁻²·²⁵ or 10⁻²·⁵ — a quarter of a decade, one step of the sweep. At 1% every choice on 26 points and more is 10⁻¹·⁵; at 0.01%, on 40 points and more, 10⁻³. The earlier finding that the best λ on fine grids is one number for the sampled kernel is therefore not about the sampled kernel. It is one number for all three discretisations of the same blur at the same noise.

That has a direct consequence for how λ is chosen. A parameter-choice rule — the discrepancy principle, or generalised cross-validation — computed on a cheap sampled discretisation of a fine grid gives the λ the expensive integrated discretisation would have wanted. The λ is a property of the noise and the blur, not of how the blur was written down.

Where the choices differ is on coarse grids, and they differ in kind rather than in size. The sampled kernel on 16, 20, 24 and 26 points at 0.1% wants no λ; the integrated ones want 10⁻²·⁵ to 10⁻³ on 24 and 26 points and none on 20. The grid essay called a coarse grid the first filter. It is a stronger filter under the crude discretisation than under the faithful ones, which is the same statement as the earlier essay’s title read from the other side.

The coarsest grid that is good enough #

Put as a single number per discretisation — the coarsest grid within 2% of the fine-grid answer — the three noise levels tell three different stories.

At 0.1% the integrated discretisations get there on 26 points and the sampled kernel on 40. This is the regime where a better discretisation buys a smaller problem.

At 0.01% all three need 40. The noise is small enough that the fine-grid answer is limited by the step in the signal, which no smooth reading on a coarse grid represents, and the discretisation of the kernel is no longer the binding error.

At 1% the two hat discretisations get there on 40 points and the spline discretisation only on 96. Its 40-point error, 0.1418, is 3.1% above the fine-grid answer against 2.0% for the sampled kernel; this is the one place the spline discretisation’s high-noise disadvantage survives a λ, and it survives as a grid size rather than as an error. A spline reading of an answer that has to be heavily smoothed spends its extra continuity on something the λ is about to remove.

Why the 96-point answer is not the best answer #

The fine-grid reference used above is the three discretisations’ shared answer on 96 points, and it is not the least error on the figures. At 0.1% noise the integrated hat discretisation on 40 points reaches 0.1133, and at 0.01% it reaches 0.1073, both below the 96-point answers of 0.1178 and 0.1113. The sampled kernel and the spline discretisation dip at 40 points too.

A grid that beats finer grids under all three discretisations is a statement about the grid, not about any discretisation, and the likeliest reading is the step in the signal. A node that falls on or very near the step lets a piecewise reading represent the jump more sharply than the grids either side of it, and the error against the continuous signal is dominated by that jump once the noise is small. The 30-point bump is the same effect in the other direction. Taking the best grid anywhere as the reference would have credited a discretisation with a coincidence of node placement, which is why the reference is the 96-point answer the three agree on.

What the choice of discretisation is, once λ is chosen #

The earlier essay concluded that discretisation error and noise cannot be dealt with separately, because a more faithful discretisation is a worse-conditioned matrix. With a λ in the picture that conclusion needs a qualifier. They cannot be dealt with separately without a regulariser; with one, the conditioning stops mattering and the three discretisations become three routes to the same answer on any grid fine enough.

What remains is cost, and it is cost in two currencies. A faithful discretisation costs more to assemble — integrating a kernel against splines is a quadrature per matrix entry where sampling is an evaluation — and it can reach the fine-grid answer on a coarser grid at moderate noise. Which of those wins depends on how the assembly cost and the solve cost scale with the grid, which is a property of the problem’s dimension and of the solver, not of this blur. When the answer is a choice put the regularisation parameter at the centre of an ill-posed problem; the measurement here says the discretisation, once that parameter is chosen, is a choice about how cheaply to get there.

What this rests on #

One blur of width 2.5/63 on the unit interval, one signal of two bumps and a step, three discretisations on the same nodes, grids of 16 to 96 points, sixteen noise draws per point, Tikhonov regularisation with λ on a quarter-decade grid from 10⁻⁸ to 1, and the error measured against the continuous signal on 2,000 fine points. The best λ is the one whose median error over the sixteen draws is least — a single λ per grid, as a person tuning an instrument would have — and not a λ chosen per draw. The fine-grid reference is the median of the three discretisations on 96 points. Only Tikhonov regularisation is measured; a truncation might order the discretisations differently on coarse grids, where it and Tikhonov filter the leading components differently.

The claim that has to fail #

The claim is the natural extension of the earlier measurement: that a more faithful discretisation keeps its advantage once λ is chosen well, so that the discretisation and the regulariser are independent decisions. At 1% noise on 96 points, with each discretisation’s best λ, the sampled kernel reaches 0.1375 and the spline discretisation 0.1374. The refusal is fed the claim that the sampled error exceeds the spline one by more than 2% and fails.

Still open: a reading that can make a corner, and the grid as a parameter a rule could choose #

A reading with a breakpoint. At 0.01% noise all three discretisations need 40 points, and the reason given above is the step: no smooth reading of a coarse grid represents it. A reading with a breakpoint placed at the step — a spline with a knot of multiplicity four there, or a hat basis plus one jump function — would remove that limit without changing the operator’s conditioning, and would say how much of the 40 points is the step and how much is the bumps. The grid essay and its successor both named this and neither has measured it; with λ now known to settle the discretisation’s conditioning, it is the cleanest remaining test of representation alone.

Choosing the grid and λ together from the data. Every measurement here chose λ with the exact answer in hand, and chose among grids the same way. The finding that λ is one number across discretisations suggests a rule could choose it on a cheap discretisation and then choose the coarsest grid on which a faithful discretisation’s residual matches the fine one’s. Whether any data-driven rule can see the difference between a 26-point and a 40-point grid at 0.1% noise — a difference of 1.8 per cent in the error — is the question where the answer stops being in the data would ask of it.