Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Generalised cross validation — where it appears

A parameter-choice rule whose objective divides the residual by a trace over the fitted subspace, so at scale it contains an estimated quantity.

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

Also named here as influence matrix — the same set of essays touches all of them, so they are one junction rather than several.

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

Named alongside it

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

Influence matrixCancellationDiscrepancy principleGolub kahan bidiagonalisationHutchinson's estimatorHybrid regularisationIll posed problemMatrix-freeOracleParameter choiceProbabilistic boundsProjected problem

All concepts