Numerical Linear Algebra
where the algebra stops being the arithmetic
Least squares, and the road not to take

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.
21 min read 14 figures Whose fault is itIdentical algebra, different arithmeticMeasured, not assertedTwo routes to a numberAssertions that reject

Worth reading first: A correction cheaper than the problem · The projection and the right angle · A factorisation with nothing to pivot for.

Adding a rank-one term to a Cholesky factor is easy and safe. A sequence of Givens rotations — orthogonal, each of them, and therefore each of them incapable of amplifying anything — takes R to the factor of RᵀR + xxᵀ in 2p² operations, and the result is as accurate as a fresh factorisation.

Removing one is a different problem, and the difference is not a matter of degree.

An orthogonal transformation preserves the Frobenius norm. Removing a term makes the matrix smaller. So no sequence of orthogonal transformations can perform a downdate, and the algorithm that does is built from rotations that are not orthogonal:

[ c  −s ]        with  c² − s² = 1   rather than   c² + s² = 1
[ −s  c ]

a hyperbolic rotation. It preserves a² − b² instead of a² + b², which is exactly what removing a term needs. And the property that made the orthogonal version safe — that ‖G‖ = 1, so nothing it touches can grow — is precisely the property it has given up. c and s are both unbounded.

Downdating a Cholesky factor against refactorising it, as the removed row's leverage approaches oneA rank-one term is removed from a 6×6 Gram matrix by hyperbolic rotations and, separately, by factorising the downdated matrix from scratch. The downdate's residual rises from 2.1·10⁻¹⁶ at h = 0.3 to 3.5·10⁻¹⁰ at h = 1 − 10⁻⁷, a slope of 1.04 against 1/(1 − h). The refactorisation is flat at 8.1·10⁻¹⁷, and the matrix both are producing has a condition number of 4.3 at every point on the axis — so the difficulty belongs to the route and not to the answer.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
Fig. 1 Downdating a Cholesky factor against factorising the downdated matrix from scratch, as the leverage of the removed row approaches one. The downdate’s residual has a slope of one against 1/(1 − h); the refactorisation is flat. Drag the number of columns.

The measurement

A 40×6 design matrix, with the leverage of its first row set rather than measured — the row is scaled until h takes a chosen value, so the axis is an input. The Gram matrix G = AᵀA is factorised; then aaᵀ is removed from it two ways.

h ‖R̄ᵀR̄ − (G − aaᵀ)‖ / ‖·‖, downdated refactorised κ(G − aaᵀ)
0.3 2.1·10⁻¹⁶ 1.2·10⁻¹⁶ 4.3
0.99 3.6·10⁻¹⁵ 1.6·10⁻¹⁶ 3.3
1 − 10⁻⁴ 8.0·10⁻¹³ 6.8·10⁻¹⁷ 4.0
1 − 10⁻⁷ 3.5·10⁻¹⁰ 1.8·10⁻¹⁶ 4.3

The fitted slope of the downdate against 1/(1 − h) is 1.04.

And the last column is the finding. The matrix being produced has a condition number of about four at every row of that table. It is not a hard matrix. A fresh factorisation of it is exact to rounding at every leverage. The difficulty belongs entirely to the route.

The growth factor of a 12×12 elimination, against the condition number of the matrixThree curves against κ. Cholesky's growth factor is exactly 1 at every condition number drawn — the elimination never produces an entry larger than the matrix already had. Partial pivoting on the same matrices reaches the same growth, and reaches it by making up to 9 row interchanges, each of which destroys the symmetry that was the reason to use a symmetric factorisation. The bound the general theory allows, 2^11 = 2048, is drawn above them both.10¹10³10⁵10⁷10⁹10¹¹110¹10²10³10⁴condition number of the matrixgrowth factorbound 2^11partial pivotingCholeskyno pivot to gain fromCholesky growth, every κ1Cholesky interchanges0partial pivoting, worst9the bound, 2^112048both eliminations reach the same growthand only one of them had to swap to get there
Fig. 2 The factorisation being downdated, whose own growth factor is exactly one. Nothing about the object being modified is fragile; what is fragile is the modification.

The number under the square root

The mechanism is one line of algebra and it is the reason this essay exists.

Downdating G by aaᵀ begins by solving Rᵀp = a. The first hyperbolic rotation’s coefficients are 1/√(1 − pᵀp), and

pᵀp  =  ‖R⁻ᵀa‖²  =  aᵀ(RᵀR)⁻¹a  =  aᵀ(AᵀA)⁻¹a  =  h

which is the leverage of the row a — the diagonal of the hat matrix H = A(AᵀA)⁻¹Aᵀ, a quantity every regression package computes and every regression textbook plots.

So the algorithm’s amplification factor is 1/√(1 − h), its breakdown condition is h ≥ 1, and both are the statistician’s warning written in a different alphabet. A leverage near one means this observation is the only thing determining some direction of the fit; the downdate says the same thing by having no real square root.

Neither field states it in the other’s language. Numerical analysis texts derive the downdate and observe that it fails when the result is not positive definite. Statistics texts define leverage, prove it sums to p, and warn about points near one. They are the same number and the two derivations never meet.

Leverage and the deleted residual for 40 observations of a 6-column fitThe upper panel is the diagonal of the hat matrix, one bar per observation, with the average p/m = 0.150 drawn through it; the leverages sum to 6.000000000, which is exactly the number of columns. The lower panel is the leave-one-out residual, computed in closed form as eᵢ/(1 − hᵢ) and, separately, by refitting the model 40 times without each observation; the two agree to 1.3·10⁻¹². The first observation carries a leverage of 0.5000 by construction, and 1 − h is the number a hyperbolic downdate takes the square root of.the diagonal of the hat matrix, hᵢ = aᵢᵀ(AᵀA)⁻¹aᵢaverage p/m = 0.15010the leave-one-out residual: eᵢ/(1 − hᵢ), and forty refitsbars: closed form · dots: refitted without that pointone number, two fieldsΣ hᵢ, exactly p6largest leverage0.5closed form against refits1.3·10⁻¹²1 − h of the first row0.5y appears in the residualand nowhere in the leverage
Fig. 3 The leverages of forty observations and the deleted residuals they divide. The bars sum to exactly six, which is the number of columns; the first row’s leverage is set by construction.

The statistic that is the same downdate

Leave-one-out cross-validation asks: refit without observation i, and how badly does the fit predict it? Doing that honestly is m refits. The closed form everybody uses instead is

e₍ᵢ₎  =  eᵢ / (1 − hᵢ)

— one division per observation, and it is a rank-one downdate written as arithmetic. Every package that reports a studentised or deleted residual is running this.

It agrees with refitting. Measured against forty actual refits on a forty-observation problem, the worst relative disagreement is 1.3·10⁻¹². That agreement is what licenses the shortcut, and it is worth having as a measurement rather than as a derivation, because the derivation is exact and the question is arithmetic.

And the divisor is 1 − h. At h = 0.999 the closed form multiplies the residual by a thousand, and the thousand is correct — that observation really does drag the fit onto itself, and removing it really does move the prediction that far. What is not correct at that point is any digit past the fourth, because the numerator was computed against a fit that observation dominated.

How far the coefficients can move without changing the fit, degree 9Relative increase in the residual against relative change in the coefficients, along the least determined direction. The residual does not move measurably until the coefficients have changed by more than a factor of one.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
Fig. 4 Where a fit stops determining itself. A high-leverage point is the same phenomenon localised to one observation: along one direction the data has one vote.
The widest box a uniqueness proof is available forVerified half-width against the distance between two roots, both axes logarithmic. The measured widths are 0.05, 0.005, 5·10⁻⁴, 5·10⁻⁵ at separations of 0.1, 0.01, 0.001, 10⁻⁴ — a ratio of 0.5000 at every one of them. The operator verifies exactly up to the point where the box would reach the second root, and a box containing both is refused.10⁻⁴10⁻³10⁻²10⁻¹10⁻⁴10⁻³10⁻²10⁻¹distance between the two rootswidest verified half-widththe separationverified widthuniqueness is a claim about a regionwidth ÷ separation at δ = 0.10.5width ÷ separation at δ = 0.010.5width ÷ separation at δ = 0.0010.5verified up to the second rootand refused past it
Fig. 5 And the width of the answers a fit is consistent with. Removing the observation that was holding a direction down widens this, which is what the divisor is reporting.

Why the closed form is everywhere and the downdate is not

There is an asymmetry between the two halves of this essay worth accounting for. The leave-one-out formula is in every statistics package; the hyperbolic downdate is in LINPACK, in a handful of signal processing libraries, and almost nowhere else.

The reason is that the two are doing different amounts of work. eᵢ/(1 − hᵢ) produces one number — what the fit would have predicted at observation i without it — and needs the leverages, which cost one triangular solve each and are usually wanted anyway. The downdate produces a whole factor, which is what a caller needs when the reduced problem is going to be solved again: a sliding window, a recursive least squares with a forgetting factor, an active-set method releasing a constraint.

So the closed form is the cheap special case of the general operation, and it is the one that has a denominator a user can look at. The downdate has the same denominator buried inside a square root inside a loop, where nothing reports it.

That is worth naming as a general habit rather than a fact about these two routines. A shortcut whose dangerous quantity appears in the output is safer than one whose dangerous quantity appears in an intermediate, even when the arithmetic is identical — because a caller can see the first and cannot see the second. eᵢ/(1 − hᵢ) at h = 0.999 announces itself by returning a residual a thousand times the others. A downdate at h = 0.999 returns a factor that looks like every other factor.

What the solver reported, and what it achievedFinal relative residual and final relative error against the working precision, on a logarithmic vertical axis. The residual sits at the stopping tolerance at every precision — the method converged, by every test available to it. The error runs from 4.91·10⁻¹³ at 53 bits to 0.00501 at 8, tracking the unit roundoff, which is drawn beside it.614223038465410⁻¹³10⁻¹⁰10⁻⁷10⁻⁴working significand bitsrelative sizeerrorresidualuthe gap the solver cannot seeerror ÷ residual at 24 bits2.3·10⁵error ÷ residual at 16 bits5.2·10⁷error ÷ residual at 8 bits3.9·10¹⁰every convergence test passesand the answer is wrong in proportion to u
Fig. 6 The general shape of that habit. A quantity that would have warned you, computed and discarded, is the most expensive kind of intermediate there is.

The three quantities that agree, and one that does not

Three routes to h, sharing no arithmetic:

The triangular solve. ‖R⁻ᵀa‖², from a forward substitution against the Cholesky factor. The inverse. aᵀG⁻¹a, forming G⁻¹ explicitly — one of the legitimate uses of an inverse, since the entries are the answer. The hat matrix. The (i, i) entry of A(AᵀA)⁻¹Aᵀ, from the projection itself.

They agree to 10⁻⁸ at every leverage tested, which is the site’s two routes habit applied to a quantity that has three.

And one that does not agree, which is the sum rule: Σhᵢ = p, exactly. Not approximately — the trace of a projection onto a p-dimensional subspace is p, and the measurement returns 5.999999999999998 for a six-column fit. Adding a column adds exactly one unit of leverage to be shared out, whatever the data looks like, so the average leverage is p/m and depends on nothing.

That last fact is worth pausing on because it says what leverage is. The response y does not appear in it anywhere. Leverage is a property of the design — of where the observations were taken — and not of what was measured there.

The least-squares solution as a projection, with the right angle measuredThe column space drawn edge-on as a plane, the data vector above it, and the perpendicular dropped to the plane, with the residual marked at a right angle to it.everything Ax can reachb = (1.1, 0.4, 1.5)Ax, the closest reachable 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
Fig. 7 The projection whose diagonal this is. h is how much of observation i’s own value the fitted value at i is made of, which is why h = 1 means the fit passes through that point exactly.
Fitting the same degree-11 polynomial in two basesOn the left, the data and two fitted curves that lie on top of each other. On the right, the condition numbers of the two design matrices, ten orders of magnitude apart.00.10.20.30.40.50.60.70.80.910.20.40.60.81xyboth fits, drawn on top of one anothercondition number of the design matrixmonomial1.2·10⁸Chebyshev2.5largest fitted coefficientmonomial113Chebyshev0.51rms residual: 3.9·10⁻⁶ and 2.9·10⁻⁷ — the data is fitted either way.30 points, degree 11, single precisionthe basis is part of the problem
Fig. 8 And what the design’s conditioning does to the same object. A high-leverage row is one the design has no other information about, which is a statement about the columns rather than about the values.

When the downdate simply fails

Past a leverage the arithmetic can distinguish from one, a step’s discriminant a² − b² comes out negative and the algorithm stops. That is the honest outcome and it is worth separating into two cases.

h > 1 genuinely. Impossible: leverage is a projection diagonal and lies in [0, 1]. So a negative discriminant is never a correct report of an impossible downdate for a Gram matrix.

h < 1 but not distinguishably. At h = 1 − 10⁻¹⁶ the stored value of 1 − h is a rounding error, and the algorithm refuses a downdate that is mathematically fine. The result it refuses to produce is, once again, a well-conditioned matrix a fresh factorisation would return without complaint.

A refusal is much better than a wrong answer, and it is the behaviour a caller can act on. What it is not is a statement about the problem, and the temptation to read it as one — this downdate is ill-posed — is exactly the misattribution this site exists to separate.

Past the cliff: what each method returnsLoss of orthogonality at four condition numbers past κ²u = 1. Cholesky QR returns a factor whose implied Q is 0.37 away from orthogonal at κ = 10⁸ and 1.49 at 10¹² — and at 3·10¹⁰ it refuses outright, on a pivot of -6.5·10⁻¹⁷. The sweep and the tree return a usable factorisation of every one of these matrices.‖QᵀQ − I‖ of the implied Qκ = 10⁸, Cholesky0.37κ = 10⁸, sweep8.5·10⁻⁹κ = 10¹⁰, Cholesky1.3κ = 10¹⁰, sweep3·10⁻⁷κ = 3·10¹⁰, Choleskyrefusedκ = 3·10¹⁰, sweep6.7·10⁻⁶κ = 10¹², Cholesky1.5κ = 10¹², sweep1.4·10⁻⁴the safe run is the one that failsrefusals in the range1wholly non-orthogonal returns2the pivot it refused on-6.5·10⁻¹⁷one of these outcomes is safeand it is the refusal
Fig. 9 The site’s standing picture of a method that refuses against one that answers anyway. A downdate that stops is in the left half of this; the danger is the range just before it, where it answers.
How often Cholesky still calls a 12×12 matrix positive definite, against λ_min/λ_max in units of the format's own roundoffThree curves, one per precision, of the share of 24 seeded matrices on which the factorisation succeeds. Measured in units of each format's unit roundoff the three lie almost on top of one another, with the edge — the smallest ratio at which every seed succeeds — at 1.0, 1.0, 1.8 times u. The absolute thresholds are 6·10⁻⁸, 2.3·10⁻¹⁰ and 2·10⁻¹⁶: nine orders of magnitude apart, and the same number in the format's own units.10⁻³10⁻²10⁻¹110¹10²10³10⁴00.250.50.751λ_min / λ_max, in units of the format's own ushare of seeds that succeed24 bits32 bits53 bitsone threshold, three formats24-bit edge, absolute6·10⁻⁸32-bit edge, absolute2.3·10⁻¹⁰53-bit edge, absolute2·10⁻¹⁶in units of u, at 53 bits1.8a yes-or-no question with a precision in itand a coin flip three decades below the edge
Fig. 10 And the edge at which definiteness stops being a property a computation can see. A downdate near h = 1 is asking that question about a matrix it is in the middle of producing.

What to do instead, and what it costs

The alternative is a refactorisation, and the cost is worth being exact about because it is smaller than it looks.

Downdating a p×p factor is 2p² operations. Refactorising G − aaᵀ from the Gram matrix is p³/3 — at p = 6 that is 72 against 72, which is to say nothing at all. The saving only becomes real when the Gram matrix itself has to be reassembled from a large A, at mp² operations, and that is a saving of a factor of m rather than of p.

So for a small model on a large dataset — the usual case in a sliding-window or leave-one-out setting — the downdate is worth having, and it is worth having with a guard: compute the leverage first. It costs one triangular solve, it is a number worth looking at for its own sake, and it decides whether the shortcut is safe before the shortcut is taken.

Where the leverage is high, the honest options are to refactorise, or to notice that the answer being asked for is a fit with one direction supported by a single observation, and that the numerical question is the smaller of the two problems.

Downdating a Cholesky factor against refactorising it, as the removed row's leverage approaches oneA rank-one term is removed from a 10×10 Gram matrix by hyperbolic rotations and, separately, by factorising the downdated matrix from scratch. The downdate's residual rises from 1.7·10⁻¹⁶ at h = 0.3 to 6·10⁻¹⁰ at h = 1 − 10⁻⁷, a slope of 0.96 against 1/(1 − h). The refactorisation is flat at 1.3·10⁻¹⁶, and the matrix both are producing has a condition number of 6.7 at every point on the axis — so the difficulty belongs to the route and not to the answer.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 matrix6.7κ of the matrix downdated3.5·10⁷rotation's amplification377downdate residual6·10⁻¹⁰a hyperbolic rotation is not orthogonaland that is exactly what it is for
Fig. 11 The same measurement with ten columns rather than six. The slope does not move: it is a statement about 1/(1 − h) and not about the size of the model.
Implied orthogonality of four factorisations of a 256×6 matrixFour curves against the condition number, both axes logarithmic. Cholesky QR's implied orthogonality has a fitted slope of 1.96 and reaches 0.169; the same routine run twice has a slope of 0.79 and reaches 2.32·10⁻¹⁰, which is where the Householder sweep and the reduction tree are.10²10³10⁴10⁵10⁶10⁷10⁸10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²condition number‖QᵀQ − I‖one passsweeptwicetreewhat the second pass removesfitted slope, one pass2fitted slope, two passes0.79rounds, two passes6rounds, the sweep18one pass squares the condition numberand two do not
Fig. 12 And the general remedy for an orthogonalisation that has lost something — doing it again. It works where the loss is orthogonality and does not work here, because a hyperbolic sweep has nothing to re-orthogonalise against.

The mechanism, twice

This is the second algorithm in two essays whose error is governed by the object it routed through rather than by the problem it answers, and the two share no arithmetic.

Sherman–Morrison’s four quantities are solves against A, so its error is κ(A)u while the answer’s condition number is one. A hyperbolic downdate’s rotations are built from R, so its error is proportional to 1/(1 − h) — a property of the original Gram matrix and the row being removed — while the matrix it produces has a condition number of four.

One formula, one sweep of rotations; one governed by a condition number, one by a leverage. The general statement is the phase’s second finding: where a method reaches its answer through an intermediate, the intermediate’s conditioning is what it charges, and the answer’s conditioning is what a reader checks.

Sherman–Morrison against a direct solve, on 20×20 systems whose answer is the identityA is QΛQᵀ with Λ = (1, …, 1, ε) and the rank-one update takes ε back to 1, so A + uvᵀ is the identity and κ of the problem being solved is 1.000000 at every point on the axis. A direct solve returns 1.1·10⁻¹⁶. The update formula, which is exact algebra, returns 2.5·10⁻⁴ — a slope of 1.00 against κ(A), the matrix that was replaced. Its arithmetic is three solves against that matrix and there is nowhere else the error could have come from.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
Fig. 13 The other instance, from the previous essay: an update formula whose forward error tracks the condition number of the matrix it replaced, on a problem whose answer is the identity.

The sliding window, which is a downdate at every step

The setting where downdating is not an occasional operation but the whole algorithm is recursive least squares, and it is worth describing because it turns the leverage question from a diagnostic into a design parameter.

A recursive least-squares filter maintains a fit over the most recent w observations. At each step one row arrives and one leaves: an update and a downdate, both rank one, both at 2p² operations against a refactorisation’s mp². For a filter running at kilohertz over a model of six parameters, that is the difference between running and not.

The exponentially weighted variant is the same thing done continuously. Instead of dropping a row, every existing row is multiplied by √λ with λ slightly below one — a forgetting factor — so the influence of old data decays geometrically. Written as a factorisation update it is R ← √λ R followed by an ordinary Givens update for the new row, and there is no downdate in it at all. The hyperbolic rotations are gone, the algorithm is orthogonal throughout, and the whole of this essay’s difficulty disappears.

What it costs is that the window is soft. The effective number of observations is 1/(1 − λ), which is a statement about a geometric weighting rather than a count, and a filter that must forget an exact number of samples cannot use it. So the choice between a sliding window and a forgetting factor is a choice between a hard boundary computed unstably and a soft one computed stably — which is a modelling decision being made by a numerical constraint, and worth recognising as one.

And the leverage is the design parameter. In a sliding window the row about to leave has a leverage determined by how much of the fit it was holding up, and a window short enough that individual rows carry high leverage is a window in which the downdate is unstable and the fit is dominated by individual observations. Those are the same statement. A filter whose downdate is in trouble is a filter whose window is too short for its model, and the numerical diagnostic and the statistical one agree because they are the same number.

Fitting the same degree-11 polynomial in two basesOn the left, the data and two fitted curves that lie on top of each other. On the right, the condition numbers of the two design matrices, ten orders of magnitude apart.00.10.20.30.40.50.60.70.80.910.20.40.60.81xyboth fits, drawn on top of one anothercondition number of the design matrixmonomial1.2·10⁸Chebyshev2.5largest fitted coefficientmonomial113Chebyshev0.51rms residual: 3.9·10⁻⁶ and 2.9·10⁻⁷ — the data is fitted either way.30 points, degree 11, single precisionthe basis is part of the problem
Fig. 14 What the design does to the fit, which is what a window length is choosing. A window too short for the model is a design matrix whose columns are nearly dependent.

What is worth carrying

An orthogonal sweep cannot make a matrix smaller, and the sweep that can has no bound on its coefficients. That is not an accident of one algorithm; it is what removing a term costs, and every downdating method pays it in some form.

The breakdown condition is the leverage, exactly, which means the diagnostic already exists and is already plotted in a different field. Compute h before downdating; it is one triangular solve and it is the number that decides.

A dangerous quantity in the output beats the same quantity in an intermediate. The leave-one-out formula divides by 1 − h where a reader can see it; the downdate takes its square root inside a loop where nobody does. Same number, same danger, and only one of them announces itself.

And a leverage near one is not ill-conditioning of the answer. The downdated matrix has a condition number of four at every leverage measured here. What a high leverage says is that one observation was holding a direction of the fit up, which is a statement about the design and a much more interesting one than a numerical warning.

The next essay leaves updates behind and asks a question the phase has been circling: what is a function of a matrix, and is the definition a method? A function of a matrix is not a function of its entries.

Where this goes next

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⁻¹⁶. everything Ax can reachb = (1.1, 0.4, 1.5)Ax, the closest reachable 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⁻¹⁶. the mirrorx, length 4.000Hx = (-4.000, 0)v = x − αe₁safe sign: α = −‖x‖, so v is formed from a sum and nothing cancelsunsafe sign: α = +‖x‖ gives ‖v‖ only 35.1% of ‖x‖ + ‖x‖ — the digits go‖HᵀH − I‖5·10⁻¹⁶‖Hx‖ − ‖x‖8.9·10⁻¹⁶second component2.2·10⁻¹⁶built from a unit vectororthogonality is structural A reflection cannot stop being one Householder QR holds orthogonality at 10⁻¹⁵ whatever the condition number of the matrix, and Gram–Schmidt does not. The reason is not that it is more careful. It is that its Q is built from unit vectors, and rounding a unit vector gives a different reflection rather than a broken one.

What links here

Computed from the collection, not written here: the essays that point at this one.

Shares its objects with

Essays that name at least two of the same things, and that neither author linked.

Named objects

A flat tag is an object no other essay names yet.

CholeskyCondition numberGivens rotationLeast squaresLeverageLow-rank updateMatrix inverseOrthogonality