Expand description
§Chapter 12.0.6 — One-sided Jacobi SVD of a small dense matrix
§Purpose
Both truncated SVDs end with the SVD of a small matrix: the l × l
triangle of step S5 of crate::rsvd() and the projected B of step B4
of crate::svds() (and eigsh/eigs of L3.4 will reuse the sorting
and completion conventions). DenseKernel has no SVD and the crate is
generic in T: Real (decision S1), so this is the classical one-sided
(Hestenes) Jacobi method: it needs only + − · /, sqrt and the order,
and it is backward stable column by column (Demmel & Veselić), which is
what the residual guarantees of 12.4 and 12.5 rest on.
§Notation
B ∈ T^{p×q}, p ≥ q; w_i the columns of the working copy W; Y ∈ T^{q×q} the accumulated rotations, so W = B Y throughout; at the end
w_i = σ_i x_i with ‖x_i‖ = 1, hence B Y = X Σ, B = X Σ Yᵀ. tol
and max_sweeps are the fields of JacobiOptions.
§Algorithm J
J1. [Scale.] μ ← max |b_ij|. If μ = 0: Σ = 0, Y = I, X the
first q columns of I_p; done. Otherwise W ← B/2^⌊log₂ μ⌋
(exact), so the squares below neither overflow nor underflow.
J2. [Sweep.] First set to zero every column whose ‖w_i‖² underflows
to 0 (its norm is below 2⁻⁵³⁷ while max |w_ij| ≥ 1: far below
ε_T‖B‖, so a negligible backward perturbation; without it such a
column, with a = 0 but γ ≠ 0, would be rotated forever). Then for
every pair i < j in row-cyclic order: a ← ‖w_i‖²,
b ← ‖w_j‖², γ ← w_iᵀw_j. If |γ| > tol·√(a b): ζ ← (b − a)/(2γ), t ← sign(ζ)/(|ζ| + √(1 + ζ²)) (written as sign(ζ)/(|ζ|(1 + √(1 + ζ⁻²))) when |ζ| ≥ 1, so that ζ² never overflows), c ← 1/√(1 + t²), s ← c t; (w_i, w_j) ← (c w_i − s w_j, s w_i + c w_j),
the same on the columns of Y. This makes the new pair exactly
orthogonal in exact arithmetic (cs(a − b) + (c² − s²)γ = 0).
J3. [Stop.] Stop after a sweep without rotation. After max_sweeps
sweeps, report non-convergence (never seen: the method converges
quadratically once the off-diagonal mass is small).
J4. [Values.] Divide y_i and w_i by ‖y_i‖ (this keeps W = B Y
and removes the drift of the column norms of Y: c² + s² rounds
with a bias, and a column touched by r rotations drifts by up to
r·u — measured 1.3·10⁻¹⁴ for q = 21 before this step, 8·10⁻¹⁶
after, in task L3.3; without it the restarts of 12.5, P ← P Y,
compound the drift). Then σ_i ← ‖w_i‖ (unscaled); sort
nonincreasingly (stable: ties keep their column order), permuting W
and Y alike.
J5. [Left vectors.] x_i ← w_i/‖w_i‖ for σ_i > 0. For σ_i = 0 (an
exactly zero column) complete X to orthonormal columns: try e_0, e_1, … in turn, orthogonalize against the columns already in X
(two Gram–Schmidt passes) and take the first whose remaining norm
exceeds ½.
§Invariants
(J1) σ nonincreasing, nonnegative, finite for finite B.
(J2) Y orthogonal and X orthonormal to O(tol) — by the stopping
test, |x_iᵀx_j| ≤ tol relative, whatever the sizes of σ_i,
σ_j (this is why the one-sided method gives small singular values
with orthogonal vectors).
(J3) ‖B Y − X Σ‖ ≤ c·q·u·‖B‖ (backward stability of the rotations).
All three are checked by the tests below (and debug-asserted for J1).
§References
Hestenes, “Inversion of matrices by biorthogonalization”, J. SIAM 6
(1958); Demmel & Veselić, “Jacobi’s method is more accurate than QR”,
SIMAX 13 (1992); Golub & Van Loan, Matrix Computations, 4th ed.,
§8.6.3; Drmač & Veselić, “New fast and accurate Jacobi SVD algorithm”,
SIMAX 29 (2008) (the √p·ε tolerance of LAPACK dgesvj). Cited from
memory.
Structs§
- Jacobi
Options 🔒 - The thresholds of Algorithm J.
- Small
Svd 🔒 - The result
B = X diag(s) Yᵀof Algorithm J.
Functions§
- jacobi_
svd 🔒 - Algorithm J on
b(p × q,p ≥ q, finite). - pow2_
floor 🔒 2^⌊log₂ μ⌋for a positive normalμ,1otherwise.- rotate 🔒
- Rotate columns
i < jof therows-row array:(a, b) ← (c a − s b, s a + c b).