Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Noise floor — where it appears

The level below which a computed quantity carries rounding error rather than information. A tolerance set beneath it stops selecting anything and starts counting the arithmetic, which is a failure mode with no error message.

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

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 stop from 10% noise to 0.0001%, and it overshoots for a reason. The best truncation walks up the spectrum in a straight line, six or seven indices a decade; the crossing climbs in jumps of 11, 0, 8, 5 and 1.

regularisation · 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 081624324048566410⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹index kmagnitudethe floor: k = 43best truncation: k = 31σₖ|uₖᵀb| exact|uₖᵀb| with noise|uₖᵀe|, smoothedcorrelation ρ = 0.9noise energy, first 28 directions0.98tilt of the noise floor, decades1.1the crossing43the best truncation31the floor tilts, and is still a floorρ = 0.9

Noise that spares the answer and fools the rules

Make each noise sample remember the last one, keep its size fixed, and the best answer available gets slightly better — 0.1056 to 0.1010 — because slow noise hides in the directions where dividing by σ costs nothing. The Picard crossing still lands two dozen indices past the best truncation. What breaks is the rules. Generalised cross-validation more than doubles the best error on 14 draws of 48 instead of 3, the discrepancy principle's typical cost triples, and the two miss in opposite directions. Whitening by the covariance takes GCV back to 3.

regularisation · Regularisation 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 -101-101(x − 1) ÷ 0.001p(x) ÷ 2.68·10⁻¹⁵a square, drawn negativepoints sampled401negative, unfused179negative, fused196signs disagree at98widest gap1.4·10⁻¹⁵unfusedfusedthe true valuethe true curve is the flat oneeverything else is rounding

A square that evaluates negative

(x − 1)⁶ evaluated near x = 1 comes out negative at 179 of 401 points on one build and 196 on another, and the two disagree about the sign at 98 of them. Neither is nearer the truth: both traces are made entirely of rounding.

machine · Fma contraction 12345678910111210⁻¹³10⁻¹¹10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹10¹order of the reduced modelworst relative errora model made of measurementssamples used24degree read6gap at the cut2·10⁸best model, order12its error2.7·10⁻¹¹states in the original40filled: at its own samplesopen: everywhere else

A model with no matrices behind it

Twenty-four numbers — values of a transfer function at twenty-four points — produce a sixth-order model of a forty-state system that passes through every sample to 10⁻¹² and matches the function it never saw to 10⁻⁹. Noise of 10⁻¹⁰ on those numbers takes the rank decision's gap from 10⁸ to 4.

reduction · Data-driven realisation 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 -15-13-11-910⁻¹³10⁻¹¹10⁻⁹10⁻⁷log₁₀ of the defect, relative to the entry it sits inhow far the answer movedthe machine, on its owna tolerance with two sidesmachine band3.2·10⁻¹²smallest caught10⁻¹²its nearest run4.6·10⁻¹²defects hidden3window, factor1.4below the band nothing is visibleand above it everything is

What a regression test can ask for

The machine's own variation on one solve is 3.2·10⁻¹², and the smallest defect whose answers clear it is one part in 10¹². The tolerance exists, it is bracketed on both sides by a factor of 1.42, and it is neither zero nor the 10⁻⁸ that usually gets typed.

machine · Regression tolerance

Named alongside it

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

Discrepancy principleParameter choiceRegularisationTikhonov regularisationIll-posed problemL-curveFilter factorsGeneralised cross-validationOraclePicard conditionBitwise reproducibilitySingular value decomposition

All concepts