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 3 essays across 3 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

Named alongside it

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

Generalised cross-validationDiscrepancy principleIll-posed problemOracleParameter choiceCancellationGolub kahan bidiagonalisationHutchinson's estimatorHybrid regularisationL-curveMatrix-freeNoise floor

All concepts