Skip to main content

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}