Método Kaczmarz

Algoritmo

El método de Kaczmarz o algoritmo de Kaczmarz es un algoritmo iterativo para resolver sistemas de ecuaciones lineales . Fue descubierto por primera vez por el matemático polaco Stefan Kaczmarz , ^[1] y fue redescubierto en el campo de la reconstrucción de imágenes a partir de proyecciones por Richard Gordon , Robert Bender y Gabor Herman en 1970, donde se lo llama Técnica de Reconstrucción Algebraica (ART). ^[2] La ART incluye la restricción de positividad, lo que la hace no lineal. ^[3] ${\displaystyle Ax=b}$

El método de Kaczmarz es aplicable a cualquier sistema lineal de ecuaciones, pero su ventaja computacional con respecto a otros métodos depende de que el sistema sea disperso . Se ha demostrado que es superior, en algunas aplicaciones de imágenes biomédicas, a otros métodos como el método de retroproyección filtrada . ^[4]

Tiene múltiples aplicaciones, desde la tomografía computarizada (TC) hasta el procesamiento de señales . También se puede obtener aplicando a los hiperplanos, descritos por el sistema lineal, el método de proyecciones sucesivas sobre conjuntos convexos (POCS). ^{[5] [6]}

Algoritmo 1: Algoritmo de Kaczmarz

Sea un sistema de ecuaciones lineales , sea el número de filas de A , sea la fila n° de la matriz de valores complejos , y sea una aproximación inicial de valores complejos arbitraria a la solución de . Para calcular: ${\displaystyle Ax=b}$ ${\displaystyle m}$ ${\displaystyle a_{i}}$ ${\displaystyle i}$ ${\displaystyle A}$ ${\displaystyle x^{0}}$ ${\displaystyle Ax=b}$ ${\displaystyle k=0,1,\ldots }$

donde y denota la conjugación compleja de . ${\displaystyle i=k{\bmod {m}}+1,i=1,2,\ldots m}$ ${\displaystyle {\overline {a_{i}}}}$ ${\displaystyle a_{i}}$

Si el sistema es consistente, converge a la solución de norma mínima , siempre que las iteraciones comiencen con el vector cero. ${\displaystyle x^{k}}$

Se puede definir un algoritmo más general utilizando un parámetro de relajación ${\displaystyle \lambda ^{k}}$

${\displaystyle x^{k+1}=x^{k}+\lambda ^{k}{\frac {b_{i}-\langle a_{i},x^{k}\rangle }{\|a_{i}\|^{2}}}{\overline {a_{i}}}}$

Existen versiones del método que convergen a una solución de mínimos cuadrados ponderados regularizados cuando se aplican a un sistema de ecuaciones inconsistentes y, al menos en lo que respecta al comportamiento inicial, a un coste menor que otros métodos iterativos, como el método del gradiente conjugado . ^[7]

Algoritmo 2: Algoritmo de Kaczmarz aleatorio

^{En 2009, Thomas Strohmer y Roman Vershynin [8]} introdujeron una versión aleatoria del método de Kaczmarz para sistemas lineales sobredeterminados en la que la i -ésima ecuación se selecciona aleatoriamente con una probabilidad proporcional a ${\displaystyle \|a_{i}\|^{2}.}$

Este método puede verse como un caso particular de descenso de gradiente estocástico . ^[9]

En tales circunstancias, converge exponencialmente rápido a la solución de y la tasa de convergencia depende únicamente del número de condición escalado . ${\displaystyle x_{k}}$ ${\displaystyle Ax=b,}$ ${\displaystyle \kappa (A)}$

Teorema. Sea la solución de Entonces el algoritmo 2 converge a en expectativa, con el error promedio: ${\displaystyle x}$ ${\displaystyle Ax=b.}$ ${\displaystyle x}$

${\displaystyle \mathbb {E} \|x_{k}-x\|^{2}\leq \left(1-\kappa (A)^{-2}\right)^{k}\cdot \|x_{0}-x\|^{2}.}$

Prueba

Tenemos

Usando

${\displaystyle \|A\|^{2}=\sum _{j=1}^{m}\|a_{j}\|^{2}}$

podemos escribir ( 2 ) como

El punto principal de la prueba es considerar el lado izquierdo en ( 3 ) como una expectativa de alguna variable aleatoria. Es decir, recordar que el espacio de solución de la ecuación de es el hiperplano ${\displaystyle j-th}$ ${\displaystyle Ax=b}$

${\displaystyle \{y:\langle y,a_{j}\rangle =b_{j}\},}$

cuya normal es Defina un vector aleatorio Z cuyos valores sean las normales a todas las ecuaciones de , con probabilidades como en nuestro algoritmo: ${\displaystyle {\tfrac {a_{j}}{\|a_{j}\|^{2}}}.}$ ${\displaystyle Ax=b}$

${\displaystyle Z={\frac {a_{j}}{\|a_{j}\|}}}$con probabilidad ${\displaystyle {\frac {\|a_{j}\|^{2}}{\|A\|^{2}}}\qquad \qquad \qquad j=1,\ldots ,m}$

Entonces ( 3 ) dice que

La proyección ortogonal sobre el espacio de soluciones de una ecuación aleatoria de está dada por ${\displaystyle P}$ ${\displaystyle Ax=b}$ ${\displaystyle Pz=z-\langle z-x,Z\rangle Z.}$

Ahora estamos listos para analizar nuestro algoritmo. Queremos demostrar que el error se reduce en cada paso en promedio (condicionado a los pasos anteriores) por al menos el factor de La siguiente aproximación se calcula a partir de donde son realizaciones independientes de la proyección aleatoria El vector está en el núcleo de Es ortogonal al espacio de solución de la ecuación sobre la que se proyecta, que contiene el vector (recuerde que es la solución de todas las ecuaciones). La ortogonalidad de estos dos vectores produce entonces ${\displaystyle {\|x_{k}-x\|^{2}}}$ ${\displaystyle (1-\kappa (A)^{-2}).}$ ${\displaystyle x_{k}}$ ${\displaystyle x_{k-1}}$ ${\displaystyle x_{k}=P_{k}x_{k-1},}$ ${\displaystyle P_{1},P_{2},\ldots }$ ${\displaystyle P.}$ ${\displaystyle x_{k-1}-x_{k}}$ ${\displaystyle P_{k}.}$ ${\displaystyle P_{k}}$ ${\displaystyle x_{k}-x}$ ${\displaystyle x}$

${\displaystyle \|x_{k}-x\|^{2}=\|x_{k-1}-x\|^{2}-\|x_{k-1}-x_{k}\|^{2}.}$

Para completar la prueba, tenemos que acotar desde abajo. Por la definición de , tenemos ${\displaystyle \|x_{k-1}-x_{k}\|^{2}}$ ${\displaystyle x_{k}}$

${\displaystyle \|x_{k-1}-x_{k}\|=\langle x_{k-1}-x,Z_{k}\rangle }$

¿Dónde están las realizaciones independientes del vector aleatorio? ${\displaystyle Z_{1},Z_{2},\ldots }$ ${\displaystyle Z.}$

De este modo

${\displaystyle \|x_{k}-x\|^{2}\leq \left(1-\left|\left\langle {\frac {x_{k-1}-x}{\|x_{k-1}-x\|}},Z_{k}\right\rangle \right|^{2}\right){\|x_{k-1}-x\|^{2}}.}$

Ahora tomamos la expectativa de ambos lados condicionada a la elección de los vectores aleatorios (por lo tanto, fijamos la elección de las proyecciones aleatorias y, por lo tanto, los vectores aleatorios y promediamos sobre el vector aleatorio ). Entonces ${\displaystyle Z_{1},\ldots ,Z_{k-1}}$ ${\displaystyle P_{1},\ldots ,P_{k-1}}$ ${\displaystyle x_{1},\ldots ,x_{k-1}}$ ${\displaystyle Z_{k}}$

${\displaystyle \mathbb {E} _{Z_{1},\ldots ,Z_{k-1}}{\|x_{k}-x\|^{2}}=\left(1-\mathbb {E} _{Z_{1},\ldots ,Z_{k-1},Z_{k}}\left|\left\langle {\frac {x_{k-1}-x}{\|x_{k-1}-x\|}},Z_{k}\right\rangle \right|^{2}\right){\|x_{k-1}-x\|^{2}}.}$

Por ( 4 ) y la independencia,

${\displaystyle \mathbb {E} _{Z_{1},\ldots ,Z_{k-1}}{\|x_{k}-x\|^{2}}\leq (1-\kappa (A)^{-2}){\|x_{k-1}-x\|^{2}}.}$

Teniendo en cuenta las expectativas completas de ambas partes, concluimos que

${\displaystyle \mathbb {E} \|x_{k}-x\|^{2}\leq (1-\kappa (A)^{-2})\mathbb {E} {\|x_{k-1}-x\|^{2}}.\blacksquare }$

La superioridad de esta selección se ilustró con la reconstrucción de una función de banda limitada a partir de sus valores de muestreo no uniformemente espaciados. Sin embargo, se ha señalado ^[10] que el éxito informado por Strohmer y Vershynin depende de las elecciones específicas que se hicieron allí al traducir el problema subyacente, cuya naturaleza geométrica es encontrar un punto común de un conjunto de hiperplanos , en un sistema de ecuaciones algebraicas. Siempre habrá representaciones algebraicas legítimas del problema subyacente para las cuales el método de selección en ^[8] funcionará de manera inferior. ^{[8] [10] [11]}

La iteración de Kaczmarz ( 1 ) tiene una interpretación puramente geométrica: el algoritmo proyecta sucesivamente la iteración actual sobre el hiperplano definido por la siguiente ecuación. Por lo tanto, cualquier escala de las ecuaciones es irrelevante; también se puede ver a partir de ( 1 ) que cualquier escala (distinto de cero) de las ecuaciones se cancela. Por lo tanto, en RK, se pueden usar o cualquier otro peso que pueda ser relevante. Específicamente, en el ejemplo de reconstrucción mencionado anteriormente, las ecuaciones se eligieron con probabilidad proporcional a la distancia promedio de cada punto de muestra de sus dos vecinos más cercanos, un concepto introducido por Feichtinger y Gröchenig. Para avances adicionales sobre este tema, consulte ^{[12] [13]} y las referencias allí incluidas. ${\displaystyle \|a_{i}\|}$

Algoritmo 3: algoritmo de Gower-Richtarik

En 2015, Robert M. Gower y Peter Richtarik ^[14] desarrollaron un método iterativo aleatorio versátil para resolver un sistema consistente de ecuaciones lineales que incluye el algoritmo aleatorio de Kaczmarz como un caso especial. Otros casos especiales incluyen el descenso aleatorio de coordenadas, el descenso aleatorio de Gauss y el método aleatorio de Newton. Las versiones en bloque y las versiones con muestreo de importancia de todos estos métodos también surgen como casos especiales. Se muestra que el método disfruta de una tasa de decaimiento exponencial (en expectativa), también conocida como convergencia lineal, en condiciones muy suaves en la forma en que la aleatoriedad ingresa al algoritmo. El método de Gower-Richtarik es el primer algoritmo que descubre una relación "hermana" entre estos métodos, algunos de los cuales se propusieron independientemente antes, mientras que muchos de los cuales eran nuevos. ${\displaystyle Ax=b}$

Información sobre Kaczmarz aleatorio

Entre los nuevos e interesantes conocimientos sobre el método aleatorio de Kaczmarz que se pueden obtener a partir del análisis del método se incluyen los siguientes:

• La tasa general del algoritmo de Gower-Richtarik recupera con precisión la tasa del método aleatorio de Kaczmarz en el caso especial cuando se reduce a él.
• La elección de probabilidades para las que se formuló y analizó originalmente el algoritmo de Kaczmarz aleatorio (probabilidades proporcionales a los cuadrados de las normas de fila) no es óptima. Las probabilidades óptimas son la solución de un cierto programa semidefinido. La complejidad teórica del algoritmo de Kaczmarz aleatorio con las probabilidades óptimas puede ser arbitrariamente mejor que la complejidad para las probabilidades estándar. Sin embargo, la cantidad en que es mejor depende de la matriz . Hay problemas para los que las probabilidades estándar son óptimas. ${\displaystyle A}$
• Cuando se aplica a un sistema con una matriz que es definida positiva, el método de Kaczmarz aleatorio es equivalente al método de descenso de gradiente estocástico (SGD) (con un tamaño de paso muy especial) para minimizar la función cuadrática fuertemente convexa. Nótese que como es convexo, los minimizadores de deben satisfacer , que es equivalente a El "tamaño de paso especial" es el tamaño de paso que conduce a un punto que en la línea unidimensional abarcada por el gradiente estocástico minimiza la distancia euclidiana desde el minimizador desconocido (!) de , es decir, desde Esta perspectiva se obtiene a partir de una visión dual del proceso iterativo (descrito a continuación como "Punto de vista de optimización: restricción y aproximación"). ${\displaystyle A}$ ${\displaystyle f(x)={\tfrac {1}{2}}x^{T}Ax-b^{T}x.}$ ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle \nabla f(x)=0}$ ${\displaystyle Ax=b.}$ ${\displaystyle f}$ ${\displaystyle x^{*}=A^{-1}b.}$

Seis formulaciones equivalentes

El método Gower-Richtarik cuenta con seis formulaciones aparentemente diferentes pero equivalentes, lo que arroja luz adicional sobre cómo interpretarlo (y, en consecuencia, cómo interpretar sus numerosas variantes, incluido el Kaczmarz aleatorio):

• 1. Punto de vista del boceto: Boceto y proyecto
• 2. Punto de vista de optimización: restricción y aproximación
• 3. Punto de vista geométrico: intersección aleatoria
• 4. Punto de vista algebraico 1: Solución lineal aleatoria
• 5. Punto de vista algebraico 2: Actualización aleatoria
• 6. Punto de vista analítico: Punto fijo aleatorio

A continuación, describiremos algunos de estos puntos de vista. El método depende de dos parámetros:

• una matriz definida positiva que da lugar a un producto interno euclidiano ponderado y la norma inducida ${\displaystyle B}$ ${\displaystyle \langle x,y\rangle _{B}:=x^{T}By}$

${\displaystyle \|x\|_{B}=\left(\langle x,x\rangle _{B}\right)^{\frac {1}{2}},}$

• y una matriz aleatoria con tantas filas como (y posiblemente un número aleatorio de columnas). ${\displaystyle S}$ ${\displaystyle A}$

1. Boceto y proyecto

Dada la iteración anterior, el nuevo punto se calcula extrayendo una matriz aleatoria (en un modo iid a partir de alguna distribución fija) y estableciendo ${\displaystyle x^{k},}$ ${\displaystyle x^{k+1}}$ ${\displaystyle S}$

${\displaystyle x^{k+1}={\underset {x}{\operatorname {arg\ min} }}\|x-x^{k}\|_{B}{\text{ subject to }}S^{T}Ax=S^{T}b.}$

Es decir, se obtiene como la proyección de sobre el sistema esbozado aleatoriamente . La idea detrás de este método es elegir de tal manera que una proyección sobre el sistema esbozado sea sustancialmente más simple que la solución del sistema original . El método de Kaczmarz aleatorizado se obtiene eligiendo que sea la matriz identidad y que sea el vector de coordenadas unitario con probabilidad Diferentes elecciones de y conducen a diferentes variantes del método. ${\displaystyle x^{k+1}}$ ${\displaystyle x^{k}}$ ${\displaystyle S^{T}Ax=S^{T}b}$ ${\displaystyle S}$ ${\displaystyle Ax=b}$ ${\displaystyle B}$ ${\displaystyle S}$ ${\displaystyle i^{th}}$ ${\displaystyle p_{i}=\|a_{i}\|_{2}^{2}/\|A\|_{F}^{2}.}$ ${\displaystyle B}$ ${\displaystyle S}$

2. Restringir y aproximar

Una formulación aparentemente diferente pero completamente equivalente del método (obtenida a través de la dualidad lagrangiana) es

${\displaystyle x^{k+1}={\underset {x}{\operatorname {arg\ min} }}\left\|x-x^{*}\right\|_{B}{\text{ subject to }}x=x^{k}+B^{-1}A^{T}Sy,}$

donde también se permite que varíe, y donde es cualquier solución del sistema . Por lo tanto, se obtiene restringiendo primero la actualización al subespacio lineal abarcado por las columnas de la matriz aleatoria , es decir, a ${\displaystyle y}$ ${\displaystyle x^{*}}$ ${\displaystyle Ax=b.}$ ${\displaystyle x^{k+1}}$ ${\displaystyle B^{-1}A^{T}S}$

${\displaystyle \left\{h:h=B^{-1}A^{T}Sy,\quad y{\text{ can vary }}\right\},}$

y luego elegir el punto de este subespacio que mejor se aproxima a . Esta formulación puede parecer sorprendente ya que parece imposible realizar el paso de aproximación debido al hecho de que no se conoce (después de todo, ¡esto es lo que estamos tratando de calcular!). Sin embargo, todavía es posible hacer esto, simplemente porque el cálculo de esta manera es el mismo que el calculado a través de la formulación del boceto y el proyecto y dado que no aparece allí. ${\displaystyle x}$ ${\displaystyle x^{*}}$ ${\displaystyle x^{*}}$ ${\displaystyle x^{k+1}}$ ${\displaystyle x^{k+1}}$ ${\displaystyle x^{*}}$

5. Actualización aleatoria

La actualización también se puede escribir explícitamente como

${\displaystyle x^{k+1}=x^{k}-B^{-1}A^{T}S\left(S^{T}AB^{-1}A^{T}S\right)^{\dagger }S^{T}\left(Ax^{k}-b\right),}$

donde denotamos la pseudoinversa de Moore-Penrose de la matriz . Por lo tanto, el método puede escribirse en la forma , donde es un vector de actualización aleatorio . ${\displaystyle M^{\dagger }}$ ${\displaystyle M}$ ${\displaystyle x^{k+1}=x^{k}+h^{k}}$ ${\displaystyle h^{k}}$

Si se deja que se pueda demostrar que el sistema siempre tiene una solución y que para todas esas soluciones el vector es el mismo. Por lo tanto, no importa cuál de estas soluciones se elija y el método también se puede escribir como . La pseudoinversa conduce solo a una solución particular. El papel de la pseudoinversa es doble: ${\displaystyle M=S^{T}AB^{-1}A^{T}S,}$ ${\displaystyle My=S^{T}(Ax^{k}-b)}$ ${\displaystyle y^{k}}$ ${\displaystyle x^{k+1}-B^{-1}A^{T}Sy^{k}}$ ${\displaystyle x^{k+1}=x^{k}-B^{-1}A^{T}Sy^{k}}$

• Permite que el método se escriba en la forma explícita de "actualización aleatoria" como se indicó anteriormente.
• El análisis se simplifica mediante la sexta y última formulación.

6. Punto fijo aleatorio

Si restamos de ambos lados de la fórmula de actualización aleatoria, denotamos ${\displaystyle x^{*}}$

${\displaystyle Z:=A^{T}S\left(S^{T}AB^{-1}A^{T}S\right)^{\dagger }S^{T}A,}$

y utilizamos el hecho de que llegamos a la última formulación: ${\displaystyle Ax^{*}=b,}$

${\displaystyle x^{k+1}-x^{*}=\left(I-B^{-1}Z\right)\left(x^{k}-x^{*}\right),}$

donde es la matriz identidad. La matriz de iteración es aleatoria, de ahí el nombre de esta formulación. ${\displaystyle I}$ ${\displaystyle I-B^{-1}Z,}$

Convergencia

Al tomar expectativas condicionales en la sexta formulación (condicional a ), obtenemos ${\displaystyle x^{k}}$

${\displaystyle \mathbb {E} \left.\left[x^{k+1}-x^{*}\right|x^{k}\right]=\left(I-B^{-1}\mathbb {E} [Z]\right)\left[x^{k}-x^{*}\right].}$

Tomando nuevamente la expectativa y utilizando la propiedad de la torre de expectativas, obtenemos

${\displaystyle \mathbb {E} \left[x^{k+1}-x^{*}\right]=(I-B^{-1}\mathbb {E} [Z])\mathbb {E} \left[x^{k}-x^{*}\right].}$

Gower y Richtarik ^[14] muestran que

${\displaystyle \rho :=\left\|I-B^{-{\frac {1}{2}}}\mathbb {E} [Z]B^{-{\frac {1}{2}}}\right\|_{B}=\lambda _{\max }\left(I-B^{-1}\mathbb {E} [Z]\right),}$

donde la norma matricial se define por

${\displaystyle \|M\|_{B}:=\max _{x\neq 0}{\frac {\|Mx\|_{B}}{\|x\|_{B}}}.}$

Además, sin ninguna suposición sobre uno tiene Al tomar normas y desarrollar la recurrencia, obtenemos ${\displaystyle S}$ ${\displaystyle 0\leq \rho \leq 1.}$

Teorema [Gower y Richtarik 2015]

${\displaystyle \left\|\mathbb {E} \left[x^{k}-x^{*}\right]\right\|_{B}\leq \rho ^{k}\|x^{0}-x^{*}\|_{B}.}$

Observación . Una condición suficiente para que los residuos esperados converjan a 0 es Esto se puede lograr si tiene un rango de columna completo y en condiciones muy suaves en La convergencia del método se puede establecer también sin el supuesto de rango de columna completo de una manera diferente. ^[15] ${\displaystyle \rho <1.}$ ${\displaystyle A}$ ${\displaystyle S.}$

También es posible mostrar un resultado más fuerte:

Teorema [Gower y Richtarik 2015]

Las normas cuadradas esperadas (en lugar de las normas de expectativas) convergen a la misma tasa:

${\displaystyle \mathbb {E} \left\|\left[x^{k}-x^{*}\right]\right\|_{B}^{2}\leq \rho ^{k}\left\|x^{0}-x^{*}\right\|_{B}^{2}.}$

Observación . Este segundo tipo de convergencia es más fuerte debido a la siguiente identidad ^[14] que se cumple para cualquier vector aleatorio y cualquier vector fijo : ${\displaystyle x}$ ${\displaystyle x^{*}}$

${\displaystyle \left\|\mathbb {E} \left[x-x^{*}\right]\right\|^{2}=\mathbb {E} \left[\left\|x-x^{*}\right\|^{2}\right]-\mathbb {E} \left[\|x-\mathbb {E} [x]\|^{2}\right].}$

Convergencia de Kaczmarz aleatorizado

Hemos visto que el método aleatorio de Kaczmarz aparece como un caso especial del método de Gower-Richtarik para y siendo el vector de coordenadas unitario con probabilidad donde es la fila de Se puede comprobar mediante cálculo directo que ${\displaystyle B=I}$ ${\displaystyle S}$ ${\displaystyle i^{th}}$ ${\displaystyle p_{i}=\|a_{i}\|_{2}^{2}/\|A\|_{F}^{2},}$ ${\displaystyle a_{i}}$ ${\displaystyle i^{th}}$ ${\displaystyle A.}$

${\displaystyle \rho =\|I-B^{-1}\mathbb {E} [Z]\|_{B}=1-{\frac {\lambda _{\min }(A^{T}A)}{\|A\|_{F}^{2}}}.}$

Otros casos especiales

Algoritmo 4: PLSS-Kaczmarz

Dado que la convergencia del método de Kaczmarz (aleatorio) depende de una tasa de convergencia, el método puede avanzar lentamente en algunos problemas prácticos. ^[10] Para asegurar la terminación finita del método, Johannes Brust y Michael Saunders (académico) ^[16] han desarrollado un proceso que generaliza la iteración de Kaczmarz (aleatorio) y termina en, como máximo, iteraciones en una solución para el sistema consistente . El proceso se basa en la reducción de la dimensionalidad o proyecciones sobre espacios de menor dimensión, de donde deriva su nombre PLSS (Projected Linear Systems Solver). Una iteración de PLSS-Kaczmarz puede considerarse como la generalización ${\displaystyle m}$ ${\displaystyle Ax=b}$

${\displaystyle x^{k+1}=x^{k}+A_{:,1:k}^{T}(A_{1:k,:}A_{:,1:k}^{T})^{\dagger }(b_{1:k}-A_{1:k,:}x^{k})}$

donde es la selección de filas 1 a y todas las columnas de . Una versión aleatoria del método utiliza índices de fila no repetidos en cada iteración: donde cada uno está en . La iteración converge a una solución cuando . En particular, dado que se cumple que ${\displaystyle A_{1:k,:}}$ ${\displaystyle k}$ ${\displaystyle A}$ ${\displaystyle k}$ ${\displaystyle \{i_{1},\ldots ,i_{k-1},i_{k}\}}$ ${\displaystyle i_{j}}$ ${\displaystyle 1,2,...,m}$ ${\displaystyle k=m}$ ${\displaystyle A_{1:m,:}=A}$

${\displaystyle Ax^{m+1}=Ax^{m}+AA^{T}(AA^{T})^{\dagger }(b-Ax^{m})=b}$

y por lo tanto es una solución del sistema lineal. El cálculo de iteraciones en PLSS-Kaczmarz se puede simplificar y organizar de manera efectiva. El algoritmo resultante solo requiere productos matriz-vector y tiene una forma directa. ${\displaystyle x^{m+1}}$

El algoritmo PLSS-Kaczmarz es  entrada: matriz A lado derecho b  salida: solución x tal que Ax=b x := 0 , P = [0]  para  k  en  1,2,...,m  hacer  a  := A(i k ,:)' // Seleccionar un índice i k en 1,...,m sin remuestrear  d  := P' * a  c 1  := norm(a)  c 2  := norm(d)  c 3  := (b i k -x'*a)/((c 1 -c 2 )*(c 1 +c 2 ))  p  := c 3 *(a - P*(P'*a)) P  := [ P, p/norm(p) ] // Añadir una actualización normalizada x  := x + p devolver  x

Notas

1. Kaczmarz (1937)
2. Gordon, Bender y Herman (1970)
3. Gordon (2011)
4. Herman (2009)
5. Censor y Zenios (1997)
6. Aster, Borchers y Thurber (2004)
7. Véase Herman (2009) y referencias allí citadas.
8. Strohmer y Vershynin (2009)
9. Needell, Srebro y Ward (2015)
10. Censor, Herman y Jiang (2009)
11. Strohmer y Vershynin (2009b)
12. Bass y Gröchenig (2013)
13. Gordon (2017)
14. Gower y Richtarik (2015a)
15. Gower y Richtarik (2015b)
16. Brut y Saunders (2023)

Referencias

• Kaczmarz, Stefan (1937), "Angenäherte Auflösung von Systemen linearer Gleichungen" (PDF) , Bulletin International de l'Académie Polonaise des Sciences et des Lettres. Clase de Ciencias Matemáticas y Naturales. Serie A, Ciencias Matemáticas , vol. 35, págs. 355–357
• Chong, Edwin KP; Zak, Stanislaw H. (2008), Introducción a la optimización (3.ª ed.), John Wiley & Sons, págs. 226-230
• Gordon, Richard ; Bender, Robert; Herman, Gabor (1970), "Técnicas de reconstrucción algebraica (ART) para microscopía electrónica tridimensional y fotografía de rayos X", Journal of Theoretical Biology , 29 (3): 471–481, Bibcode :1970JThBi..29..471G, doi :10.1016/0022-5193(70)90109-8, PMID  5492997
• Gordon, Richard (2011), ¡ Detengamos el cáncer de mama ahora! Imaginando vías de imagen para la búsqueda, destrucción, cura y observación del cáncer de mama premetástasis. En: Cáncer de mama: una enfermedad lobular, editor: Tibor Tot , Springer, págs. 167–203
• Herman, Gabor (2009), Fundamentos de la tomografía computarizada: reconstrucción de imágenes a partir de proyecciones (2.ª ed.), Springer, ISBN 9781846287237
• Censor, Yair ; Zenios, SA (1997), Optimización paralela: teoría, algoritmos y aplicaciones , Nueva York: Oxford University Press
• Aster, Richard; Borchers, Brian; Thurber, Clifford (2004), Estimación de parámetros y problemas inversos , Elsevier
• Strohmer, Thomas; Vershynin, Roman (2009), "Un algoritmo de Kaczmarz aleatorizado para sistemas lineales con convergencia exponencial" (PDF) , Journal of Fourier Analysis and Applications , 15 (2): 262–278, arXiv : math/0702226 , doi :10.1007/s00041-008-9030-4, S2CID  1903919
• Needell, Deanna; Srebro, Nati; Ward, Rachel (2015), "Descenso de gradiente estocástico, muestreo ponderado y el algoritmo aleatorio de Kaczmarz", Programación matemática , 155 (1–2): 549–573, arXiv : 1310.5715 , doi :10.1007/s10107-015-0864-7, S2CID  2370209
• Censor, Yair; Herman, Gabor ; Jiang, M. (2009), "Una nota sobre el comportamiento del algoritmo aleatorizado de Kaczmarz de Strohmer y Vershynin", Journal of Fourier Analysis and Applications , 15 (4): 431–436, doi :10.1007/s00041-009-9077-x, PMC  2872793 , PMID  20495623
• Strohmer, Thomas; Vershynin, Roman (2009b), "Comentarios sobre el método aleatorio de Kaczmarz", Journal of Fourier Analysis and Applications , 15 (4): 437–440, doi :10.1007/s00041-009-9082-0, S2CID  14806325
• Bass, Richard F. ; Gröchenig, Karlheinz (2013), "Muestreo relevante de funciones limitadas por bandas", Illinois Journal of Mathematics , 57 (1): 43–58, arXiv : 1203.0146 , doi :10.1215/ijm/1403534485, S2CID  42705738
• Gordon, Dan (2017), "Un enfoque de desaleatorización para recuperar señales de banda limitada en una amplia gama de frecuencias de muestreo aleatorias", Numerical Algorithms , 77 (4): 1141–1157, doi :10.1007/s11075-017-0356-3, S2CID  1794974
• Vinh Nguyen, Quang; Lumban Gaol, Ford (2011), Actas del 2º Congreso Internacional de Aplicaciones Informáticas y Ciencias Computacionales de 2011 , vol. 2, Springer, págs. 465–469
• Gower, Robert; Richtarik, Peter (2015a), "Métodos iterativos aleatorios para sistemas lineales", SIAM Journal on Matrix Analysis and Applications , 36 (4): 1660–1690, arXiv : 1506.03296 , doi :10.1137/15M1025487, S2CID  8215294
• Gower, Robert; Richtarik, Peter (2015b), "Ascenso dual estocástico para resolver sistemas lineales", arXiv : 1512.06890 [math.NA]
• Brust, Johannes J; Saunders, Michael A (2023), "PLSS: un solucionador de sistemas lineales proyectados", SIAM Journal on Scientific Computing , 45 (2): A1012–A1037, arXiv : 2207.07615 , Bibcode :2023SJSC...45A1012B, doi :10.1137/22M1509783

Enlaces externos

• [1] Un algoritmo de Kaczmarz aleatorio con convergencia exponencial
• [2] Comentarios sobre el método aleatorio de Kaczmarz
• [3] Algoritmo de Kaczmarz en el entrenamiento de la red de Kolmogorov-Arnold