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 3 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 unpreconditioneddimension a step1.2best iterate carries24at step20τ = 10⁻³, past the edgedimension a step3.6best iterate carries33its error0.4837111519232731353910⁻¹10⁻⁰.⁵1effective dimensionrelative errorthe arc: dimension 8.0 to 24.0none10⁻⁰.⁵10⁻¹10⁻¹.⁵10⁻²10⁻².⁵10⁻³large dots: each run's own best iteratethe answer sits at one effective dimension

The parameter neither knob is

A preconditioned run has a cutoff and a step count, and neither is the regularisation parameter. The parameter is the effective dimension of the iterate: every cutoff that works puts its own best at 23.7 to 24.3 of it, where the unpreconditioned run's best sits at 23.2, and what the cutoff buys is the rate — 1.27 of it a step with no preconditioner and 3.53 with one. The edge is where a single stride is longer than the distance left.

combination · Iterative regularisation

Named alongside it

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

Conjugate gradientsFilter factorsIterative regularisationTikhonov regularisationSemi-convergenceStopping criterionCirculant preconditionerDiscrepancy principleEffective dimensionFlop countIll-posed problemKrylov subspace

All concepts