Spectral decay — where it appears
Named by 2 essays across one field — each of them below, with the objects they name alongside it.
Randomisation does not create structure
On a matrix whose singular values are all equal, a rank-ten randomised approximation has error 1.0 — and so does the optimal deterministic one. Neither achieved anything, and only one of them is usually sold with the implication that it might.
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.
Named alongside it
The objects these essays reach for when they reach for this one.
CancellationGeneralised cross validationHutchinson's estimatorInfluence matrixLow-rank approximationMatrix-freeProbabilistic boundsRandom projectionRandomised SVDResidualSingular value decompositionSingular values