Skip to main content

Module rsvd

Module rsvd 

Source
Expand description

§Chapter 12.4 — Randomized SVD (Halko, Martinsson & Tropp 2011)

§Purpose

What are the leading k singular triplets of a matrix I can only multiply by? — when a stated expected error is enough. rsvd() spends 2(q + 1) passes over A with a block of l = k + p columns, plus O((m + n) l²) dense work, and its error is governed by the tail of the spectrum beyond k (bound below). range_finder returns the orthonormal basis alone (sketching, CUR, randomized PCA by the caller). For an answer accurate to ε σ_1 on every value, crate::svds().

§Notation

A ∈ T^{m×n}, σ_1 ≥ σ_2 ≥ … its singular values; k the rank wanted, p the oversampling (RsvdOptions::oversample), q the power iterations (RsvdOptions::power_iters), l = min(k + p, m, n); Ω ∈ T^{n×l} the test matrix of Algorithm G (Chapter 12.1); orth(Y) the Q factor of Algorithm Q (Chapter 12.0.4: Householder, any rank).

§Algorithm S (randomized SVD; HMT §4–5)

S1. [Sketch.] l ← min(k + p, m, n); draw Ω column by column from the seed’s stream (G5), in the distribution RsvdOptions::sketch. S2. [Range.] Y ← A Ω; Q ← orth(Y) (m × l). S3. [Power.] Repeat q times: Z ← orth(Aᵀ Q); Q ← orth(A Z) — the re-orthonormalization at every half step that HMT recommend against the loss of small singular directions in rounding. (Task L3.3 could not exhibit that loss with q ≤ 6 on spectra down to 10⁻¹²σ_1: without the half step the results agreed to ε σ_1; the step costs one n × l QR per iteration and is kept.) S4. [Project.] Bᵀ ← Aᵀ Q (n × l; B = QᵀA). S5. [Small SVD.] Bᵀ = Q_b R (Algorithm Q); R = X Σ Yᵀ by the one-sided Jacobi SVD (Algorithm J, Chapter 12.0.6). Then B = Y Σ (Q_b X)ᵀ. S6. [Lift.] U ← Q Y, V ← Q_b X, s ← Σ; keep the leading k.

range_finder(op, l, opts) is S1–S3 with the width l given directly (the oversampling is not added: it returns Q ∈ T^{m×l}). After every application the output is checked for NaN/∞ (StatlaError::NonFinite with what = "operator output").

Expectation bound (Gaussian Ω, p ≥ 2; HMT Thm. 10.6 and Cor. 10.10, cited from memory):

E‖A − QQᵀA‖ ≤ [ (1 + √(k/(p−1))) σ_{k+1}^{2q+1}
              + (e√(k+p)/p) (Σ_{j>k} σ_j^{2(2q+1)})^{1/2} ]^{1/(2q+1)}

(for q = 0 the familiar (1 + √(k/(p−1)))σ_{k+1} + (e√(k+p)/p)(Σ_{j>k} σ_j²)^{1/2}). The bound is on the mean: the pilot s01 saw one Gaussian run at 0.99 of it, so the acceptance (L3.3) is on the mean over ≥ 40 seeds, for q ∈ {0, 1, 2}, never per run. With U Σ Vᵀ as above, ‖A − U Σ Vᵀ‖ = ‖A − QQᵀA‖ up to rounding, since U Σ Vᵀ = Q B exactly when l = k; for l > k truncation to k adds at most σ_{k+1}(B) ≤ σ_{k+1}.

§Invariants

(R1) Q, U, V have orthonormal columns (Algorithm Q, J2); s is nonincreasing and nonnegative (J1) — tested. (R2) Determinism. Same operator, k, options and seed ⇒ same bits on every platform (Algorithm G; fixed loop orders) — tested by running twice and by the frozen sequence of 12.1.

§References

Halko, Martinsson & Tropp, “Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions”, SIAM Review 53 (2011), §4.2–4.5, §5.1, §10 (theorem numbers cited from memory); R package rsvd (Erichson et al.) for the defaults p = 10, q = 2 (from memory).

Structs§

RsvdOptions
Options of rsvd() and range_finder; the defaults follow R’s rsvd (p = 10, q = 2; cited from memory) and HMT’s advice to re-orthonormalize at every half step of the power scheme.
Svd
A truncated SVD A ≈ U diag(s) Vᵀ: U is m × k, V is n × k (not transposed: R’s svd convention), s nonincreasing.
SvdStats
Work counters of rsvd() and crate::svds().

Functions§

apply_new 🔒
Y ← A X (or Aᵀ X) into a new block, checked for non-finite output.
range 🔒
Steps S1–S3 with width l (validated by the callers).
range_finder
Steps S1–S3 only: an orthonormal Q ∈ R^{m×l} whose range approximates that of A (for sketching, CUR, randomized PCA by the caller). The width is l itself: RsvdOptions::oversample is not added (it belongs to rsvd()’s k + p).
rsvd
Randomized SVD of rank k.