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§
- Rsvd
Options - Options of
rsvd()andrange_finder; the defaults follow R’srsvd(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ᵀ:Uism × k,Visn × k(not transposed: R’ssvdconvention),snonincreasing. - SvdStats
- Work counters of
rsvd()andcrate::svds().
Functions§
- apply_
new 🔒 Y ← A X(orAᵀ 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 ofA(for sketching, CUR, randomized PCA by the caller). The width islitself:RsvdOptions::oversampleis not added (it belongs torsvd()’sk + p). - rsvd
- Randomized SVD of rank
k.