Module randomized 

Randomized SVD: range finding by random projection.

Two sketching strategies, both built on the same reduction:

• Sketch::PowerIteration — Halko, Martinsson & Tropp. Cheap and accurate when the spectrum decays quickly.
• Sketch::BlockKrylov — Musco & Musco. Keeps every power-iteration block instead of only the last, which is markedly more accurate on slowly-decaying spectra at the cost of a wider basis.

The final factorization is l × l, not l × cols

Once a range basis Y (rows × l) is in hand, the naive next step is to form B = Yᵀ·A (l × cols) and take its dense SVD. cols can be large, so 1.x’s b.svd(true, true) was a dense factorization of a potentially huge matrix.

Instead note that Bᵀ = Aᵀ·Y is itself tall and skinny (cols × l). Factor it with tsqr as Bᵀ = Q_c·R_c, then the only dense SVD needed is of R_cᵀ, which is l × l:

A ≈ Y·Bᵀᵀ = Y·R_cᵀ·Q_cᵀ = (Y·Û)·Ŝ·(Q_c·V̂)ᵀ

With rank 50 and 10 oversamples that is a 60 × 60 factorization regardless of how wide the input is.

Structs

RandomizedConfig

Configuration for svd_with.

Enums

Normalizer

How the intermediate basis is re-orthogonalised between products.

Sketch

The sketching strategy.

Constants

DEFAULT_OVERSAMPLES

Default oversampling beyond the requested rank.

DEFAULT_POWER_ITERATIONS

Default power iterations.

Functions

svd

rank largest singular triplets with default settings.

svd_block_krylov

Block-Krylov variant with blocks blocks.

svd_centered

PCA: rank largest triplets of the implicitly mean-centered matrix.

svd_seed

rank largest singular triplets with a fixed seed.

svd_with

Compute a decomposition with explicit configuration.

Type Aliases

Progress

A sink for progress messages, called once per major stage.