Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Discrepancy principle — where it appears

A rule that stops regularising when the residual has fallen to the size of the noise, and therefore has to be told what the noise is.

Named by 2 essays across 2 fields — each of them below, with the objects they name alongside it.

015304560759010512010⁻²10⁻¹110¹steprelative sizeleast error: 20discrepancy stop: 7errorresidualthe knob is an integerleast error, at step20error there0.14error at step 1206the residual falls at every stepthe error turns and keeps rising

A parameter that counts steps

The regularisation field's knob is a positive real number chosen by one of three rules. The iterative field's is an integer nobody called a knob — where to stop. On the same problem the best step is 20 and the best λ is 0.025, and they reach 0.1426 and 0.1406.

combination · iterative regularisation 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.

Tikhonov regularisationConjugate gradientsCross validationFilter factorsIll posed problemIterative regularisationKrylov subspaceL curveNoise floorParameter choiceRegularisationReorthogonalisation

All concepts