Zemor's decoding algorithm

The Landweber iteration or Landweber algorithm is an algorithm to solve ill-posed linear inverse problems, and it has been extended to solve non-linear problems that involve constraints. The method was first proposed in the 1950s, and it can be now viewed as a special case of many other more general methods.

Basic algorithm

The original Landweber algorithm attempts to recover a signal x from 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 errors made on 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}0.5\|Ax-y\|_{2}^{2}$

using an iterative method. For ill-posed problems, the iterative method may be purposefully stopped before convergence.

The algorithm is given by the update

$x_{k+1}=x_{k}-A^{*}(Ax_{k}-y).$

If we write $f(x)=0.5\|Ax-y\|_{2}^{2}$, then the update can be written in terms of the gradient

$x_{k+1}=x_{k}-\nabla f(x_{k})$

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

Discussion of the Landweber iteration as a regularization algorithm can be found in.

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<\tau <2/(\|A\|^{2})$ 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<\tau <2/(\|A\|^{2})$. 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 by many scientific communities, especially those studying ill-posed problems. In particular, the computer vision community and the signal restoration community. It is also used in image processing, since many image problems, such as deblurring, are ill-posed. Variants of this method have been used also in sparse approximation problems and compressed sensing settings.