Numerical Linear Algebra
where the algebra stops being the arithmetic
Ladder

Randomised — the ladder

2 distinct arguments against one idea, from the one that introduces it to the one that assumes the rest.
  1. 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.

    rung 1 · randomised
  2. 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.

    rung 2 · randomised

All ladders