Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Oversampling — where it appears

Drawing a few more random columns than the rank being sought, which is what makes a randomised factorisation reliable rather than merely likely.

Named by 2 essays across 2 fields — each of them below, with the objects they name alongside it.

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

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.

randomised · randomised 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 boundsRandomised SVDSingular valuesEckart–YoungFilter factorsIll posed problemLow-rank approximationOrthogonal projectionRandom projectionSingular value decompositionSketchingTruncated svd

All concepts