A second blur, narrower than the first

The first two essays on regularisation read it as a list. When the answer is a choice writes both standard methods as one sum with a weight on each term, and where the answer stops being in the data finds the index at which the weights ought to fall. Every quantity in both is indexed by k, the position in the singular value decomposition, and every error in both is measured against a truth that exists only because the problem was built rather than observed.

There is a second way to read the same weights, in the space of the answer rather than the space of the spectrum, and it has a property the first reading does not: part of what it says about the error can be computed without the truth at all. The regularised answer turns out to be a matrix applied to the true signal, plus a filtered copy of the noise, and the matrix depends on the operator and on λ and on nothing that was measured. Its rows can be drawn. They look like the instrument’s own blur, only narrower, and with a feature the instrument never had.

The answer is a matrix applied to the truth #

The Tikhonov answer is x_λ = R_λ b, where R_λ = V F Σ⁻¹ Uᵀ and F holds the filter factors fₖ = σₖ²/(σₖ² + λ²) on its diagonal. The data are b = Ax + e, the blurred truth plus noise. Put the two together and the algebra is a single line:

x_λ  =  R_λ A x  +  R_λ e  =  V F Vᵀ x  +  R_λ e

The first term is the whole of the claim. V F Vᵀ is a matrix that the true signal is multiplied by, and it contains V and F — the right singular vectors of the operator and the weights λ put on them. It does not contain b. It does not contain e. It does not contain x. It can be computed, printed and plotted before a single measurement is taken, and it says what the regularised answer will do to whatever signal is actually out there.

Its rows are called averaging kernels, and the name is exact. Row i says with what weights the answer at point i averages the true signal at every other point. For the unregularised solve, F is the identity and V F Vᵀ = VVᵀ = I, so each row is a spike and the answer at i is the truth at i — plus a noise term that on this problem is five hundred million times the signal. Regularisation trades that noise term away, and what it pays with is the spike. The row becomes a bump with a width.

Measured on the collection’s standing problem, a 64-point Gaussian deconvolution, at λ = 3.98·10⁻³ — the value that minimises the error at 0.1% noise — the middle row is 2.82 points wide at half its height. The blur whose effect it is undoing has rows 5.89 points wide. So the regularised answer has not removed the blur. It has replaced it with a second one, a little under half as wide, and the answer is the truth seen through that. The entries of the middle row sum to 0.9999, which is the statement that a constant signal passes through undamaged — the blur preserves constants by construction, and a constant lives in the leading singular directions where every filter factor is close to one.

Narrower than the instrument, and negative where it never was #

The width is the obvious difference. The shape is the one that matters for reading an answer.

A Gaussian blur’s rows are positive everywhere: every point of a blurred signal is a weighted average of the true signal around it with all weights positive, which is why a blurred picture looks soft rather than wrong. The kernel is not like that. It dips to −0.075 two to three points either side of its peak, rises to a small positive lobe of 0.043 beyond that, and oscillates with decreasing amplitude out to the edge of the plot. The answer at a point is therefore the truth nearby, minus a fraction of the truth a little further away, plus a smaller fraction beyond that.

That is what produces the ringing every regularised reconstruction of an edge shows, and it can now be stated as a number rather than a complaint. Put a unit step through the kernel at the best λ: the 10%-to-90% rise takes 2.23 points where the blur’s own rise takes 6.47, the answer overshoots the top of the step to 1.091 and undershoots the bottom to −0.091. None of those three numbers depends on the noise draw. They are properties of V F Vᵀ, and a reader looking at an overshoot of nine per cent beside an edge in a reconstruction can know, from the operator and λ alone, that nine per cent is what this kernel does to any edge — and that the overshoot is therefore not evidence of anything in the signal.

Heavier regularisation softens the ringing and widens the kernel together. At λ = 0.1 the side lobes are −0.041 and the width 4.29. Lighter regularisation sharpens both: at λ = 10⁻⁵ the width is 1.96 and the deepest lobe −0.101. No choice of λ gives a kernel that is both narrow and positive, because the kernel is built from a finite number of smooth singular vectors, and a narrow function made of smooth pieces has to cancel itself on the flanks.

Most of the error is the kernel’s, and the kernel is free #

The decomposition x_λ − x = (V F Vᵀ − I)x + R_λ e splits the error into two vectors that are measured by different information. The first needs the truth; the second needs the noise; neither needs the other, and their sum has to be the error computed directly. It is, to 1.8·10⁻¹² relative at worst, which is the two-routes check applied here to anything it is about to build an argument on.

At the λ that minimises the error, three noise levels:

The column to read is the fourth against the fifth. At the best λ, the kernel’s part of the error is larger than the noise’s at every level, by a factor of 2.3 at 1% noise and nearly 9 at 0.01%. The optimum is not a balance point where the two contributions are equal. As λ shrinks the kernel’s part falls slowly and the noise’s part rises steeply, and the minimum of the total sits where those two rates cancel — which on a spectrum that decays like this one is well before the two parts are the same size.

That has a practical reading. The larger half of the error in a well-regularised answer is not a random quantity at all. It is a deterministic blurring of the truth by a known matrix, and the uncertainty about it is entirely uncertainty about what the truth contains at scales finer than the kernel. A small residual is not a small error is the collection’s standing warning that an answer can fit its data perfectly and be wrong; here is the specific way it is wrong, and the way is printed on the kernel.

The noise’s half has its own number that needs no truth either. ‖R_λe‖/‖e‖, the factor by which the filtered solve amplifies whatever noise the data carry, is 5.9 at the best λ for 1% noise, 27.9 at 0.1% and 119.8 at 0.01%. It rises as the noise falls because the best λ falls with it, and a smaller λ keeps more of the components that divide by a small σ. That is the condition number as an amplifier, applied not to the operator but to the regularised operator, where it is finite and was chosen.

The width is a count of what the filter keeps #

The width moves with λ, and it moves in a way that has a law in it.

The trace of F, Σfₖ, is the number of components the filter keeps — a sum of fractions, so a real number rather than an integer, but at λ = 3.98·10⁻³ it is 28.1 and the matched truncation keeps 28. It is also the quantity generalised cross-validation divides by, where it appears as the effective number of parameters the fit has spent. Multiply the kernel’s width by it and divide by n:

width × Σfₖ / n lies between 1.10 and 1.27 at every λ from 10⁻⁸ to 10⁻¹, with a median of 1.22, while the width itself goes from 1.37 points to 4.29 over the same range. Sizes 48, 64 and 96 give the same widths to three figures — the blur is a fixed number of grid points wide in all three — and traces in proportion to n: 24.0, 31.5 and 46.7 at λ = 10⁻³. So the kernel is n/Σfₖ grid points wide to within a fifth, and the resolution of a regularised answer is, to that accuracy, the grid divided by the number of components kept.

The constant has a reading, though it is a comparison rather than a derivation. A matrix like this one — nearly symmetric, and nearly constant along its diagonals — has singular vectors that are close to cosines, which a limit the matrix never reaches makes precise for the family it belongs to. An ideal filter keeping the first K of n cosines produces a kernel that is a periodic sinc, whose main lobe is 1.207n/K wide at half height. The measured 1.10 to 1.27 sits around that number, lower where the filter’s shoulder is gentle relative to what it keeps and higher where it is sharp. The cosine picture is an approximation to this matrix and the agreement is a measurement, not a proof.

The slowness has a reading too, and this one is closer to exact. The blur’s singular values fall like exp(−ck²), so the index at which σₖ passes λ grows only like the square root of log(1/λ). Between λ = 10⁻¹ and 10⁻⁵ the logarithm grows fivefold, so the count kept should grow by √5 = 2.24 and the width shrink by the same factor. The measured widths are 4.29 and 1.96, a ratio of 2.19. Four decades of λ buy a factor of 2.2 in resolution, which is the resolution-side statement of what the Picard essay found for error: a million-fold better instrument buys a factor of two.

Where the count stops describing the width #

The law is claimed from 10⁻⁸ to 10⁻¹ and the figure is drawn to λ = 1, deliberately, because the part past 10⁻¹ is where it fails and the failure is informative.

At λ = 0.32 the constant has fallen to 1.03, and at λ = 1 it is 0.52, with the width at 7.27 points — wider than the blur. Nothing has gone wrong in the arithmetic. At λ comparable to the largest singular value the filter has stopped keeping some components and dropping others; it is multiplying every one of them by roughly σₖ²/λ², so the kernel becomes the shape of AᵀA scaled down, and AᵀA is the blur applied twice. A blur applied twice is wider than the blur. Σfₖ, meanwhile, collapses towards zero, and a count that is collapsing no longer describes a width that is growing.

So the statement has a boundary, and the boundary is where regularisation stops being a truncation with a soft edge and becomes a uniform damping. The best λ at 1%, 0.1% and 0.01% noise — 2.5·10⁻², 4.0·10⁻³ and 1.2·10⁻³ — all sit well inside the range where the count works, and a λ past 10⁻¹ on this problem is one no rule measured in these essays has chosen when told the truth about the noise. The first version of the check behind this figure required the constant over the whole drawn range and refused its own figure, which is why the range a law is claimed over is now named separately from the range that is drawn.

Two spikes, and the separation the kernel decides #

A width is a number about one feature. The question a reader of a reconstruction usually has is about two: whether two things close together in the answer were two things in the truth.

The test is the Rayleigh criterion’s depth: two peaks are seen as two when the dip between them falls below 81% of the lower one. Any fixed depth is a convention, and what the comparison needs is only that the same convention is applied to both operators.

The blur needs seven points of separation. The kernel needs four. At four points the kernel’s image dips to 0.40 of its peaks — decisively two. At seven the blur’s image just dips below 0.81. So on this problem, at this noise level, regularisation roughly halves the separation at which two features can be told apart, which is the same factor it applies to the width, as it should be.

And one point closer, at three, the kernel’s image has no dip at all: two spikes three points apart are returned as one feature, with nothing in the answer to say that it was ever two. The transition is abrupt because the kernel’s flanks are steep — the same steepness that produces the negative lobes — and it sits within about one point of the kernel’s own width of 2.82.

That separation is the quantity worth publishing beside a reconstruction, and it is available before the data arrive. Two structures closer than four grid points in a regularised answer computed this way are not evidence of two structures; two structures further apart than four are, subject to the noise term. Rank is a decision makes the same point about a matrix whose singular values have a gap: the resolution of the answer is decided by a threshold, and the threshold belongs next to the answer rather than inside the method.

A truncation’s kernel rings harder for the same width #

Truncation has a kernel too, and comparing the two kernels at matched strength says something the two errors could not.

Four knobs and one floor found that truncation and Tikhonov reach best errors within 3% of each other on this problem, and on the draw used here they are 0.1058 and 0.1051. Their kernels at matched strength have nearly the same width, 2.86 against 2.82, and the width law holds for both — 1.251 for the truncation. What differs is the ringing. A truncation’s filter is a step, and a step in the spectrum is a sinc in space whose side lobes decay slowly; Tikhonov’s filter has a shoulder a decade wide, and the shoulder damps the lobes. The second lobe is 40% larger for the truncation.

That is a difference a caller can see and an error norm cannot. Two answers with the same relative error and the same resolution can differ in how much false structure they draw beside every edge, and which of them is better depends on whether the reader of the answer is more misled by a softened edge or by a ghost beside it — a question about the use of the answer rather than about its accuracy.

The edge of the signal has a kernel of its own #

Every number above is for the middle row. A kernel is a row of a matrix, and the matrix has rows near its boundary too.

Near the edge the kernel’s width barely changes, 2.83 points against 2.82, but its shape does. It cannot spread symmetrically, so the negative lobe that would sit on its left is pushed against the boundary and deepens to −0.096 there, and the entries sum to 0.992 — a constant signal near the edge is returned eight parts in a thousand low. Those are small numbers, and they are the kind of small number that matters for a reconstruction whose interesting feature happens to sit near the edge of the field of view, where the answer’s value at the last point is partly an extrapolation made by the singular vectors rather than an average of anything that was measured.

A resolution statement is what a caller can publish #

Put the pieces together and a regularised answer comes with three things that do not require the truth.

A kernel for every point, which says what the answer at that point is an average of. It is exact, it is V F Vᵀ, and it costs one matrix product once the decomposition is in hand.

A width and a separation, which summarise the kernel as a length: 2.82 points and four points here. The width law makes the first predictable from a single number already computed for parameter choice — n divided by the trace, times about 1.2.

A noise amplification, ‖R_λe‖/‖e‖ or its expected value from the filter factors, which bounds the part of the error that is random.

What remains unknown is the other part — how far the truth itself differs from its own blurred copy — and that cannot be known, because it is exactly the information the instrument destroyed. The field’s constructed problem makes it measurable here, at 0.1023 of the answer’s 0.1051, which is the reason an answer that is known is worth its construction. For any real measurement the honest publication is the kernel and the noise bound, with the statement that detail finer than the kernel is not in the answer and was never in the data.

The data-space twin already met #

The resolution matrix has a partner on the other side of the operator. Multiply R_λ by A on the left instead of the right and the result is A R_λ = U F Uᵀ — the matrix that maps data to fitted data, the influence matrix. Influence is decided before the data reads the diagonal of the unregularised version of it as leverage, and finds the same property this essay finds for the kernel: it is fixed by the design, and the response appears nowhere in it.

The two matrices share their filter and their trace. Σfₖ is the influence matrix’s trace, which is the number of degrees of freedom the fit spends, and it is the resolution matrix’s trace, which divided into n gives the kernel’s width. One number read two ways: the more of the data the fit is allowed to follow, the finer the detail its answer can show, and the exchange rate between the two is the constant of about 1.2 measured above.

Where this goes from here #

Three continuations follow from this essay, and each changes one thing the kernel took for granted.

Noise that is not white. The noise’s part of the error was bounded here by a single amplification factor, which assumes the noise is spread evenly over the singular directions. Noise that spares the answer and fools the rules measures what happens when it is not, and finds the kernel’s side of the ledger untouched and the parameter-choice side badly damaged.

The grid as a kernel. Everything here is on a 64-point grid that was chosen before λ was. A coarser grid can only represent smooth functions, so it has an averaging kernel of its own before any filter is applied. The grid was the first filter measures that kernel as filter factors and finds that the best grid for an unregularised solve sits where the best truncation does.

And choosing λ for a resolution instead of an error. Every rule measured in these essays picks λ to make an error small. The kernel makes it possible to pick it to make a width small subject to a bound on the noise amplification, which is the Backus–Gilbert formulation from geophysics, and it would rank the λs on this problem differently from the oracle — at the best λ the kernel’s part of the error already dominates, so a rule asking for resolution would push λ lower than the error-minimising value. How much lower, and what the answer looks like there, is not measured here. The general-form penalty that a parameter that counts steps measures would change the kernel’s shape as well as its width, and its kernel is not drawn either.