Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Oracle — where it appears

The parameter that actually minimises the error of a regularised solution, found by comparing every candidate against the exact answer. It exists only for a problem constructed so that the answer is known, which makes it the reference practical rules are scored against rather than a rule itself.

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

27121722273237424710⁻²10⁻¹110¹subspace size kvalueno answer below 8GCV's traceλ from GCVλ from the residuala denominator that is not the problem'strace at k = 41trace at k = 4827λ range across the run2.2subspace before an answer8the divisor moves by twenty-sevenand the answer does not move

A parameter chosen on a smaller problem

Inside a hybrid method the regularisation parameter is chosen on a 25×24 problem rather than a 64×64 one. The rule that reads a residual transfers exactly; the rule that reads a trace is biased by exactly two grid steps at twenty-four steps and one at forty, at every noise level from 10% to 0.1%.

combination · Parameter choice 110¹10²10³10⁴10⁵10⁶error ÷ the oracle's, on the same drawten times the oracleover tendiscrepancy principletold ‖e‖0 of 1000unbiased risktold σ²15 of 1000cross-validationtold nothing57 of 1000quasi-optimalitytold nothing0 of 1000L-curvetold nothing0 of 1000blue: median · bar to the 90th percentile · line to the 99th · red: worstthe counts are the tail

One draw in twenty

Sixteen draws gave generalised cross-validation a worst case of 12%. A thousand draws at each of five noise levels give it a second answer on four to six in every hundred, ten to seven million times worse than the oracle, while its median stays among the best of five rules. The quasi-optimality criterion, told nothing either, never costs more than 1.41 in five thousand draws. The share settles by a thousand draws, and letting the search look further down more than triples it.

regularisation · Parameter choice 10⁻⁸10⁻⁷10⁻⁶10⁻⁵10⁻⁴10⁻³10⁻²10⁻¹110⁻⁴10⁻³10⁻²10⁻¹110¹10²10³10⁴λnoise part ÷ signal part, in ‖x‖where every corner sitsthe corner, ×2.29the oraclethe corner reads ‖x‖noise share at the corner0.23noise share at the oracle0.026corner ÷ oracle, this draw2.3corner ÷ oracle, 60-draw median1.5noise share: ‖L·(noise part)‖ ÷ ‖L·(signal part)‖the corner reads that share

The corner reads the norm it is drawn in

The L-curve was the costliest rule this field scored, and the cost was not the rule's. On the same sixty draws, with the same best achievable error, the corner of ‖x‖ against the residual costs 1.53 times the oracle and the corner of ‖L₁x‖ costs 1.003. Across five signals and three penalties the corner lands wherever amplified noise is between a tenth and a fifth of the norm being plotted, and it finds the oracle only when the oracle happens to sit there — twenty-nine times too costly on a smooth signal under ‖x‖, within half a per cent on four spikes.

regularisation · Parameter choice 1110¹10²10³10⁴10⁵the noise level it is told ÷ the true oneerror ÷ the oracle's0.40.50.71.523twice the oraclecliff, ρ = 0.69told the truthworst of 400middle 80%median draweach draw against its own oraclecliff, median ρ0.69told the truth, median1.1told a half, median3201shaded: the middle 80% of drawsbelow the cliff the error has doubled

Thirty-two coefficients instead of a noise level

The discrepancy principle has to be told the noise, and told too little it does not degrade — it falls off a cliff, at 0.80 of the truth when the noise is 10% and at 0.58 when it is 0.001%, exactly where the understatement forces the filter past its best truncation. The missing number is in the data. The root mean square of the last thirty-two coefficients never sends the rule over the cliff at or below 1% noise in four hundred draws, where eight coefficients with the same median do so thirty-five times.

regularisation · Parameter choice

Named alongside it

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

Discrepancy principleParameter choiceGeneralised cross-validationIll-posed problemNoise floorTikhonov regularisationFilter factorsInfluence matrixL-curveRegularisationGolub kahan bidiagonalisationHybrid regularisation

All concepts