Landweber iteration

Basic algorithm

The original Landweber algorithm attempts to recover a signal x from (noisy) measurements y. The linear version assumes that y = Ax for a linear operator A. When the problem is in finite dimensions, A is just a matrix.

When A is nonsingular, then an explicit solution is x = A^{-1} y. However, if A is ill-conditioned, the explicit solution is a poor choice since it is sensitive to any noise in the data y. If A is singular, this explicit solution doesn't even exist. The Landweber algorithm is an attempt to regularize the problem, and is one of the alternatives to Tikhonov regularization. We may view the Landweber algorithm as solving:

: \min_x |Ax-y|_2^2/2

using an iterative method. The algorithm is given by the update

: x_{k+1} = x_{k} - \omega A^*(Ax_k - y).

where the relaxation factor \omega satisfies 0 . Here \sigma_1 is the largest singular value of A. If we write f(x) = |Ax-y|_2^2 /2, then the update can be written in terms of the gradient

: x_{k+1} = x_k - \omega \nabla f(x_k)

and hence the algorithm is a special case of gradient descent.

For ill-posed problems, the iterative method needs to be stopped at a suitable iteration index, because it semi-converges. This means that the iterates approach a regularized solution during the first iterations, but become unstable in further iterations. The reciprocal of the iteration index 1/k acts as a regularization parameter. A suitable parameter is found, when the mismatch |Ax_k-y|_2^2 approaches the noise level.

Using the Landweber iteration as a regularization algorithm has been discussed in the literature.

Nonlinear extension

In general, the updates generated by x_{k+1} = x_{k} - \tau \nabla f(x_k) will generate a sequence f(x_k) that converges to a minimizer of f whenever f is convex and the stepsize \tau is chosen such that 0 where |\cdot | is the spectral norm.

Since this is special type of gradient descent, there currently is not much benefit to analyzing it on its own as the nonlinear Landweber, but such analysis was performed historically by many communities not aware of unifying frameworks.

The nonlinear Landweber problem has been studied in many papers in many communities; see, for example.

Extension to constrained problems

If f is a convex function and C is a convex set, then the problem

: \min_{x \in C} f(x)

can be solved by the constrained, nonlinear Landweber iteration, given by:

: x_{k+1} = \mathcal{P}C( x{k} - \tau \nabla f(x_k) )

where \mathcal{P} is the projection onto the set C. Convergence is guaranteed when 0 . This is again a special case of projected gradient descent (which is a special case of the forward–backward algorithm) as discussed in.

Applications

Since the method has been around since the 1950s, it has been adopted and rediscovered by many scientific communities, especially those studying ill-posed problems. In X-ray computed tomography it is called SIRT - simultaneous iterative reconstruction technique. It has also been used in the computer vision community Johansson, B., Elfving, T., Kozlovc, V., Censor, Y., Forssen, P.E., Granlund, G.; "The application of an oblique-projected Landweber method to a model of supervised learning", Math. Comput. Modelling, vol 43, pp 892–909 (2006) and the signal restoration community. It is also used in image processing, since many image problems, such as deconvolution, are ill-posed. Variants of this method have been used also in sparse approximation problems and compressed sensing settings.{{cite book |name-list-style = amp |chapter-url = http://infoscience.epfl.ch/record/183059

References

Landweber, L. (1951): An iteration formula for Fredholm integral equations of the first kind. Amer. J. Math. 73, 615–624

References

1. Louis, A.K. (1989): Inverse und schlecht gestellte Probleme. Stuttgart, Teubner
2. Vainikko, G.M., Veretennikov, A.Y. (1986): Iteration Procedures in Ill-Posed Problems. Moscow, Nauka (in Russian)
3. A convergence analysis of the Landweber iteration for nonlinear ill-posed problems, Martin Hanke, Andreas Neubauer and Otmar Scherzer. NUMERISCHE MATHEMATIK, Volume 72, Number 1 (1995), 21-37, {{doi. 10.1007/s002110050158
4. Eicke, B.: Iteration methods for convexly constrained ill-posed problems in Hilbert space. Numer. Funct. Anal. Optim. 13, 413–429 (1992)
5. Trussell, H.J., Civanlar, M.R.: The Landweber iteration and projection onto convex sets. IEEE Trans. Acoust., Speech, Signal Process. 33, 1632–1634 (1985)
6. P. L. Combettes and J.-C. Pesquet, "Proximal splitting methods in signal processing," in: Fixed-Point Algorithms for Inverse Problems in Science and Engineering, (H. H. Bauschke, [[Regina S. Burachik. R. S. Burachik]], P. L. Combettes, V. Elser, D. R. Luke, and H. Wolkowicz, Editors), pp. 185–212. Springer, New York, 2011. [https://arxiv.org/abs/0912.3522 ArXiv]