Numerical Linear Algebra
where the algebra stops being the arithmetic
Series

Fitting — the series

5 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. 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.

    part 3 · leastsquares
  2. 08162432404810⁻¹10²10⁵10⁸10¹¹10¹⁴10¹⁷10²⁰degreeκ of the design matrix1/u: past this a double holds nothingmonomialsChebyshevArnoldi on the pointsκ at degree 48monomials1.5·10¹⁷Chebyshev1.6·10⁷Arnoldi on the points1200 two intervals with a gap between themthree bases for one space of polynomials

    A basis built from the points

    A polynomial fit computed in monomials and in an orthogonal basis gives the same curve on exact data, and the valley essay drew the two lying on top of each other. Add 0.1% noise and they separate — by 1.7·10⁻⁵ at degree 40 and 0.004 at degree 48 — because the fitted curve moves with the basis by its condition number times the rounding times the residual. Chebyshev polynomials keep that small only on points spread like their weight; on a sample with a hole in it they reach κ = 1.55·10⁷. A basis orthogonalised against the sample points themselves stays at 1 on every set.

    part 4 · leastsquares
  3. 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.

    part 5 · leastsquares
  4. 124816the smooth function, σ = 0.01generalised cross-validationleave-one-outinformation criteriondiscrepancy principlethe smooth function, σ = 0.0001generalised cross-validationleave-one-outinformation criteriondiscrepancy principle|x|, σ = 0.01generalised cross-validationleave-one-outinformation criteriondiscrepancy principle|x|, σ = 0.0001generalised cross-validationleave-one-outinformation criteriondiscrepancy principle1/(1.05 − x), σ = 0.01generalised cross-validationleave-one-outinformation criteriondiscrepancy principle1/(1.05 − x), σ = 0.0001generalised cross-validationleave-one-outinformation criteriondiscrepancy principleerror of the rule's degree over the best degree'sdot: median · line: to the 95th percentile · logarithmicone rule stops at the kink

    The rule that divides by one minus the leverage

    On a smooth function the rules that choose a polynomial fit's degree were forgiven by a lopsided valley: too few degrees cost thousands of times the best error, too many about twice. On |x| and on a function with a pole just outside the interval, the left wall was predicted to flatten, the best degree to climb, and the information criterion's tight threshold to become a liability. All three happen. The wall falls to a twentieth more, the best degree on |x| runs to the largest the basis has, and the criterion is the costliest rule on |x| at one per cent noise. But the rule that actually fails is leave-one-out: at small noise it stops at degree 26 and costs twelve times the best error, because by degree 26 the leverage of the end points is 0.97 and its formula divides every residual by what is left.

    part 6 · leastsquares
  5. 124816equispaced points, σ = 0.01generalised cross-validationleave-one-outinformation criteriondiscrepancy principleChebyshev points, σ = 0.01generalised cross-validationleave-one-outinformation criteriondiscrepancy principleequispaced points, σ = 10⁻⁴generalised cross-validationleave-one-outinformation criteriondiscrepancy principleChebyshev points, σ = 10⁻⁴generalised cross-validationleave-one-outinformation criteriondiscrepancy principleequispaced points, σ = 10⁻⁶generalised cross-validationleave-one-outinformation criteriondiscrepancy principleChebyshev points, σ = 10⁻⁶generalised cross-validationleave-one-outinformation criteriondiscrepancy principleerror of the rule's degree over the best degree'sred: leave-one-out · logarithmic, cut at 16the points, not the rule

    Chebyshev points make the two rules one

    On 200 equispaced points leave-one-out cross-validation stopped a fit to |x| at degree 26, where the best was 120, because the end points' leverage had reached one and the score divides by what is left. On Chebyshev points the largest leverage stays at twice the average, and leave-one-out was predicted to follow the best degree to within five and cost within ten per cent. At small noise it lands on the best degree on the median draw at no cost at all; at one per cent it is six degrees off and within 1.06, which is as close as any rule gets there. What the prediction did not say is that it stops being a different rule: on Chebyshev points leave-one-out and generalised cross-validation choose the same degree on 86 to 100 draws in a hundred. And the earlier defence of the equispaced stop — that degree 26 was the honest degree for the ends — does not survive measuring the ends: there it costs the end points a thousand times the best they could have.

    part 7 · leastsquares

All series