Iteración de Landweber

La iteración Landweber o algoritmo Landweber es un algoritmo para resolver problemas lineales inversos mal planteados y se ha ampliado 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 ahora puede verse como un caso especial de muchos otros métodos más generales. ^[2]

Algoritmo básico

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

Cuando A es no singular , entonces una solución explícita es . Sin embargo, si A está mal condicionado , 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 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 x=A^{-1}y}$

${\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 satisface . Aquí está el valor singular más grande de . Si escribimos , entonces la actualización se puede escribir en términos del gradiente. ${\displaystyle \omega }$ ${\displaystyle 0<\omega <2/\sigma _{1}^{2}}$ ${\displaystyle \sigma _{1}}$ ${\displaystyle A}$ ${\displaystyle f(x)=\|Ax-y\|_{2}^{2}/2}$

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

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

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

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

extensión no lineal

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

Dado que se trata de un tipo especial de descenso de gradiente, actualmente no resulta muy beneficioso analizarlo por sí solo como el Landweber no lineal, pero dicho análisis fue realizado históricamente por muchas comunidades que no eran conscientes de los marcos unificadores.

El problema no lineal de Landweber se ha estudiado en muchos artículos en muchas comunidades; ver, por ejemplo. ^[5]

Extensión a problemas restringidos

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

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

se puede resolver mediante la iteración Landweber no lineal restringida, dada por:

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

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

Aplicaciones

Dado que el método existe desde la década de 1950, ha sido adoptado y redescubierto por muchas comunidades científicas, especialmente aquellas que estudian problemas mal planteados. En la tomografía computarizada de rayos X se llama SIRT: técnica de reconstrucción iterativa simultánea. 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] También se utiliza en el procesamiento de imágenes , ya que muchos problemas de imágenes, como la deconvolución , están mal planteados. También se han utilizado variantes de este método en problemas de aproximación escasa y entornos de detección comprimidos . ^[9]

Referencias

1. Landweber, L. (1951): Una fórmula de iteración para ecuaciones integrales de Fredholm de primer tipo. América. J. Matemáticas. 73, 615–624
2. PL Combettes y J.-C. Pesquet, "Métodos de división proximal en el procesamiento de señales", en: Algoritmos de punto fijo para problemas inversos en ciencia e ingeniería, (HH Bauschke, RS Burachik , PL Combettes, V. Elser, DR Luke y H. Wolkowicz, editores), págs. 185-212. Springer, Nueva York, 2011. ArXiv
3. Louis, AK (1989): Problema inverso y schlecht gestellte. Stuttgart, Teubner
4. Vainikko, GM, Veretennikov, AY (1986): Procedimientos de iteración en problemas mal planteados. Moscú, Nauka (en ruso)
5. Un análisis de convergencia de la iteración de Landweber para problemas no lineales mal planteados, Martin Hanke, Andreas Neubauer y Otmar Scherzer. NUMERISCHE MATHEMATIC, Volumen 72, Número 1 (1995), 21-37, doi :10.1007/s002110050158
6. Eicke, B .: Métodos de iteración para problemas mal planteados con restricciones convexas en el espacio de Hilbert. Número. Función. Anal. Óptimo. 13, 413–429 (1992)
7. Johansson, B., Elfving, T., Kozlovc, V., Censor, Y., Forssen, PE, Granlund, G.; "La aplicación de un método Landweber de proyección oblicua a un modelo de aprendizaje supervisado", Math. Computadora. Modelado, vol 43, págs. 892–909 (2006)
8. Trussell, HJ, Civanlar, MR: La iteración y proyección de Landweber sobre conjuntos convexos. Traducción IEEE. Acústica, Habla, Proceso de Señal. 33, 1632-1634 (1985)
9. Anastasios Kyrillidis y Volkan Cevher (2011). "Recetas sobre métodos estrictos de umbralización". Recetas para métodos de umbralización estricta . págs. 353–356. doi :10.1109/CAMSAP.2011.6136024. ISBN 978-1-4577-2105-2. S2CID  14996037.