Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Golub kahan bidiagonalisation — where it appears

A recurrence building two orthonormal bases at once with a bidiagonal matrix between them, which is what LSQR and the hybrid methods project onto.

Named by 3 essays across 2 fields — each of them below, with the objects they name alongside it.

1591317212529333710⁻¹110¹10²bidiagonalisation stepsrelative errorleast without: 20no penaltypenalty insidewhat stopping is worthbest without a penalty0.14and at step 40161best with one0.14and at step 400.14the same floor, reached twiceand only one run stays on it

The step that stops mattering

Regularise the problem the iteration has built rather than the problem it was given, and the error curve stops turning. The unregularised run ends 1,127 times above its own best; the same run with a penalty inside it ends 1.000000000003 times above.

combination · iterative regularisation 27121722273237424710⁻²10⁻¹110¹subspace size kvalueno answer below 8GCV's traceλ from GCVλ from the residuala denominator that is not the problem'strace at k = 41trace at k = 4827λ range across the run2.2subspace before an answer8the divisor moves by twenty-sevenand the answer does not move

A parameter chosen on a smaller problem

Inside a hybrid method the regularisation parameter is chosen on a 25×24 problem rather than a 64×64 one. The rule that reads a residual transfers exactly; the rule that reads a trace is biased by exactly two grid steps at twenty-four steps and one at forty, at every noise level from 10% to 0.1%.

combination · parameter choice 10²10⁴10⁶10⁸10¹⁰0285684112140168196224condition numberstepsnormal equationsbidiagonalisationone sequence, two costssteps at κ = 10², both16at κ = 10⁶, ratio1.1at κ = 10¹⁰, ratio1.9the same iterates in the algebraand twice the work at κ = 10¹⁰

One sequence and two recurrences

CGLS and LSQR compute the same iterates — the minimiser over a space is unique, so there is nothing to choose between them in the algebra. At κ = 10⁶ they cost 42 steps and 47. At κ = 10¹⁰ they cost 110 and 209, across four seeds, and the quantity that separates them is the orthogonality of a basis neither of them keeps.

iterative · krylov

Named alongside it

The objects these essays reach for when they reach for this one.

Hybrid regularisationIll posed problemProjected problemStopping criterionCglsDiscrepancy principleForward errorGeneralised cross validationInfluence matrixIterative regularisationKrylov subspaceLsqr

All concepts