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.
- Svds
Options - Options of
svds(). Defaults are scipy’ssvdswhere 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_Gof 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(orAᵀ 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
ksingular triplets by Golub–Kahan–Lanczos bidiagonalization with thick restart — a Krylov engine of its own, not an eigensolver onAᵀ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).