Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Influence matrix — where it appears

The matrix mapping data to fitted values, whose trace is the effective number of parameters a regularisation has left and is rarely computable exactly. Its trace is the effective number of parameters a fit has used, and at scale it is estimated by random probes rather than computed.

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

1112131415193111.365129.731148.096166.461probes takenrunning estimate of the tracenormal±1one probe, no errorthe exact trace99±1 variance, this matrix0±1 variance, rotated57normal variance545the same spectrum in a general basiscosts the ±1 probe its whole advantage

Counting what cannot be looked at

The trace is n additions and one of the most expensive quantities in the subject to estimate, because the matrices whose trace is wanted are never stored. Hutchinson's estimator is unbiased with one line of algebra — and its variance depends on which random vector is used, by a factor that is a property of the matrix, and on a diagonal matrix one choice is exact from the first probe and the other is not.

randomised · Trace estimation 27121722273237424710⁻²10⁻¹110¹subspace size kvalueno answer below 8GCV's traceλ from GCVλ from the residuala denominator that is not the problem'strace at k = 41trace at k = 4827λ range across the run2.2subspace before an answer8the divisor moves by twenty-sevenand the answer does not move

A parameter chosen on a smaller problem

Inside a hybrid method the regularisation parameter is chosen on a 25×24 problem rather than a 64×64 one. The rule that reads a residual transfers exactly; the rule that reads a trace is biased by exactly two grid steps at twenty-four steps and one at forty, at every noise level from 10% to 0.1%.

combination · Parameter choice 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 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 square systemfloor minima21interior dips28four samples per unknownfloor minima0interior dips4051015202530samples per unknowndraws of 24011.251.524minimum at the floorinterior dipGCV over 10× the oracleover 100×horizontal axis doubles at each gridlinethe floor goes at once and the dip does not

More samples take the floor and leave the dip

GCV's catastrophic misses on fine grids were blamed on squareness: on an n × n system the residual and n − t both reach zero as λ does, and their ratio can dip there. With more samples than unknowns neither reaches zero, and the prediction was that the dip would be gone by construction. Half of it is. The minimum at the floor of the scale, 21 draws in 240 on square systems, is gone at every ratio. The interior dip is not — 28, 20, 13, 8 and 4 draws at one to four samples per unknown — and at four per unknown one draw still misses the oracle by 877 times.

regularisation · Regularisation 45 interior dipsρ at the dip, true noise, median0.84ρ at the dip, estimated, median0.980.50.7511.251.51.7520.50.7511.251.51.752ρ at the dip, true noiseρ̂ at the dip, estimated noisedashed: the estimate equal to the truththe estimate pins every dip at one

An estimate that shares the dip's luck

GCV's interior dips form where the residual per remaining degree of freedom is low, and the proposal was a guard that estimates the noise from the least-squares residual and refuses a minimum whose residual is implausibly small. Over 960 draws holding 45 dips it refuses none, and picks plain GCV's minimum on every draw. At the dip ρ is 0.84 with the true noise and 0.98 with the estimate, because the estimate is made from the residual at the dip's own end of the scale and inherits its luck. Told the true noise instead, the guard can refuse 14 dips only by refusing 78 real minima. Handed the same estimate, the discrepancy principle misses by 570,000 times.

regularisation · Regularisation

Named alongside it

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

Generalised cross-validationDiscrepancy principleParameter choiceTikhonov regularisationDiscretisationIll-posed problemLeast squaresOracleRegularisationCancellationCatastrophic cancellationDeconvolution

All concepts