Numerical Linear Algebra
where the algebra stops being the arithmetic
Field

Least squares, and the road not to take

The normal equations are taught first and used by nobody, because forming AᵀA squares the condition number and then, below a computable value of ε, breaks outright. Underneath that is a harder fact: a wide range of very different fits explain the data equally well, and no arithmetic can choose between them.
everything Ax can reachb = (1.1, 0.4, 1.5)Ax, the closest pointr = b − Ax‖Aᵀr‖ / (‖A‖‖r‖)1.7·10⁻¹⁶‖b‖² − ‖Ax‖² − ‖r‖²1.3·10⁻¹⁵‖r‖1.3200 random nearby points of the plane were tried; none is closer.a 3×2 system, Householder QRperpendicularity is checked

The projection and the right angle

The least-squares solution is the one whose residual is perpendicular to everything the columns can reach. That is not a mnemonic — it is an equation, Aᵀr = 0, and the computed answer satisfies it to 10⁻¹⁶.

 10⁻⁸10⁻⁷10⁻⁶10⁻⁵10⁻⁴10⁻³10⁻²10⁻¹10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹10¹ε in Läuchli's matrix (smaller ε, larger κ)relative error in the coefficientsAᵀA exactly singularnormal equationsQRκ from 1.7·10⁸ to 17the cliff is at √u = 2.4·10⁻⁴

The road that squares the problem

The normal equations are the first method every course teaches and the method no library uses. Forming AᵀA squares the condition number, and below ε = √u it does not degrade — it produces a matrix that is exactly singular, from data that was perfectly usable.

 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.

 00.250.50.75110⁻¹110¹share of the noise placed in the matrixleast-squares error ÷ total least-squares errorequally accuratetotal leastsquares aheadordinary leastsquares aheadthe model, not the methodadvantage, all noise in b0.28advantage, all noise in A2.5seeds at each share40the same total noise at every pointand only where it sits changes

When the matrix is wrong too

Every least-squares problem here has assumed A is exact and b is not, and moved b onto the column space of A. Where both were measured, the smallest correction that makes the system consistent moves the matrix as well — and on the problems where that answer is more accurate, it has the larger residual, by construction rather than by luck.

 10¹10³10⁵10⁷10⁹10¹¹10¹³10¹⁵10⁻¹⁸10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³1κ₂(A), the matrix that was updatedrelative forward errorSherman–Morrisondirect solve of A + uvᵀone answer, two routesκ of the answer's matrix1κ of the matrix replaced10·10¹³update formula's error2.5·10⁻⁴direct solve's error1.1·10⁻¹⁶the question's condition number is 1at every point on this axis

A correction cheaper than the problem

Sherman and Morrison's formula updates a solved system for a rank-one change to the matrix, at 4n² operations instead of (2/3)n³. It is exact algebra. On a problem whose updated matrix is the identity — condition number one, the easiest system there is — it returns a forward error of 2.5·10⁻⁴ where a direct solve returns 10⁻¹⁶.

 110¹10²10³10⁴10⁵10⁶10⁷10⁻¹⁷10⁻¹⁶10⁻¹⁵10⁻¹⁴10⁻¹³10⁻¹²10⁻¹¹10⁻¹⁰10⁻⁹10⁻⁸1/(1 − h), the leverage of the removed row‖R̄ᵀR̄ − (G − aaᵀ)‖ / ‖G − aaᵀ‖downdatedrefactorisedat h = 1 − 10⁻⁷κ of the downdated matrix4.3κ of the matrix downdated9.3·10⁶rotation's amplification344downdate residual3.5·10⁻¹⁰a hyperbolic rotation is not orthogonaland that is exactly what it is for

The observation that cannot be removed

Removing a rank-one term from a Cholesky factor needs a rotation that is not orthogonal, and the number under its square root is 1 − h, where h is the leverage of the row being removed. The algorithm's breakdown condition and the statistician's warning are the same quantity, arrived at from opposite ends, and neither field states it in the other's language.

 0246810121410⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹10⁴10⁷10¹⁰log₁₀ τ — the weight on the constraintrelative error against the exact answerτ = 1/√uGram–Schmidtnormal equationsHouseholder QRthe ceiling is the method'sHouseholder, τ = 10¹⁴4.8·10⁻¹⁵normal equations14Gram–Schmidt4.9·10¹⁰1/√u6.7·10⁷a constraint is a weight at infinityand the solver decides how far infinity is

A constraint is a weight at infinity

Stack an equality constraint on top of a least-squares problem with a large weight and the answer approaches the constrained one like 1/τ². The limit is takeable to any accuracy — and how far it can be taken is a property of the solver, not of the problem. One of them stops at the square root of the precision, and one of them does not stop.

 the diagonal of the hat matrix, hᵢ = aᵢᵀ(AᵀA)⁻¹aᵢ · dashed: its average p/m = 0.200p/m10the leave-one-out residual: eᵢ/(1 − hᵢ), and forty refitsbars: closed form · dots: refitted without that pointone number, two fieldsΣ hᵢ, exactly p10largest leverage0.5closed form against refits8.9·10⁻¹³1 − h of the first row0.5y appears in the residualand nowhere in the leverage

Influence is decided before the data

The diagonal of the hat matrix sums to the number of columns and the response appears nowhere in it, so a fit has exactly p units of influence to hand out among m observations. The same row at h = 0.5 is a ten-fold outlier on one design and a boundary case on another, and which of those it is was settled before a single measurement was taken.

 the upper pair is distance from the truth; the lower pair is ‖Ax − b‖least squares · error0.08523total least squares · error0.037least squares · ‖Ax − b‖3.965total least squares · ‖Ax − b‖4.078two orderingserror ratio (ls ÷ tls)2.3residual ratio (tls ÷ ls)1seeds40no vector makes the residual smallernot even the one the problem was built from

The two numbers a caller has

Choosing between the two least-squares methods is a statement about where the noise is, and the two quantities a caller can compute are both blind to it. The residual separates the answers by 0.14 per cent where their accuracies differ by 14, and κ(A) falls from 3.54 to 2.46 across a sweep in which the error rises by a factor of sixty-two.

 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.

 1357911131510⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²1k, where h = 1 − 10⁻ᵏrelative error of 1 − h1 − ‖R⁻ᵀa‖²1 − ‖row of Q₁‖²‖row of Q₂‖²40 × 6k = 12, Cholesky route1.1·10⁻⁴k = 12, thin QR route4.4·10⁻⁴complement, worst k3·10⁻¹⁵one minus a sum of squaresor the sum of the other squares

One minus a leverage is a subtraction

Every deletion diagnostic divides by 1 − h, and computing it as one minus a computed leverage loses digits in proportion to 1/(1 − h), however accurate the leverage. The complementary block of a QR factor gives the same number as a sum of squares and loses κ(A)·u instead: every digit on a well-conditioned design, and half the digits the subtraction loses on a design whose far point is what made 1 − h small.

 -1012345612345678xyall 32without one twinwithout boththe pair at x = 6leverage of each0.44pair's joint share0.89deleted alone, mean0.62deleted together, mean3each twin covers for the otheronly removing both shows the shift

Two observations that hide each other

Two observations at the same place, wrong by the same amount, each look harmless when deleted alone, because a fit without one still has the other. Single deletion sees the shared error cut by (1 − 2h)/(1 − h) — measured at 261 times at the far end — and only the pair's two-by-two block of the hat matrix says what the two of them hold.

 10¹10³10⁵10⁷10⁹10¹¹10¹³10⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹κ(B), the conditioning of the constraint blockrelative error, and feasibilitydashes: the method of weightingthe saddle-point routethe null-space routealong the bottom: how nearly every answer satisfies the constraintsfeasible and wrongκ(B)4.6·10¹²κ(B)·u0.001null space1.2·10⁻⁴saddle point0.0082weighting2.6feasibility10⁻¹⁵every constraint is satisfiedand the answer has no digits

Feasible and wrong

A third constraint that nearly repeats the first takes the best route's answer from 2.96·10⁻¹⁵ to 1.16·10⁻⁴, and the other two routes to no correct digit at all. Every one of those answers satisfies every constraint to 10⁻¹⁵. The quantity a caller checks after a constrained solve is the one quantity here that says nothing.

 10³10⁶10⁹10¹²10⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹κ(A), identical for both problemsrelative error in the answerthe weak directions in the constraint's null spacethe weak directions in the constraint's own rowsone κ(A), two problemsκ(A), both10¹²κ left, constrained1κ left, free10¹²error, constrained4.7·10⁻¹⁶error, free3·10⁻⁴between them6.4·10¹¹a constraint is informationand κ(A) does not know it arrived

The condition number that does not know

Two constrained fits with the same size, the same number of constraints and the same κ(A) to twelve figures. One returns 4.7·10⁻¹⁶ and the other 3.0·10⁻⁴. What separates them is the conditioning of A restricted to the constraint's null space — 1.00 against 10¹² — which every solver computes on the way and none reports.

 10¹10³10⁵10⁷10⁹10¹¹10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³1κ(A), the conditioning of the fitrelative error in the answerthe saddle-point route, in floating pointdashes: forming AᵀA, then solving exactlythe method of weighting, τ = 10⁸the null-space routethe reference was a methodκ(A)10¹¹κ of what is left4.9·10⁶null space1.9·10⁻⁹saddle point4.6·10⁻⁴forming AᵀA alone3.4·10⁻⁴weighting3·10⁻⁹the damage is in the formingand not in the solving

The reference was a method

The optimality conditions of a constrained fit contain AᵀA, so solving them is the road that squares the problem wearing a block structure. At κ(A) = 10¹¹ the route that never forms a cross-product returns 1.89·10⁻⁹ and the route that does returns 4.64·10⁻⁴ — and forming AᵀA and then solving it in exact rationals returns 3.45·10⁻⁴, so nearly all of the loss happens before any elimination begins.

 1357911131510⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²1k, where h = 1 − 10⁻ᵏrelative error of 1 − hsubtractwith a correction stepcorrection kept as a pairfrom the reflectors40 × 6k = 12, subtracting1.1·10⁻⁴k = 12, with a correction1.1·10⁻⁴k = 12, from the reflectors3·10⁻¹⁵reflector operations900dashed: a unit of roundoff over the divisorthree routes sit on it and one does not

The factor a sparse code keeps anyway

Every deletion diagnostic divides by one minus a leverage, and computing it as a subtraction loses a digit for every decade the leverage is from one. The route that does not subtract needs the orthogonal factor, which a sparse factorisation is supposed not to have. Three repairs that avoid it all fail at exactly a unit of roundoff over the divisor — and the fourth, which reaches the orthogonal factor through the Householder vectors a sparse code keeps in order to solve anything at all, returns the same bits as a stored factor in 900 operations.

 heavy row first1 − h at 4³⁰7.4·10⁻¹⁸κ(A) at 4³⁰3.1·10⁸complement's error2.1·10⁻¹⁶110³10⁶10⁹10¹²10¹⁵10¹⁸10⁻¹⁷10⁻¹⁵10⁻¹³10⁻¹¹10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹weight on the rowrelative error of 1 − h1 − ‖R⁻ᵀa‖²1 − ‖row of Q₁‖²‖row of Q₂‖²κ(A)·uthe rows are the same in every positiononly the order the factorisation meets them changes

The weight the factor met first

The route to one minus a leverage through the orthogonal factor was said to lose a digit for every decade of the condition number, whatever else it does. Put a weight on one row and it does not. With the heavy row first, the complement keeps every digit at κ(A) = 2.5·10⁹ while both subtractions return nothing. With the same row last it loses digits as the row's scale grows. And two heavy rows that leave κ(A) at 3.1 still lose six digits when the light rows come first. The law was about the order the factor met the rows, and the condition number had been standing in for it.

 heavy row firstresidual at 4³⁰-2.8·10⁻¹⁰complement's error9.1·10⁻¹⁶110³10⁶10⁹10¹²10¹⁵10¹⁸10⁻¹⁷10⁻¹⁵10⁻¹³10⁻¹¹10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹weight on the rowrelative error of its residualb − Axb − Ax, exactlyQ₂Q₂ᵀbu·wthe same rows, the same data, in every positionthe solution misfits the heavy row by its own rounding

The residual the solution cannot hold

Sorting a weighted fit's rows heaviest first gave every digit of one minus the heavy row's leverage back. It gives nothing back to the heavy row's residual, if that residual is computed the way every textbook computes it — as the datum minus the fitted value. The fitted value is a double, and a double cannot resolve a misfit smaller than its own last digit times the weight: at a weight of 4²⁴ the residual formed from the solution is wrong in its second digit in every order, and forming the subtraction exactly changes nothing. Taken from the same orthogonal factor as the divisor, the residual keeps fifteen digits, and so does Cook's distance at 3.4·10¹⁷.

 same κ(B), two right-hand sides‖λ‖ ÷ κ(B), asking0.0081‖λ‖ at κ(B) = 10⁶·⁷, consistent0.00410¹10³10⁵10⁷10⁹10¹¹10¹³10⁻³10⁻¹10¹10³10⁵10⁷10⁹10¹¹κ(B), the conditioning of the constraint block‖λ‖, the multipliers' sizethird constraint asksasks nothing∝ κ(B)the same B at every point, two values of d₃the multipliers read the right-hand side

A multiplier is a force

A third constraint nearly parallel to the first made the multipliers of a constrained fit rise in exact proportion to κ(B), which looked like the conditioning measured a second, dearer way. It was not. Give the third constraint a datum that asks for nothing new and, at the same κ(B) = 4.6·10¹², the multipliers are eighteen thousand times smaller; give it a strain δ and they are 0.0133 δ/ε², a force on a lever of length ε. What they measure is what the constraint asks. What they do not measure is the error of the best route, which sits at the same level whether the constraint asks for nothing or for a displacement of 3·10⁹.

 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.

 error at the largest strainas given4.6·10⁻⁴multipliers to the size of x3.3·10⁻⁸first-solve scale, never below one1.8·10⁻⁸null-space route1.8·10⁻⁸10⁻¹⁰10⁻⁹10⁻⁸10⁻⁷10⁻⁶10⁻⁵10⁻⁴10⁻³strain δ (left: none)relative error in x10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²noneas givenmultipliers to the size of xfirst-solve scale, never below onenull-space routethe loss was the multipliers' sizeand it scales away

The scale that only moved a pivot

Multiply the constraint rows of a saddle-point system until its multipliers are the size of its solution, and the extra error the route was blamed for — 4.6·10⁻⁴ against the null-space route's 1.8·10⁻⁸ — falls to 3.3·10⁻⁸. The prediction holds and its reason does not. A scale of ten does what a scale of 6·10⁵ does; hold the elimination's row order fixed and nine decades of scale move the error by less than a factor of five. What the scale changed was which row partial pivoting took at the second step, and taking the constraint rows first does the same job with no scale at all.

 predicted against measuredproblems49worst relative difference4.4·10⁻¹⁶1.522.533.5coupling, from one to ten to the minus twelveswitching scale11e-21e-41e-61e-81e-101e-12repeatedconsistentstrainedrings: predictedevery dot inside its ringone elimination tells the switch

The switch is read before the solve

Scaling the constraint rows of a saddle-point system rescued the route to a constrained least-squares fit by changing which row partial pivoting takes at the second step. The scale at which it changes can be read before anything is solved: scaling multiplies every constraint row's candidate by s and leaves every other row's alone, so one unscaled elimination, recording the two kinds of candidate at each step, gives the switch exactly — on all forty-nine problems, to within one part in 10¹⁵ of what bisection finds, decided at the second step everywhere but at a coupling of one. A scale just past it removes the catastrophe where there was one. It does not make the route as good as eliminating the constraints first: on four problems every scale tried is thirty to thirty-nine times worse, and they are the problems where the unscaled route was too.

 the same in every columnleast squares0.32total, weighted0.11total, c → 00.16total, c → ∞0.1710⁻⁴10⁻²110²10⁴00.050.10.150.20.250.30.35factor c the first column's units are changed byrelative error, medianreverse regressionrecorded unitsleast squarescolumn 1 exactweighted by the noisedots: plain total least squaresthe units choose the answer

A unit is a statement about the noise

Total least squares minimises one Frobenius norm over every column of [A b], so the unit a column is written in is a claim about how noisy it is. On a 60-row fit with two measured regressors, rewriting one column in units from 10⁻⁴ to 10⁴ times the recorded ones leaves ordinary least squares exactly where it was and moves total least squares by half again, continuously, between two estimators with their own names: the reverse regression of that column on the others, and the fit that treats it as exact. Its correction is split among the columns as the squares of the coefficients, which the units set and the noise never enters. Dividing each column by its noise level makes every unit give one answer, the best of five estimators on all three placements of the noise tried, and two replicate readings a column are enough to get most of the way there when the recorded units were badly wrong.

 -1-0.500.51-1-0.500.51log₁₀ weight on column 1, relative to column 2log₁₀ weight on bnoise equalnoise largest in column 1noise almost all in bdots: self-consistentsquares: the true noiseone cloud, three truthsthe data's own weights are the geometry's

The weights the fit chooses for itself

Total least squares needs each column's noise level, and the tempting shortcut is to read it off the fit: weight, fit, take each column's correction as its noise, reweight, repeat. The prediction was that this converges, to weights that depend on where it starts. It does not converge at all. Each step multiplies every weight by its own column's share of the smallest singular vector, the one self-consistent weighting is unstable — a departure from it doubles every step — and every run leaves for the edge in two to seven steps, landing on the reverse regression or on ordinary least squares by which side it started. The self-consistent weights are nearly the same whatever the noise is: they describe the fit's geometry, and only replicate readings describe the noise.

 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.

 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.

All essays