Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Random projection — where it appears

A multiplication by a random matrix that maps vectors into fewer dimensions while distorting their lengths by a bounded amount.

Named by 2 essays across 2 fields — each of them below, with 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 0481216202428321rank keptrelative errormedianthe answer movesspread at rank 81.8spread at rank 241best median error0.14widest where the method is worstand the bound does not say so

An answer that changes with the seed

A randomised rank-k solve is a truncation computed in a random subspace, and it reaches the same floor as the deterministic ones. What it does not do is return the same answer twice — a factor of 1.84 across four seeds at rank 8, and 1.02 at the rank where the method is best.

combination · randomised

Named alongside it

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

Probabilistic boundsSketchingDimension reductionFilter factorsIll posed problemJohnson–LindenstraussOrthogonal projectionOrthogonalityOversamplingRandomised SVDSingular valuesTruncated svd

All concepts