Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Leverage — where it appears

The diagonal of the hat matrix, aᵀ(AᵀA)⁻¹a, which is how much of an observation's own value its fitted value is made of. It says how much of an observation's fitted value is its own value, and an observation with leverage one cannot be removed from a fit at all.

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

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⁻¹⁶.

leastsquares · Low-rank update 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.

leastsquares · Low-rank update 10²10³10⁴10⁻¹⁷10⁻¹⁶10⁻¹⁵10⁻¹⁴10⁻¹³10⁻¹²steps taken‖RᵀR − AᵀA‖ ⁄ ‖AᵀA‖the bound, linear in the steps√k · uevery step safe, the chain notdrift after the run3.9·10⁻¹⁴the bound there3.3·10⁻¹³√k · u there6.1·10⁻¹⁵worst single amplification2.7worst leverage met0.69refreshes1backward stable onceand three thousand times is a different claim

Stable once, and three thousand times

A sliding window adds a row and removes one at every step and never looks at the data again. No single step of it amplifies by more than 2.72, no downdate fails, and after three thousand steps the triangular factor in memory is 3.9·10⁻¹⁴ from the matrix it is supposed to be a factor of — six hundred times growth from a per-step bound that says nothing about chains.

sequence · Sequence stability 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.

leastsquares · Leverage 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.

leastsquares · Leverage -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.

leastsquares · Leverage 111315171921232510⁻¹110¹sketch width l, for rank 10‖(I − QQᵀ)A‖ ÷ σ₁₁GaussianHadamardone nonzero a rowthree nonzeros a rowcoherent, geometric 0.8, width 20, twenty seedsGaussian: median 0.41, worst0.78Hadamard: median 0.37, worst0.94one nonzero a row: median 3.3, worst7.1three nonzeros a row: median 0.41, worst0.99solid: median · dashed: worst of twentybelow one: better than the best rank-10 error

A sketch that finds the columns it can see

A sparse sketch with one nonzero in each row is twenty times cheaper to apply than a Gaussian one, and on a matrix whose important directions are spread across its columns it finds the same range: a median error of 0.45 against 0.43. Put the same ten directions into ten particular columns and it is eight times worse — 3.33 against 0.41, with a worst draw of 7.1 — because two important columns hashed to one bucket are one direction. Three nonzeros a row repair it at a sixth of the Gaussian's cost, and a randomised Hadamard transform never had the problem.

randomised · Randomised 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.

leastsquares · Leverage 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.

leastsquares · Leverage 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¹⁷.

leastsquares · Leverage median ratioone nonzero, t = 03.5one nonzero, t = 0.011.210⁻⁴10⁻³10⁻²10⁻¹11mixture t (t = 0 at the left edge)error ÷ σ₁₁one nonzero a rowheavy columns reservedthree nonzeros a rowGaussianthe left edge is exact coherencethe failure fades over four decades of mixing

The leverage that did not move

A one-nonzero sketch fails on a matrix whose leading directions sit on ten particular columns, and coherence — the largest column leverage — is the statistic that names the failure. Turn the directions away from their columns by a hundredth of a radian and the sketch's median error falls from 3.47 to 1.23 times σ₁₁ while the coherence stays at 6.40 to three figures. Giving the heaviest columns buckets of their own repairs the rest, but only when it reserves more buckets than the rank: ten reserved leave 1.16, sixteen reach 0.36, below the Gaussian's 0.41.

randomised · Randomised 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.

leastsquares · Fitting fraction left after a decademedian, t = 10⁻³ → 10⁻²0.57median, t = 10⁻² → 10⁻¹0.6210⁻⁷10⁻⁶10⁻⁵10⁻⁴10⁻³10⁻²10⁻¹1110¹mixing angle terror ÷ σ₁₁median of 80single drawseach draw drops once, somewherethe median's slope is where they drop

A fade made of drops

A one-nonzero sketch's median error fell by about forty per cent for every factor of ten in how far a coherent matrix had been mixed toward an incoherent one, and nothing explained the rate. Followed one draw at a time, no draw fades at that rate. Each holds its coherent error — as large as the singular value of the direction its hash lost — and then drops, within one to three decades of mixing, never faster than one decade of error per decade of mixing. The median's steady slope is where the drops happen to fall. Change the spectrum and they fall elsewhere: at a decay of 0.9 there is no slope, only a cliff.

randomised · Randomised

Named alongside it

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

Condition numberLeast-squaresResidualCatastrophic cancellationHouseholder reflectionNormal equationsQR factorisationUnit roundoffExact ground truthFlop countLow-rank updateRandom projection

All concepts