The grid was the first filter

Every essay on regularisation here begins with a 64-point matrix and asks what to do with it. When the answer is a choice solves it without regularisation and gets a relative error of 5.5·10⁸; the essays after it choose a filter, find where the filter should fall, and score rules for choosing it. None of them asks where the 64 came from.

It came from a decision made before the matrix existed. A blur is a continuous operation — an integral of the signal against a kernel — and a 64-point matrix is one discretisation of it among many. A 12-point matrix of the same blur is perfectly well conditioned, and its unregularised solution is a coarse but honest picture of the signal. A 48-point matrix has a condition number of 10⁷ and its unregularised solution is noise. Somewhere between them the grid stops helping and starts hurting, and the place where it does turns out to be a number already measured under another name.

A continuous problem, and the grid it is solved on #

The setup has to be built with some care, because the obvious experiment answers the wrong question.

The blur is fixed in the continuous variable: a Gaussian of width 2.5/63 on the interval [0, 1], chosen so that on 64 points it is exactly the collection’s standing operator. The signal is fixed as a function — two smooth bumps and a step — rather than as a vector. On a grid of n equispaced points, the operator is the sampled kernel with each row normalised to sum to one, which is what anybody discretising this integral on n points would write down.

The data are where the care goes. If the data on each grid were generated by that grid’s own matrix applied to that grid’s samples of the signal, every grid would be exactly consistent with itself and a noise-free solve would be perfect on all of them. So the data are computed instead from the continuous problem: at each grid point, the blur of the continuous signal, integrated on two thousand quadrature points. A coarse grid then receives data it cannot quite explain, which is the honest situation — the discrete operator is an approximation to the instrument and the measurement was made by the instrument.

The noise is fixed per sample, at a fraction of the data’s root mean square, and drawn from the same seeds on every grid. A finer grid therefore has more measurements of the same quality, which is the situation in which refining it ought to help. And the error is measured against the continuous signal: each grid solution is joined into a piecewise-linear function and compared with the signal on the quadrature points, so a 12-point answer and a 48-point answer are scored on the same footing rather than each against its own samples.

Refining the grid makes the answer worse, then much worse #

With no noise, refinement does what it is supposed to. The error of the noise-free solve falls from 0.266 at 12 points to 0.183 at 16, 0.137 at 24, 0.130 at 26 and 0.100 at 40, and stays near there to 48. That curve is the discretisation error — how well piecewise-linear functions on n points can represent two bumps and a step, plus how well the sampled operator approximates the integral — and it improves with n, unevenly, because where the samples happen to land on the step matters.

At 0.1% noise per sample the same curve follows it down to 26 points and leaves it there. The noisy error is 0.130 at 26, 0.132 at 28, 0.141 at 30, 0.165 at 32, 0.267 at 34, 0.607 at 36, 5.04 at 40 and 761 at 48. The noise-free solve at 40 points is better than any noisy solve on any grid, and the noisy solve at 40 points is fifty times worse than the noise-free one.

So refining the grid of an unregularised solve has an optimum, and the optimum is not where the discretisation error is smallest. It is where the discretisation error stops falling faster than the noise amplification rises. Left of it, the grid is too coarse to represent the signal and the noise is irrelevant; right of it, the grid can represent the signal and the solve cannot afford to. The noise-free curve says nothing about where the optimum is, because it contains no noise; the condition number alone says nothing either, because it contains no discretisation error. The optimum is a joint property of the two, which is the definition of a regularisation parameter.

The best grid sits where the best truncation does #

A regularisation parameter already measured is the truncation index — how many singular components of the 64-point operator to keep. Scored the same way, against the continuous signal with the same noise per sample and the same seeds:

The best grid size is within two of the best number of components to keep, at all three noise levels — 24 against 24, 26 against 28, 34 against 32 — and the unregularised solve on it reaches within 4%, 11% and 16% of the best truncation’s error, and within 2%, 9% and 16% of the best Tikhonov solution’s.

That is a strong coincidence to leave as one, and it is not one. A grid of n points can only return a piecewise-linear function with n degrees of freedom. The best truncation keeps a K-dimensional space of the operator’s smoothest singular vectors. Both are restrictions of the answer to a subspace whose dimension is the parameter, both keep smooth functions and discard rough ones, and the noise decides the right dimension the same way in both: by where the next degree of freedom starts contributing more noise than signal. The grid is a truncation onto a different, cruder subspace, and it is chosen by the same trade.

The cruder subspace is also why it loses, and by more at low noise. At 1% noise the best dimension is 24 and both subspaces are smooth enough that it hardly matters which 24 functions are kept; at 0.01% the best dimension is over 30, and at that size the difference between the operator’s own singular vectors and a set of hat functions shows — a 16% gap. Four knobs and one floor found four parameters that share no arithmetic reaching the same floor within 3%; the grid is a fifth knob, the oldest of them, and it reaches the same floor less well.

A grid has filter factors, and they sum to its size #

The claim that a grid is a truncation can be made literal, in the vocabulary used here for every filter.

Take the 64 singular vectors of the fine operator and ask of each one how much of it survives being represented on an n-point grid — the squared length of its least-squares projection onto the hat functions, as a fraction of its own. That is a number between zero and one for each index k, which is precisely what a filter factor is: a statement of how much of direction k the answer is allowed to contain. Nobody chose these. They are what the grid does.

They sum to n, exactly — 24.000000 on the 24-point grid, 32.000000 on the 32-point one — because a projection onto an n-dimensional space has trace n and the singular vectors are an orthonormal basis. That is checked numerically rather than trusted. And they fall through one half at k = n: at 24 for the 24-point grid, at 16 for the 16-point grid, at 31 for the 32-point grid. So the grid keeps about n components in exactly the sense that a truncation at K = n does, and the trace — the quantity a second blur, narrower than the first found setting the width of a regularised answer’s averaging kernel — is the grid size itself.

The resolution matrix of the grid’s answer is therefore the projector these factors describe, and the width argument of that essay applies to it: a grid of n points resolves detail about 64/n fine-grid points wide, which is a tautology said about the grid and a measurement said about the filter factors.

What the grid keeps that a truncation would not #

The grid’s filter is not a clean step, and the way it differs from one is worth reading.

Below the shoulder it is softer than a truncation: at n = 24, index 20 is kept at 0.805 and index 23 at 0.709, where the truncation keeps both whole. Hat functions represent a smooth singular vector well and a moderately wiggly one only partly, so the grid starts losing components several indices before its size. That softness is part of why its error at the optimum is higher than the truncation’s.

Above the shoulder it does something a truncation never does: it keeps part of components it should have dropped entirely. Index 24 is kept at 0.042 on the 24-point grid, and index 25 at 0.331. On the 32-point grid index 33 is kept at 0.588, and the fractions from 33 onward sum to 2.62. This is aliasing. A singular vector just past the grid’s resolution oscillates at nearly the grid’s own spacing, and sampled there it looks like a smoother function the grid can represent — so part of it is folded back into the answer rather than discarded. The components that come back this way are the ones with small σ, which is to say the ones that divide noise by a small number, and the finer the grid the more of them come back.

That is a mechanism for the cliff beyond the optimum that the condition number alone does not show. A truncation past its best index adds whole components one at a time; a grid past its best size adds a fraction of the next few at once, including components well beyond its nominal cut.

Three answers on three grids #

The error curve is a summary. What the answers themselves look like is where the grid’s regularisation becomes visible, and the three worth drawing are one on each side of the optimum and one at it.

At 16 points the grid’s matrix has a condition number of 2.83 and the noise is invisible — the noisy error and the noise-free error are both 0.183. What is wrong with the answer is entirely resolution: the grid spacing is a fifteenth of the interval and the step, which is less than a seventh of it, spans two samples. That answer is regularised as heavily as it can be, and it shows the characteristic failure of heavy regularisation, the softened edge, with no λ anywhere.

At 26 points the answer is about as good as this kind of answer gets. The condition number is 61, the noise adds three thousandths to the error, and the rest of the 0.133 is the grid’s inability to put a corner exactly where the step’s corner is — the samples straddle it. This is the picture a well-regularised 64-point Tikhonov answer resembles, and the recovered signal at the best λ has the same rounded step for the same reason: no filter over smooth components can make a corner.

At 36 points the answer has crossed the cliff. Without noise this grid would do better than 26 points — 0.115 against 0.130 — because it resolves the step more finely. With noise the answer oscillates with an amplitude of two across the part of the interval where the signal changes fastest, and its error is 0.501. The grid has admitted components whose σ is small enough that a noise of one part in a thousand is amplified to the size of the signal, and the oscillation is those components. It is the same picture as the 64-point unregularised solve, at a milder scale, and for the same reason.

The cliff is a condition number meeting the noise #

The grids’ condition numbers grow faster than exponentially: 1.3 at 12 points, 2.8 at 16, 29 at 24, 61 at 26, 790 at 32, 5,900 at 36, 56,000 at 40 and 10⁷ at 48. That is the discrete shadow of a spectrum falling like exp(−k²): each extra grid point admits a component whose σ is smaller than the last by a growing factor.

The cliff — the first grid past the optimum at which the error has doubled — sits at 30 points for 1% noise, 34 for 0.1% and 40 for 0.01%. The condition numbers there are 316, 2,100 and 56,000. Read against the noise levels, κ times the noise is 3.2, 2.1 and 5.6: the error doubles when the condition number has grown to a few times the reciprocal of the noise. That is the condition number as an amplifier read in reverse — not how much a given κ costs, but which grid first has a κ the measurement cannot pay for — and it is an order-of-magnitude statement, since κ is a worst case over directions and the noise does not arrange itself along the worst one.

The cliff moves four to six grid points for each decade of noise, and the best grid moves with it. That rate is the grid version of the slow walk the Picard essay measured: the best truncation there moves six or seven indices a decade, and here the best truncation of 64 points moves from 24 to 28 to 32. A factor of a hundred in measurement quality buys ten grid points, because the spectrum falls so fast that every additional point costs more than the one before.

What the coarse side of the curve is made of #

Left of the optimum the noisy and noise-free curves coincide, and that side is worth a closer look, because it is the part of the error no amount of care with the noise will reduce.

It has two sources and the experiment does not separate them. One is representation: a piecewise-linear function on n points cannot follow a step or the peak of a narrow bump. The other is the operator: the sampled, row-normalised kernel is a quadrature rule for the integral, and on a coarse grid it is a poor one — at 12 points the grid spacing is 2.3 times the blur’s standard deviation, about its whole width at half height, so a neighbouring sample gets a weight of 0.07 against the centre’s one, each row is nearly a spike, and the “deconvolution” is barely a deconvolution at all. Both shrink as n grows, unevenly, and the noise-free curve is their sum. The dip at 26 points and the bump at 30 in that curve are the step’s corner landing on a sample and between two.

What can be said is that this error is systematic and grid-dependent, and it is what a different equation on every grid warns about in another field: a convergence study on a sequence of grids measures the discretised equations, and the discretised equations are not the same problem at every n. Here the lesson has a sharper edge. A convergence study of this deconvolution with noisy data would find the answers converging up to about 26 points and then diverging, and would be tempted to call the divergence a bug.

Why nobody calls it regularisation #

A grid is chosen for reasons that have nothing to do with noise — the resolution of a detector, a memory budget, a mesh inherited from another code — and it is chosen first. By the time anybody thinks about regularisation, the dimension of the problem has been fixed, and every tool in these essays treats that dimension as given. A parameter chosen on a smaller problem is the one essay here in which the size of the problem moves, and there the smaller problem is a Krylov projection chosen by the iteration rather than a grid chosen by a person.

The measurement says the separation is an illusion. On this problem, a person who picked 24 or 26 points for an unrelated reason and solved without regularisation would get an answer within about a tenth of the best Tikhonov answer on a finer grid, and a person who picked 40 points would get an answer with a relative error of 5 — five times worse than returning zero. Neither would have made a decision about regularisation, and both would have made one. When a fine grid is chosen, the grid’s own filter factors keep nearly everything, the regularisation has to be done explicitly, and everything measured in these essays applies; when a coarse grid is chosen, the grid has already done it, crudely, and an explicit filter on top of it filters an answer that was already filtered.

The practical form is a question worth asking before choosing λ: how many components does the grid itself admit, and is that already fewer than the noise can afford? Its answer is the grid size, read as a trace, against a best truncation that where the answer stops being in the data bounds from above with the Picard crossing. If the grid is below it, λ has little left to do.

Where this goes from here #

Three measurements continue from this one, and each removes a simplification it made.

The grid and λ together. Everything here is either a grid with no λ or a fine grid with λ. The joint question — which pair of grid and λ is best, and whether a moderately coarse grid with light regularisation beats a fine grid with heavy — is a two-parameter surface, and the aliasing measured above suggests the answer depends on the grid’s filter past its shoulder, which explicit regularisation cannot remove because it acts on the grid’s own singular vectors rather than the fine ones.

Correlated noise on a refined grid. Noise that is independent per sample on one grid is not the same physical noise as noise independent per sample on another. A real instrument’s error has a correlation length in the continuous variable, so refining the grid makes the noise per sample more correlated. Noise that spares the answer and fools the rules measures what correlation does at a fixed grid; the grid sweep with a fixed physical correlation length is not drawn, and it would move the optimum, probably to finer grids, since slow noise is cheap.

Better subspaces than hat functions. The grid loses to the truncation by 4 to 16 per cent because hat functions are a crude basis for this operator. Higher-order elements, or a basis adapted to the kernel, would close some of that gap while keeping the grid’s one virtue — that it was never ill-conditioned to begin with — and whether the gap closes entirely, so that a well-chosen discretisation is a complete regularisation, is open. The general-form penalty in a parameter that counts steps is the explicit version of preferring smooth answers, and comparing its kernel with a grid’s would say how much of what it does a discretisation does for free.