Concept
Randomised SVD — 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.
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.
Named alongside it
The objects these essays reach for when they reach for this one.
Low-rank approximationSingular value decompositionSingular valuesEckart–YoungOrthogonal projectionOversamplingProbabilistic boundsResidualSketch-and-solveSketchingSpectral decay