Skip to main content

Module svds

Module svds 

Source
Expand description

§Chapter 12.5 — Truncated SVD by Golub–Kahan–Lanczos bidiagonalization with thick restart

§Purpose

The leading k singular triplets of an operator, each value accurate to ε σ_1. svds() is a Krylov engine of its own (decision S2 of D-0127), not an eigensolver on AᵀA: it never squares the condition, so every singular value comes out with an absolute error of order ε σ_1 — where scipy’s ARPACK-on-the-normal-operator route gives ε σ_1²/σ_i.

§Notation

A ∈ T^{m×n}; P_j = [p_1 … p_j] ∈ T^{n×j}, U_j = [u_1 … u_j] ∈ T^{m×j} with orthonormal columns (right and left Lanczos vectors); B_j ∈ T^{j×j} upper triangular. After j steps

A  P_j = U_j B_j                                     (B-left)
Aᵀ U_j = P_j B_jᵀ + β_j p_{j+1} e_jᵀ,  p_{j+1} ⟂ P_j  (B-right)

Before the first restart B_j is upper bidiagonal (α_i on the diagonal, β_i above it). After a restart that kept k′ triplets it is diag(σ̃_1 … σ̃_{k′}) with a spike ρ in column k′ + 1, then bidiagonal again (the “arrowhead” of Baglama & Reichel). The spike follows from (B-right) of the kept triplets: Aᵀ ũ_i = σ̃_i p̃_i + ρ_i p_{ncv+1}, so U_{k′}ᵀ A p_{k′+1} = (Aᵀ U_{k′})ᵀ p_{k′+1} = ρ and the next left step is w = A p_{k′+1} − U_{k′} ρ. τ is the tolerance of step B5 (τ = ε_T when SvdsOptions::tol is 0), σ̃_1 the largest Ritz value. Locked triplets (n_L of them, always the first columns) have ρ_i = 0, so B is block diagonal: diag(σ̃_L) and the active block, which is all that Steps B4–B6 touch.

§Algorithm B (thick-restart Lanczos bidiagonalization)

B1. [Start.] p_1 ← v0/‖v0‖ (v0 from the options, or n Gaussian deviates of the seed’s stream, Algorithm G); j ← 0; k′ ← 0; n_L ← 0; σ̃_est ← 0. B2. [Left step.] j ← j + 1; w ← A p_j − Σ_{i<j} b_{ij} u_i (the recurrence: β_{j−1} u_{j−1}, or U_{k′} ρ right after a restart); reorthogonalize against all of U_{j−1} and take α_j ← ‖w‖, u_j ← w/α_j by Algorithm E of Chapter 12.0.7 with floor = ε_T σ̃_est (breakdown: α_j ← 0, u_j from the seed’s stream). b_jj ← α_j. B3. [Right step.] r ← Aᵀ u_j − α_j p_j; reorthogonalize against all of P_j, β_j, p_{j+1} by Algorithm E as in B2. b_{j,j+1} ← β_j (or β_ncv ← β_j when j = ncv). σ̃_est ← max(σ̃_est, √(α_j² + β_j²)). If j < ncv, go to B2. B4. [Ritz.] SVD of the active block B_act = X Σ̃ Yᵀ by one-sided Jacobi (Algorithm J, Chapter 12.0.6), values nonincreasing. Active Ritz triplets (σ̃_i, U_act X e_i, P_act Y e_i); by (B-left)/(B-right) A p̃_i = σ̃_i ũ_i and Aᵀ ũ_i − σ̃_i p̃_i = ρ_i p_{ncv+1}, ρ_i = β_ncv · e_lastᵀ X e_i. σ̃_1 ← the largest of the locked and active values. B5. [Test.] The wanted are the k largest among the locked and the active Ritz values (ties: locked first). Locked ones are converged; an active one when |ρ_i| ≤ τ σ̃_1 (absolute: a test relative to σ̃_i is unattainable for small σ_i and is not offered). If the k wanted are converged, go to B7. If the restart limit is reached, StatlaError::NoConvergence (or, with allow_partial, B7 with the converged ones). B6. [Thick restart.] Lock the converged wanted active triplets (appended to the locked block in value order; their ρ_i becomes 0, a perturbation of A of norm ≤ τ σ̃_1, and their vectors are never rotated again). Choose k′ by Algorithm K of Chapter 12.0.7 (n_conv = the converged wanted) and keep the k′ − n_L largest unlocked active triplets: P ← [P_L, P_act Y_kept, p_{ncv+1}], U ← [U_L, U_act X_kept], B ← diag(σ̃_L, σ̃_kept) with the spike (0, ρ_kept) in column k′ + 1. Count a restart; j ← k′; go to B2. B7. [Result.] The (converged) wanted, nonincreasing: locked ones as stored, active ones as U_act X e_i, P_act Y e_i.

Reorthogonalization policy: full and two-sided (B2 against U, B3 against P, locked vectors included); at most two Gram–Schmidt passes per step. Cost per step: two operator applications plus ≈ 4(m + n) j flops. One-sided (Simon & Zha) and partial (PROPACK, Larsen) reorthogonalization are candidates for a measured later version.

§Invariants

(G1) ‖P_jᵀP_j − I‖, ‖U_jᵀU_j − I‖ ≤ c_G · j · u — debug-asserted at every restart (with c_G = C_G); measured in the tests. (G2) ‖A P_j − U_j B_j‖ and ‖Aᵀ U_j − P_j B_jᵀ − β_j p_{j+1} e_jᵀ‖ ≤ c_G · j · u · σ̃_est after every expansion: computed by the unit tests (it costs 2j extra applications, so it is not a debug_assert!: the operator may count its calls). (G3) B is upper triangular: diagonal in the kept block, the spike in column k′ + 1, bidiagonal after it; locked rows are zero off the diagonal — by construction, debug-asserted. (G4) σ̃ nonincreasing (Algorithm J), nonnegative, finite — the operator output is checked for NaN/∞ after every application. (G5) A locked triplet is never modified again and its ρ_i is zero — by construction (Steps B4–B6 touch only the active block).

§Guarantee

For every returned triplet let r = (A v − σ̂ u; Aᵀ u − σ̂ v). The symmetric Jordan–Wielandt matrix M = [0 A; Aᵀ 0] has eigenvalues ±σ_j and |m − n| zeros, and w = (u; v)/√2 is a unit vector (to (G1)) with M w − σ̂ w = r/√2. By the residual bound for symmetric matrices (for unit w, min_λ |λ − σ̂| ≤ ‖Mw − σ̂w‖: expand w in the eigenvectors of M), some σ_j (or 0) satisfies |σ̂ − σ_j| ≤ ‖r‖/√2. The algorithm makes ‖r‖ ≤ (τ + c_G · ncv · u) σ̃_1: the first term is step B5 (|ρ_i| ≤ τ σ̃_1 is the right half of r in exact arithmetic, and the left half is zero), the second the rounding of the relations and the loss of orthogonality, bounded by (G1)–(G2) with a measured constant. Two limits: the index j is the i-th only if no copy of a multiple singular value was missed (a single-vector Krylov method can miss multiplicities: in exact arithmetic it sees one copy only), and the error is absolute — small singular values carry ε σ_1, not ε σ_i.

The constant c_G = C_G = 8 (measured in task L3.3, margin 3.5×): the largest recomputed (‖r‖/σ̂_1 − τ)/(ncv·u) over the acceptance cases was 2.3 in f64 (2000 × 200; ≤ 1.4 for m ≤ 300) and 0.05 in double-double; (G2) at most 0.85·ncv·u·σ̃_est; (G1) at most 1.1·ncv·u (l33-tables.md).

§Acceptance (L3.3, S9; as ratified, with the oracle used)

(i) every returned triplet: the recomputed ‖r‖ ≤ (τ + c_G·ncv·u) σ̂_1; (ii) |σ̂_i − σ_i| ≤ 10⁻¹³ σ_1 (f64) on matrices with prescribed spectra down to 10⁻¹⁴ σ_1, clusters included, where the gap to the neighbours is ≥ 10⁻⁸ σ_1 — the reference SVD is the construction itself, certified to u‖A‖_F by Weyl, and cross-checked against a one-sided Jacobi SVD in double-double (tests/svds.rs); (iii) against scipy.sparse.linalg.svds on Matrix Market matrices, 1e-10 relative on the σ_i ≥ 10⁻³σ_1 with gap ≥ 10⁻⁶σ_1 — moved to task L3.4 (D-0134), in CI on committed fixtures (tests/arpack.rs); (iv) DoubleDouble: (i) with u = 2⁻¹⁰⁵.

§References

Golub & Kahan, “Calculating the singular values and pseudo-inverse of a matrix”, SIAM J. Numer. Anal. 2 (1965); Baglama & Reichel, “Augmented implicitly restarted Lanczos bidiagonalization methods”, SISC 27 (2005) (the arrowhead after a thick restart; irlba); Wu & Simon, “Thick-restart Lanczos method for large symmetric eigenvalue problems”, SIMAX 22 (2000); Simon & Zha, SISC 21 (2000); Larsen, DAIMI PB-537 (1998); Daniel, Gragg, Kaufman & Stewart (1976); Parlett, The Symmetric Eigenvalue Problem (1998), Thm. 4.5.1 (the residual bound). Cited from memory.

Structs§

Cand 🔒
One candidate of step B5.
Diag 🔒
Diagnostics of a run (read by the unit tests).
Engine 🔒
The state of Algorithm B.
Params 🔒
The validated parameters of one run.
SvdsOptions
Options of svds(). Defaults are scipy’s svds where it has one (cited from memory), with ARPACK’s dimension rule.

Enums§

Slot 🔒
Where a candidate of step B5 lives.
SvdWhich
Which singular values svds() computes. v0.1 has only the largest; the smallest (harmonic Ritz or refined restarts, Baglama & Reichel; cited from memory) would be a new variant, hence #[non_exhaustive].

Constants§

C_G 🔒
The constant c_G of invariants (G1)–(G2) and of the guarantee ‖r‖ ≤ (τ + c_G·ncv·u)σ̂_1 (measured in task L3.3, with a margin).

Functions§

apply 🔒
y ← A x (or Aᵀ x) with the counters and the NaN check.
invalid 🔒
run 🔒
Algorithm B; with paranoid (unit tests) the largest (G2) residual is returned in the diagnostics.
svds
Leading k singular triplets by Golub–Kahan–Lanczos bidiagonalization with thick restart — a Krylov engine of its own, not an eigensolver on AᵀA (S2): it never squares the condition, so every singular value comes out with an absolute error of order ε σ_1.
validate 🔒
Check the arguments (in the order of the error conventions, 12.0.1).