Concept
Probabilistic bounds — where it appears
2 essays name this object, across one field. What follows is each of them, and the objects they name alongside it.
A bound that holds with probability
Every other guarantee on this site is deterministic. The randomised low-rank approximation offers one that holds with a probability, the seed changes the answer, and the honest figure is a band rather than a line.
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.
Named alongside it
The objects these essays reach for when they reach for this one.
Orthogonal projectionDimension reductionEckart–YoungJohnson–LindenstraussLow-rank approximationOrthogonalityOversamplingRandom projectionRandomised SVDSingular value decompositionSingular valuesSketching