Expand description
§Chapter 12.3 — Thin QR with explicit Q and five updating operations
§Purpose
A least-squares fit min ‖Ax − b‖ whose design A gains or loses an
observation (a row) or a regressor (a column), or changes by a rank-1
term, should cost O(mn), not the O(mn²) of refactorizing. Qr
keeps the thin factorization A = QR — Q ∈ T^{m×n} with orthonormal
columns, explicit; R ∈ T^{n×n} upper triangular with positive diagonal
— through insert_row, delete_row, insert_col, delete_col and
rank1_update (decision S8 of D-0127). The Q-less variant is
Cholesky (RᵀR = AᵀA): Qr::to_cholesky.
§Notation
A ∈ T^{m×n}, m ≥ n, full column rank; q_j the columns of Q,
q_(i)ᵀ its row i; R̂, M the bordered factors during an operation
(A = M R̂ throughout). A rotation G = (c, s) (Chapter 12.0.4)
applied to rows k, l of R̂ is always applied to columns k, l of M
with the same (c, s): then M R̂ is unchanged, because c q_k + s q_l,
−s q_k + c q_l against c r_k + s r_l, −s r_k + c r_l gives back
q_k r_kᵀ + q_l r_lᵀ. τ = rank_tol resolved (see QrOptions); η = reorth_eta.
§Algorithm F (factor: Householder, GVL Algorithm 5.2.1)
F1. [Check.] m ≥ n, A finite, options valid.
F2. [Reduce.] For k = 0, …, n − 1: a reflector H_k (Algorithm H)
maps W[k.., k] to α_k e_0; apply it to W[k.., k+1..].
F3. [Form Q.] Q ← H_0 ⋯ H_{n−1} [I_n; 0], applied backwards (the
reflector H_k touches columns k..n only).
F4. [Signs.] Where r_kk < 0, negate row k of R and column k of
Q.
F5. [Rank.] If r_kk ≤ τ ‖a_k‖, StatlaError::RankDeficient at k.
§Algorithm I (insert row wᵀ before row i)
I1. Check |w| = n, i ≤ m, w finite.
I2. Border: M = [Q with a zero row at i, e_i], R̂ = [R; wᵀ].
I3. For j = 0, …, n − 1: G_j with G_j (r_jj, w_j) = (ρ, 0); rotate
rows j, n of R̂ (columns j..) and columns j, n of M.
I4. Drop the last row of R̂ (now zero) and the last column of M.
Cost 3mn + 3n²/2 flops; nothing can fail after I1.
§Algorithm D (delete row i; requires m > n)
D1. z ← e_i, orthogonalized against Q by Algorithm D of 12.0.4
(DGKS, at most two passes); ν = ‖z‖ (in exact arithmetic ν² = 1 − ‖q_(i)‖²). If ν ≤ τ, the remaining rows are rank deficient:
RankDeficient (reported with the row index), nothing written.
D2. Border: M = [Q, z/ν], R̂ = [R; 0], w ← (q_(i); z_i/ν) the row
i of M.
D3. For k = n − 1, …, 0: G_k (w_k, w_{k+1}) = (·, 0); rotate rows k, k+1 of R̂ (columns k..; this fills (k+1, k) only) and columns
k, k+1 of M. Now w = ±e_0 (so column 0 of M is ±e_i), R̂ is
upper Hessenberg, its row 0 is the deleted row of A.
D4. R ← R̂[1.., ..] (upper triangular), Q ← M[rows ≠ i, 1..]; signs as
F4. Cost ≈ 5mn.
§Algorithm C (insert column c before column j; requires m > n)
C1. Check |c| = m, j ≤ n, c finite.
C2. h ← Qᵀc, z ← c − Qh by Algorithm D of 12.0.4; ρ = ‖z‖; if ρ ≤ τ ‖c‖, RankDeficient at j, nothing written.
C3. Border: M = [Q, z/ρ]; R̂ ∈ T^{(n+1)×(n+1)} with the columns of R
(and a zero last row) and the spike (h; ρ) at position j.
C4. For k = n, …, j + 1: G with G (r̂_{k−1,j}, r̂_{kj}) = (·, 0);
rotate rows k − 1, k of R̂ (columns j+1..) and columns k − 1, k
of M. Signs as F4. Cost ≈ 4mn + 3n(n − j).
§Algorithm E (delete column j)
E1. Remove column j of R: an n × (n−1) matrix, upper Hessenberg
from column j on.
E2. For p = j, …, n − 2: G (r_pp, r_{p+1,p}) = (·, 0); rotate rows
p, p+1 (columns p+1..) and columns p, p+1 of Q.
E3. Drop the last row of R (zero) and the last column of Q; signs.
Cost 6m(n − j); nothing can fail after the index check.
§Algorithm R (rank-1 update A + u vᵀ; Hammarling & Lucas §2.5)
R1. Check |u| = m, |v| = n, finite.
R2. w ← Qᵀu, z ← u − Qw (Algorithm D of 12.0.4), ρ = ‖z‖. If ρ ≤ τ ‖u‖, u is in the range of Q to working precision: ρ ← 0, z ← 0 (the border column then never mixes in: every rotation that
touches it has s = 0 exactly).
R3. Work on copies: M = [Q, z/ρ], R̂ = [R; 0], ŵ = (w; ρ).
R4. For k = n − 1, …, 0: G_k (ŵ_k, ŵ_{k+1}) = (·, 0) on rows k, k+1
of R̂ and columns k, k+1 of M: ŵ = ‖ŵ‖e_0, R̂ upper
Hessenberg.
R5. R̂_{0,:} ← R̂_{0,:} + ‖ŵ‖ vᵀ (still Hessenberg).
R6. For k = 0, …, n − 1: G (r̂_kk, r̂_{k+1,k}) = (·, 0) on rows k, k+1
(columns k+1..) and columns k, k+1 of M. The last row of R̂ is
now zero.
R7. Signs; if some r_kk ≤ τ (‖a_k‖ + |v_k| ‖u‖) (the result lost
rank; the scale is that of the column before any cancellation),
RankDeficient at k and the copies are dropped; else commit Q ← M[:, ..n], R ← R̂[..n, :]. Cost ≈ 10mn.
§Least squares
y ← Qᵀb, x ← R⁻¹y (back substitution), and the residual norm ‖b − Qy‖ (the residual is formed, not taken as √(‖b‖² − ‖y‖²), which
cancels).
§Invariants
(Q1) ‖QᵀQ − I‖_F ≤ c_Q · m · u — Qr::check_invariants(c_Q);
the DGKS step of D1, C2, R2 is what keeps it under deletions and
nearly dependent insertions.
(Q2) R upper triangular with r_jj > 0 and finite (checked by
check_invariants, and as a debug_assert! after every
operation); ‖QR − A_t‖_F ≤ c_Q · m · u · ‖A_t‖_F (tests, against
A_t in double-double).
(Q3) A failed operation leaves Q and R bit for bit unchanged: every
failure is detected before the first write (I1, D1, C1–C2, E1) or
on copies (R7).
§Acceptance (L3.2; the same as Chapter 12.2, plus Q1)
κ here is κ(A_tᵀA_t) = κ₂(A_t)², so that the bands of the
criterion (iii) — ≤ 10⁻¹² where κ ≤ 10⁸, ≤ 10× the distance
between two refactorizations elsewhere — mean the same conditioning of
R as in Chapter 12.2. Tests in tests/qr.rs. Per instance: (Q1),
(Q2) with c_Q = 16, fwd ≤ 8 κ u; in aggregate (20 seeds, 150 × 100): the ratified (iii) holds in full — max fwd ≤ 4.6·10⁻¹⁵ where
κ ≤ 10⁸ and ≤ 1.3× the distance between refactorizations. The
literal per-instance (iii) fails on small matrices (ratio up to 3·10²
on 5 × 3, where the refactorization is nearly exact): question
Q-L32-2.
§References
Golub & Van Loan (2013), §5.2 (Householder QR), §6.5.1–6.5.3 (updating the full QR); Hammarling & Lucas, MIMS EPrint 2008.111 (economy updates); Daniel, Gragg, Kaufman & Stewart, Math. Comp. 30 (1976) (Gram–Schmidt completion with reorthogonalization). Cited from memory.
Structs§
- Qr
- Thin QR
A = QR,Q ∈ R^{m×n}explicit with orthonormal columns,R ∈ R^{n×n}upper triangular withr_jj > 0,m ≥ n, full column rank (Chapter 12.3: Algorithms F, I, D, C, E, R). - QrOptions
- Options of
Qr.
Functions§
- drop_
last_ 🔒row R̂[..n, ..]of an(n+1) × cblock, as ann × cblock.- fix_
signs 🔒 - Where
r_kk < 0fork ≥ from, negate rowkofrand columnkofq(step F4).