Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Regularisation — where it appears

4 essays name this object, across 2 fields. What follows is each of them, and 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 081624324048566410⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹index kmagnitudethe floor: k = 32best truncation: k = 28σₖ|uₖᵀb| exact|uₖᵀb| with noisetwo different indicesthe crossing, from the data alone32the truncation that is actually best28relative error there0.11the exact coefficients never flattenthe noisy ones stop at ‖e‖/√n

Where the answer stops being in the data

The Picard condition finds the index where a noisy right-hand side stops carrying signal, from the data alone, with no knowledge of the answer. It lands at 32 where the truncation that actually minimises the error is 28 — and at 45 where the best is 38. It overshoots at every noise level from 1% to 0.001%, and it overshoots for a reason.

regularisation · regularisation 10⁻⁴10⁻³10⁻²10⁻¹110¹10²10³10⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹relative change in the coefficients, along the worst directionrelative increase in the residualcoefficients doubled39% change, fit unmoved in the sixth digit308×: the third digit movesκ(A) = 3.6·10⁶. Exact arithmetic would pick one point on this floor. It would not raise it.24 points, degree 9, monomial basisthe data leaves them free

The valley with no bottom

A degree-nine fit's coefficients can be moved by a third of their own size before the residual changes in the sixth significant figure. The arithmetic did not lose those digits. The data never contained them.

leastsquares · fitting 10⁻²10⁻¹110¹10²10³10⁴‖Ax − b‖‖x‖the oraclediscrepancyL-curvegeneralisedscored against a truth none hasoracle, relative error0.11discrepancy principle, as a multiple1.1L-curve corner, as a multiple2.3generalised cross-validation, as a multiple1the oracle needs the exact answer and is not a methodit is the reference the others are scored on

Choosing without knowing

Three published rules for choosing a regularisation parameter, scored against an oracle that requires the exact answer and is therefore not a method. Generalised cross-validation lands on the oracle's λ exactly; the discrepancy principle costs 6%; the L-curve costs 129%. And told a noise level ten times too small, the discrepancy principle's error goes from 0.112 to 10,449.

regularisation · parameter choice

Named alongside it

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

Ill posed problemCondition numberFilter factorsNoise floorSingular value decompositionTikhonov regularisationTruncated svdBasis choiceCross validationDeconvolutionDiscrepancy principleIll posedness

All concepts