Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Sketching — where it appears

2 essays name this object, across one field. What follows is each of them, and the objects they name alongside it.
10²10².³10².⁵⁹⁹⁹⁹⁹⁹⁹⁹⁹⁹⁹⁹⁹⁹⁶10⁻¹10⁻⁰.⁵1rows in the sketchworst relative distortiondimension 64dimension 2565 seeds per point, band is best to worstthe dimension does not appear

The dimension does not appear

A random projection preserves the lengths of a set of vectors to within a distortion that depends on how many vectors there are and not on how many coordinates each one has. That is the fact the whole field rests on, and it is genuinely surprising.

randomised · sketching 04812162010⁻¹10⁻⁰.⁵1target rank k‖A − A_k‖₂published boundrandomisedσ_{k+1}, optimalhow far apart the three areworst seed spread1.1bound / median at k = 1211median / optimum at k = 12160×60, 6 seeds, oversampling p = 5band is best to worst

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.

randomised · randomised

Named alongside it

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

Dimension reductionJohnson–LindenstraussLow-rank approximationOrthogonal projectionOrthogonalityProbabilistic boundsRandom projectionRandomised SVDResidualSingular value decompositionSingular valuesSketch-and-solve

All concepts