Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Landweber iteration — where it appears

The iteration that adds a fixed multiple of Aᵀ times the current residual to the solution at every step, which is gradient descent on the least-squares misfit. Stopped early it regularises an ill-posed problem, with filter factors 1 − (1 − ωσ²)ᵏ that depend on step length and step count mainly through their product.

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

conjugate gradientsbest step20best error0.1410% window, last/first6.5Landweberbest step1778best error0.1410% window, last/first901110¹10²10³10⁴10⁵10⁶10⁷10⁻¹110¹10²matrix–vector productsrelative errorCGLS best: step 20Landweber best: step 1,778CGLSLandweberthe same answer at two pricesand a window three orders wide

A step that is not a unit of work

Landweber's iteration reaches conjugate gradients' best answer on the same deconvolution — 0.1414 against 0.1426 — at step 1,778 instead of step 20, and at 0.1% noise at step 56,234 instead of 44. Each step costs the same two products. And within 10% of its best it runs from step 7 to step 6,310, where conjugate gradients runs from 4 to 26: the slow method is the one that forgives a late stop.

combination · Iterative regularisation 12345610⁻⁶10⁻⁵10⁻⁴10⁻³10⁻²10⁻¹digits of measurement accuracybest relative errorTikhonovtruncationCGLS stepslope 0.89, optimalslope 2/3, Tikhonov's limithow fast the error fallsTikhonov slope0.7truncation slope0.94CGLS step slope0.89optimal 2ν/(2ν + 1)0.89Tikhonov's limit0.67better data, smaller errorat a rate the method may not be able to keep

The method that cannot use a smooth answer

On the collection's own signal four regularisers reach the same floor to a few per cent. Score them instead against answers of increasing smoothness and one stops improving. Across six decades of noise Tikhonov's error falls with a fitted slope of 0.70 whether the answer is twice or four times as smooth, while truncation's rises to 0.94 — and at 10⁻⁶ noise Tikhonov's best is 38 times truncation's.

combination · Iterative regularisation

Named alongside it

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

Conjugate gradientsFilter factorsIterative regularisationTikhonov regularisationDiscrepancy principleFlop countIll-posed problemKrylov subspaceSemi-convergenceSingular valuesSource conditionStopping criterion

All concepts