Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Cross-validation — where it appears

Choosing a model parameter by holding part of the data out, fitting to the rest, and scoring the fit on what was held out. It estimates prediction error without knowing the noise level, at the price of repeated fits and a score that is itself random in the split.

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

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 how lopsided the valley isσ = 0.1: 6 too few ÷ 40 too many17σ = 10⁻³: 6 too few ÷ 40 too many231σ = 10⁻⁶: 6 too few ÷ 40 too many8184-50510152025303540110¹10²10³10⁴degree minus the best degreeerror ÷ best degree's errorσ = 0.1σ = 10⁻³σ = 10⁻⁶left of the line: too few degrees; right: too manya missing degree costs orders, an extra one a few per cent

The degree that is safe to overshoot

The rules that choose a Tikhonov parameter miss by factors of millions on one draw in twenty. Transplanted to the degree of a polynomial fit, in a basis orthonormal on the data, the same rules never cost more than 2.7 times the best degree's error in three hundred draws. The reason is the shape of the valley they search: six degrees too few costs from 44 to 16,000 times the best error, forty degrees too many costs about twice it. The one rule with a tail, the discrepancy principle, has its threshold half a standard deviation above the residual it is waiting for.

leastsquares · Fitting

Named alongside it

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

Discrepancy principleBias varianceGeneralised cross-validationIll-posed problemL-curveLeast-squaresLeverageNoise floorOrthonormal basisParameter choiceLeast squares by QRRegularisation

All concepts