xingo_statla/rsvd.rs
1//! # Chapter 12.4 — Randomized SVD (Halko, Martinsson & Tropp 2011)
2//!
3//! ## Purpose
4//! *What are the leading `k` singular triplets of a matrix I can only
5//! multiply by?* — when a stated *expected* error is enough. [`rsvd()`] spends
6//! `2(q + 1)` passes over `A` with a block of `l = k + p` columns, plus
7//! `O((m + n) l²)` dense work, and its error is governed by the tail of the
8//! spectrum beyond `k` (bound below). [`range_finder`] returns the
9//! orthonormal basis alone (sketching, CUR, randomized PCA by the caller).
10//! For an answer accurate to `ε σ_1` on every value, [`crate::svds()`].
11//!
12//! ## Notation
13//! `A ∈ T^{m×n}`, `σ_1 ≥ σ_2 ≥ …` its singular values; `k` the rank wanted,
14//! `p` the oversampling ([`RsvdOptions::oversample`]), `q` the power
15//! iterations ([`RsvdOptions::power_iters`]), `l = min(k + p, m, n)`; `Ω ∈
16//! T^{n×l}` the test matrix of Algorithm G (Chapter 12.1); `orth(Y)` the
17//! `Q` factor of Algorithm Q (Chapter 12.0.4: Householder, any rank).
18//!
19//! ## Algorithm S (randomized SVD; HMT §4–5)
20//! S1. \[Sketch.\] `l ← min(k + p, m, n)`; draw `Ω` column by column from the
21//! seed's stream (G5), in the distribution [`RsvdOptions::sketch`].
22//! S2. \[Range.\] `Y ← A Ω`; `Q ← orth(Y)` (`m × l`).
23//! S3. \[Power.\] Repeat `q` times: `Z ← orth(Aᵀ Q)`; `Q ← orth(A Z)` — the
24//! re-orthonormalization at every half step that HMT recommend against
25//! the loss of small singular directions in rounding. (Task L3.3 could
26//! not exhibit that loss with `q ≤ 6` on spectra down to `10⁻¹²σ_1`:
27//! without the half step the results agreed to `ε σ_1`; the step costs
28//! one `n × l` QR per iteration and is kept.)
29//! S4. \[Project.\] `Bᵀ ← Aᵀ Q` (`n × l`; `B = QᵀA`).
30//! S5. \[Small SVD.\] `Bᵀ = Q_b R` (Algorithm Q); `R = X Σ Yᵀ` by the
31//! one-sided Jacobi SVD (Algorithm J, Chapter 12.0.6). Then `B = Y Σ (Q_b
32//! X)ᵀ`.
33//! S6. \[Lift.\] `U ← Q Y`, `V ← Q_b X`, `s ← Σ`; keep the leading `k`.
34//!
35//! `range_finder(op, l, opts)` is S1–S3 with the width `l` given directly
36//! (the oversampling is not added: it returns `Q ∈ T^{m×l}`).
37//! After every application the output is checked for NaN/∞
38//! ([`StatlaError::NonFinite`] with `what = "operator output"`).
39//!
40//! **Expectation bound** (Gaussian `Ω`, `p ≥ 2`; HMT Thm. 10.6 and Cor.
41//! 10.10, cited from memory):
42//!
43//! ```text
44//! E‖A − QQᵀA‖ ≤ [ (1 + √(k/(p−1))) σ_{k+1}^{2q+1}
45//! + (e√(k+p)/p) (Σ_{j>k} σ_j^{2(2q+1)})^{1/2} ]^{1/(2q+1)}
46//! ```
47//!
48//! (for `q = 0` the familiar `(1 + √(k/(p−1)))σ_{k+1} + (e√(k+p)/p)(Σ_{j>k}
49//! σ_j²)^{1/2}`). The bound is on the *mean*: the pilot `s01` saw one
50//! Gaussian run at 0.99 of it, so the acceptance (L3.3) is on the mean over
51//! ≥ 40 seeds, for `q ∈ {0, 1, 2}`, never per run. With `U Σ Vᵀ` as above,
52//! `‖A − U Σ Vᵀ‖ = ‖A − QQᵀA‖` up to rounding, since `U Σ Vᵀ = Q B` exactly
53//! when `l = k`; for `l > k` truncation to `k` adds at most `σ_{k+1}(B) ≤
54//! σ_{k+1}`.
55//!
56//! ## Invariants
57//! (R1) `Q`, `U`, `V` have orthonormal columns (Algorithm Q, J2); `s` is
58//! nonincreasing and nonnegative (J1) — tested.
59//! (R2) *Determinism.* Same operator, `k`, options and seed ⇒ same bits on
60//! every platform (Algorithm G; fixed loop orders) — tested by running
61//! twice and by the frozen sequence of 12.1.
62//!
63//! ## References
64//! Halko, Martinsson & Tropp, "Finding structure with randomness:
65//! probabilistic algorithms for constructing approximate matrix
66//! decompositions", SIAM Review 53 (2011), §4.2–4.5, §5.1, §10 (theorem
67//! numbers cited from memory); R package `rsvd` (Erichson et al.) for the
68//! defaults `p = 10`, `q = 2` (from memory).
69
70use xingo_sparse::{DenseBlock, Real};
71
72use crate::error::op_err;
73use crate::jacobi::{JacobiOptions, jacobi_svd};
74use crate::operator::AdjointOperator;
75use crate::random::{Rng, Sketch};
76use crate::small::{check_finite, householder_qr};
77use crate::{MatMut, MatRef, StatlaError};
78
79/// Options of [`rsvd()`] and [`range_finder`]; the defaults follow R's
80/// `rsvd` (`p = 10`, `q = 2`; cited from memory) and HMT's advice to
81/// re-orthonormalize at every half step of the power scheme.
82#[derive(Clone, Copy, Debug, PartialEq)]
83pub struct RsvdOptions {
84 /// Oversampling `p` (default 10): the sketch has `l = k + p` columns
85 /// (capped at `min(m, n)`).
86 pub oversample: usize,
87 /// Power (subspace) iterations `q` (default 2).
88 pub power_iters: usize,
89 /// Distribution of `Ω` (default Gaussian).
90 pub sketch: Sketch,
91 /// Seed of Algorithm G (default 0: deterministic by default, unlike
92 /// scikit-learn's `random_state=None`).
93 pub seed: u64,
94}
95
96impl Default for RsvdOptions {
97 fn default() -> Self {
98 Self {
99 oversample: 10,
100 power_iters: 2,
101 sketch: Sketch::Gaussian,
102 seed: 0,
103 }
104 }
105}
106
107/// A truncated SVD `A ≈ U diag(s) Vᵀ`: `U` is `m × k`, `V` is `n × k` (not
108/// transposed: R's `svd` convention), `s` nonincreasing.
109#[derive(Clone, Debug)]
110#[non_exhaustive]
111pub struct Svd<T: Real = f64> {
112 /// Left singular vectors.
113 pub u: DenseBlock<T>,
114 /// Singular values, nonincreasing.
115 pub s: Vec<T>,
116 /// Right singular vectors.
117 pub v: DenseBlock<T>,
118 /// Counters.
119 pub stats: SvdStats,
120}
121
122/// Work counters of [`rsvd()`] and [`crate::svds()`].
123#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
124#[non_exhaustive]
125pub struct SvdStats {
126 /// Products with `A` (columns).
127 pub applies: usize,
128 /// Products with `Aᵀ` (columns).
129 pub applies_t: usize,
130 /// Restarts ([`crate::svds()`]; 0 for [`rsvd()`]).
131 pub restarts: usize,
132 /// Second Gram–Schmidt passes (DGKS) triggered ([`crate::svds()`]).
133 pub reorthogonalizations: usize,
134 /// Triplets converged ([`crate::svds()`]; `= k` unless `allow_partial`;
135 /// `k` for [`rsvd()`]).
136 pub converged: usize,
137}
138
139/// `Y ← A X` (or `Aᵀ X`) into a new block, checked for non-finite output.
140pub(crate) fn apply_new<T: Real, O: AdjointOperator<T> + ?Sized>(
141 op: &mut O,
142 x: &DenseBlock<T>,
143 transpose: bool,
144 stats: &mut SvdStats,
145) -> Result<DenseBlock<T>, StatlaError> {
146 let rows = if transpose { op.ncols() } else { op.nrows() };
147 let mut y = DenseBlock::zeros(rows, x.cols);
148 {
149 let xv = MatRef::from_block(x);
150 let yv = MatMut::from_block(&mut y);
151 if transpose {
152 op.apply_t_block(xv, yv).map_err(op_err)?;
153 stats.applies_t += x.cols;
154 } else {
155 op.apply_block(xv, yv).map_err(op_err)?;
156 stats.applies += x.cols;
157 }
158 }
159 check_finite("operator output", &y.data)?;
160 Ok(y)
161}
162
163/// Steps S1–S3 with width `l` (validated by the callers).
164fn range<T: Real, O: AdjointOperator<T> + ?Sized>(
165 op: &mut O,
166 l: usize,
167 opts: &RsvdOptions,
168 stats: &mut SvdStats,
169) -> Result<DenseBlock<T>, StatlaError> {
170 // S1.
171 let mut omega = DenseBlock::zeros(op.ncols(), l);
172 Rng::new(opts.seed).fill(opts.sketch, &mut omega.data);
173 // S2.
174 let (mut q, _) = householder_qr(apply_new(op, &omega, false, stats)?);
175 // S3.
176 for _ in 0..opts.power_iters {
177 let (z, _) = householder_qr(apply_new(op, &q, true, stats)?);
178 q = householder_qr(apply_new(op, &z, false, stats)?).0;
179 }
180 Ok(q)
181}
182
183/// Randomized SVD of rank `k`.
184///
185/// Algorithm S of Chapter 12.4: `l = min(k + p, m, n)` columns of a sketch
186/// from the seed's stream, `q` power iterations re-orthonormalized at
187/// every half step, and the SVD of the projection by Householder QR and
188/// one-sided Jacobi. **Guarantee** (Gaussian `Ω`, `p ≥ 2`): the expectation
189/// bound of HMT stated in the chapter; the acceptance of L3.3 tests the
190/// mean over 40 seeds against it.
191///
192/// # Errors
193/// [`StatlaError::InvalidArgument`] (`k = 0` or `k > min(m, n)`),
194/// [`StatlaError::Operator`], [`StatlaError::NonFinite`] (the operator
195/// returned NaN or ∞), and [`StatlaError::NoConvergence`] if the one-sided
196/// Jacobi SVD of the small projected matrix (Chapter 12.0.6) has not
197/// converged after its limit of sweeps — never observed in the tests;
198/// `converged` is then `0`.
199pub fn rsvd<T, O>(op: &mut O, k: usize, opts: &RsvdOptions) -> Result<Svd<T>, StatlaError>
200where
201 T: Real,
202 O: AdjointOperator<T> + ?Sized,
203{
204 let (m, n) = (op.nrows(), op.ncols());
205 if k == 0 || k > m.min(n) {
206 return Err(StatlaError::InvalidArgument {
207 what: "rsvd: k must satisfy 1 <= k <= min(m, n)",
208 });
209 }
210 let l = k.saturating_add(opts.oversample).min(m).min(n);
211 let mut stats = SvdStats::default();
212 let q = range(op, l, opts, &mut stats)?;
213 // S4.
214 let bt = apply_new(op, &q, true, &mut stats)?;
215 // S5.
216 let (qb, r) = householder_qr(bt);
217 let small = jacobi_svd(&r, &JacobiOptions::for_rows(l))?;
218 // S6: U = Q Y, V = Q_b X, leading k columns.
219 let mut u = DenseBlock::zeros(m, k);
220 let mut v = DenseBlock::zeros(n, k);
221 for c in 0..k {
222 for t in 0..l {
223 let (yc, xc) = (small.y.get(t, c), small.x.get(t, c));
224 for i in 0..m {
225 u.data[i + c * m] += q.data[i + t * m] * yc;
226 }
227 for i in 0..n {
228 v.data[i + c * n] += qb.data[i + t * n] * xc;
229 }
230 }
231 }
232 stats.converged = k;
233 Ok(Svd {
234 u,
235 s: small.s[..k].to_vec(),
236 v,
237 stats,
238 })
239}
240
241/// Steps S1–S3 only: an orthonormal `Q ∈ R^{m×l}` whose range
242/// approximates that of `A` (for sketching, CUR, randomized PCA by the
243/// caller). The width is `l` itself: [`RsvdOptions::oversample`] is not
244/// added (it belongs to [`rsvd()`]'s `k + p`).
245///
246/// # Errors
247/// As [`rsvd()`] (`l = 0` or `l > min(m, n)` is
248/// [`StatlaError::InvalidArgument`]).
249pub fn range_finder<T, O>(
250 op: &mut O,
251 l: usize,
252 opts: &RsvdOptions,
253) -> Result<DenseBlock<T>, StatlaError>
254where
255 T: Real,
256 O: AdjointOperator<T> + ?Sized,
257{
258 let (m, n) = (op.nrows(), op.ncols());
259 if l == 0 || l > m.min(n) {
260 return Err(StatlaError::InvalidArgument {
261 what: "range_finder: l must satisfy 1 <= l <= min(m, n)",
262 });
263 }
264 range(op, l, opts, &mut SvdStats::default())
265}