Iteración de Landweber

La iteración de Landweber o algoritmo de Landweber ^es un algoritmo para resolver problemas inversos lineales mal condicionados , y se ha extendido para resolver problemas no lineales que implican restricciones. El método fue propuesto por primera vez en la década de 1950 por Louis Landweber [ ^{1 ]} y actualmente puede considerarse un caso particular de muchos otros métodos más generales ^{[ 2 ] .}

El algoritmo original de Landweber ^{[ 1 ]} intenta recuperar una señal x a partir de mediciones (ruidosas) y . La versión lineal supone que${\displaystyle y=Ax}$para un operador lineal A. Cuando el problema está en dimensiones finitas , A es simplemente una matriz.

Cuando A no es singular , entonces una solución explícita es${\displaystyle x=A^{-1}y}$Sin embargo, si A está mal condicionada , la solución explícita es una mala elección, ya que es sensible a cualquier ruido en los datos y . Si A es singular , esta solución explícita ni siquiera existe. El algoritmo de Landweber es un intento de regularizar el problema y es una de las alternativas a la regularización de Tikhonov . Podemos considerar que el algoritmo de Landweber resuelve:

${\displaystyle \min _{x}\|Ax-y\|_{2}^{2}/2}$

utilizando un método iterativo . El algoritmo viene dado por la actualización.

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

donde el factor de relajación${\displaystyle \omega }$Satisface${\displaystyle 0<\omega <2/\sigma _{1}^{2}}$. Aquí${\displaystyle \sigma _{1}}$es el mayor valor singular de${\displaystyle A}$. Si escribimos${\displaystyle f(x)=\|Ax-y\|_{2}^{2}/2}$Entonces, la actualización se puede escribir en términos del gradiente.

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

y por lo tanto el algoritmo es un caso especial de descenso de gradiente .

Para problemas mal condicionados , el método iterativo debe detenerse en un índice de iteración adecuado, ya que converge parcialmente. Esto significa que las iteraciones se aproximan a una solución regularizada durante las primeras iteraciones, pero se vuelven inestables en iteraciones posteriores. El recíproco del índice de iteración${\displaystyle 1/k}$actúa como un parámetro de regularización. Se encuentra un parámetro adecuado cuando el desajuste${\displaystyle \|Ax_{k}-y\|_{2}^{2}}$se aproxima al nivel de ruido.

El uso de la iteración de Landweber como algoritmo de regularización se ha discutido en la literatura. ^{[ 3 ] [ 4 ]}

En general, las actualizaciones generadas por ${\displaystyle x_{k+1}=x_{k}-\tau \nabla f(x_{k})}$ generará una secuencia${\displaystyle f(x_{k})}$que converge a un minimizador de f siempre que f sea convexa y el tamaño del paso${\displaystyle \tau }$se elige de tal manera que${\displaystyle 0<\tau <2/(\|\nabla f\|^{2})}$dónde${\displaystyle \|\cdot \|}$es la norma espectral .

Dado que se trata de un tipo especial de descenso de gradiente, actualmente no hay mucho beneficio en analizarlo de forma aislada como el método de Landweber no lineal, pero históricamente, muchas comunidades que desconocían la existencia de marcos unificadores realizaron dicho análisis.

El problema de Landweber no lineal ha sido estudiado en muchos artículos en muchas comunidades; véase, por ejemplo, ^{[ 5 ] .}

Si f es una función convexa y C es un conjunto convexo , entonces el problema

${\displaystyle \min _{x\in C}f(x)}$

puede resolverse mediante la iteración de Landweber no lineal con restricciones, dada por:

${\displaystyle x_{k+1}={\mathcal {P}}_{C}(x_{k}-\tau \nabla f(x_{k}))}$

dónde${\displaystyle {\mathcal {P}}}$es la proyección sobre el conjunto C. La convergencia está garantizada cuando${\displaystyle 0<\tau <2/(\|A\|^{2})}$. ^{[ 6 ]} Este es nuevamente un caso especial del descenso de gradiente proyectado (que es un caso especial del algoritmo hacia adelante-hacia atrás ) como se discute en. ^{[ 2 ]}

Dado que el método existe desde la década de 1950, ha sido adoptado y redescubierto por numerosas comunidades científicas, especialmente aquellas que estudian problemas mal condicionados. En tomografía computarizada de rayos X se denomina técnica de reconstrucción iterativa simultánea (SIRT). También se ha utilizado en la comunidad de visión por computadora ^{[ 7 ]} y en la comunidad de restauración de señales ^{[ 8 ]} . Asimismo, se emplea en el procesamiento de imágenes , ya que muchos problemas de imagen, como la deconvolución , son mal condicionados. Variantes de este método también se han utilizado en problemas de aproximación dispersa y en entornos de detección comprimida ^{[ 9 ]} .