Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Deconvolution — where it appears

Recovering a signal from a blurred copy of it, which means solving a linear system whose operator is a smoothing kernel. The kernel's singular values decay with no gap, so the problem is ill-posed and every usable answer to it is a regularised one.

Named by 3 essays across one field — each of them below, with the objects they name alongside it.

081624324048566400.250.50.751index kfilter factor fₖno regularisation: fₖ = 1truncationTikhonovthe same sum, three weightsTikhonov, relative error0.11truncation, relative error0.11no filter at all5.5·10⁸both filters are one expression with a different weightfₖ = 1 is the catastrophe

When the answer is a choice

A backward-stable least-squares solve of this problem returns an answer whose relative error is 5.5·10⁸. Nothing went wrong. The singular values decay exponentially with no gap anywhere in them, the data does not determine the answer, and something outside the data has to choose — which is the computation rather than a preliminary to it.

regularisation · Regularisation 192123252729313335373941434500.10.20.30.40.50.60.7position jweight on the true signal at jthe blur's row, 5.89 widethe kernel, 2.82 widecomputed from A and λ alonekernel width at half height2.8components kept, Σfₖ28width × Σfₖ / n1.2deepest negative lobe-0.075no data and no truth went into this curvethe answer is the truth seen through it

A second blur, narrower than the first

A regularised answer is not the truth with the noise taken out. It is the truth seen through a second blur, V F Vᵀ, which depends on the operator and λ and on nothing that was measured. At the best λ for 0.1% noise its rows are 2.82 points wide against the instrument's 5.89, they dip to −0.075 on either side, and their width times the number of components kept stays between 1.10n and 1.27n across seven decades of λ. Two spikes four points apart come back as two; three apart, as one.

regularisation · Regularisation 1216202428323640444810⁻¹110¹10²grid points nrelative error against the continuous signalbest truncation, 0.117best grid: n = 26best K = 28with noisenoise-freeno λ anywhere in this curvebest grid, error0.13best truncation, error0.12κ on the best grid61grid where it has doubled34every point is an unregularised solvethe grid chose the truncation

The grid was the first filter

A continuous deconvolution discretised on n points and solved with no regularisation at all is not unregularised. Its error against the continuous signal is least at 24, 26 and 34 points for noise of 1%, 0.1% and 0.01% per sample — beside best truncations of 24, 28 and 32 components on a 64-point grid — and within 4 to 16 per cent of their error. The grid's own filter factors sum to n exactly and fall through a half at k = n. Choosing the grid was choosing a truncation, before anybody chose a λ.

regularisation · Regularisation

Named alongside it

The objects these essays reach for when they reach for this one.

Filter factorsIll-posed problemRegularisationTruncated SVDCondition numberResolution matrixSingular value decompositionTikhonov regularisationAveraging kernelDiscretisationDiscretisation errorGeneralised cross-validation

All concepts