El método de Kaczmarz o el 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 de Richard Gordon , Robert Bender y Gabor Herman en 1970, donde se denomina Técnica de Reconstrucción Algebraica (ART). [2] ART incluye la restricción de positividad, haciéndola no lineal. [3]
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 escaso . 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 muchas aplicaciones que van 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
Dejar ser un sistema de ecuaciones lineales , seasea el número de filas de A , ser el º fila de complejo -valued matriz , y deja ser una aproximación inicial arbitraria de valores complejos a la solución de . Para calcular:
( 1 )
dónde y denota conjugación compleja de.
Si el sistema es consistente, converge a la solución de norma mínima , siempre que las iteraciones comiencen con el vector cero.
Se puede definir un algoritmo más general utilizando un parámetro de relajación .
Hay versiones del método que convergen a una solución de mínimos cuadrados ponderados regularizada cuando se aplica a un sistema de ecuaciones inconsistentes y, al menos en lo que respecta al comportamiento inicial, a un costo menor que otros métodos iterativos, como el método de gradiente conjugado. . [7]
Algoritmo 2: algoritmo de Kaczmarz aleatorizado
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 al azar con probabilidad proporcional a
Este método puede verse como un caso particular de descenso de gradiente estocástico . [9]
Bajo tales circunstancias converge exponencialmente rápido a la solución de y la tasa de convergencia depende solo del número de condición escalado .
- Teorema. Dejar ser la solución de Entonces el algoritmo 2 converge a en expectativa, con el error promedio:
Prueba
Tenemos
( 2 )
Utilizando
podemos escribir ( 2 ) como
( 3 )
El punto principal de la demostración es ver el lado izquierdo en ( 3 ) como una expectativa de alguna variable aleatoria. Es decir, recuerde que el espacio de solución del ecuación de es el hiperplano
cuyo normal es Defina un vector aleatorio Z cuyos valores sean las normales a todas las ecuaciones de, con probabilidades como en nuestro algoritmo:
- con probabilidad
Entonces ( 3 ) dice que
( 4 )
La proyección ortogonal en el espacio de solución de una ecuación aleatoria de es dado por
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 como dónde son realizaciones independientes de la proyección aleatoria El vector está en el núcleo de Es ortogonal al espacio solución de la ecuación en la que proyectos, que contiene el vector (recordar que es la solución a todas las ecuaciones). La ortogonalidad de estos dos vectores produce
Para completar la prueba, tenemos que unir desde abajo. Por la definición de, tenemos
dónde son realizaciones independientes del vector aleatorio
Por lo tanto
Ahora tomamos la expectativa de ambos lados condicionada a la elección de los vectores aleatorios (de ahí que arreglemos la elección de las proyecciones aleatorias y así los vectores aleatorios y promediamos sobre el vector aleatorio ). Luego
Por ( 4 ) y la independencia,
Tomando todas las expectativas de ambas partes, llegamos a la conclusión de que
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 espaciados no uniformemente. Sin embargo, se ha señalado [10] que el éxito informado por Strohmer y Vershynin depende de las elecciones específicas que se tomaron 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 tanto, cualquier escala de las ecuaciones es irrelevante; también se puede ver en ( 1 ) que cualquier escala (distinta de cero) de las ecuaciones se cancela. Por lo tanto, en RK, uno puede usaro 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 obtener más información sobre este tema, consulte [12] [13] y las referencias allí contenidas.
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 linealesque incluye el algoritmo aleatorio de Kaczmarz como caso especial. Otros casos especiales incluyen el descenso de coordenadas aleatorias, el descenso gaussiano aleatorizado y el método de Newton aleatorizado. También surgen como casos especiales versiones en bloque y versiones con muestreo de importancia de todos estos métodos. Se muestra que el método disfruta de una disminución de la tasa 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 de "hermanos" entre estos métodos, algunos de los cuales se propusieron de forma independiente antes, mientras que muchos de los cuales eran nuevos.
Perspectivas sobre Kaczmarz aleatorizado
Las nuevas ideas interesantes sobre el método Kaczmarz aleatorizado que se pueden obtener del análisis del método incluyen:
- La tasa general del algoritmo de Gower-Richtarik recupera con precisión la tasa del método Kaczmarz aleatorizado en el caso especial cuando se redujo a ella.
- La elección de probabilidades para las que se formuló y analizó originalmente el algoritmo de Kaczmarz aleatorizado (probabilidades proporcionales a los cuadrados de las normas de fila) no es óptima. Las probabilidades óptimas son la solución de cierto programa semidefinido. La complejidad teórica de Kaczmarz aleatorizado con las probabilidades óptimas puede ser arbitrariamente mejor que la complejidad de las probabilidades estándar. Sin embargo, la cantidad en la que es mejor depende de la matriz. Hay problemas para los que las probabilidades estándar son óptimas.
- Cuando se aplica a un sistema con matriz que es positivo definido, el método de Kaczmarz aleatorizado 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 Tenga en cuenta que desde es convexo, los minimizadores de debe 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 atravesada por el gradiente estocástico minimiza la distancia euclidiana desde el minimizador desconocido (!) De , es decir, de Esta información se obtiene a partir de una visión dual del proceso iterativo (que se describe a continuación como "Punto de vista de optimización: restricción y aproximación").
Seis formulaciones equivalentes
El método Gower-Richtarik disfruta de seis formulaciones aparentemente diferentes pero equivalentes, que arrojan luz adicional sobre cómo interpretarlo (y, como consecuencia, cómo interpretar sus muchas 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: resolución lineal aleatoria
- 5. Punto de vista algebraico 2: actualización aleatoria
- 6. Punto de vista analítico: punto fijo aleatorio
A continuación, describimos algunos de estos puntos de vista. El método depende de 2 parámetros:
- una matriz definida positiva dando lugar a un producto interior euclidiano ponderado y la norma inducida
- y una matriz aleatoria con tantas filas como (y posiblemente un número aleatorio de columnas).
1. Bosquejo y proyecto
Dado el iterado anterior el nuevo punto se calcula dibujando una matriz aleatoria (de una manera iid a partir de alguna distribución fija), y la configuración
Es decir, se obtiene como la proyección de en el sistema esbozado al azar . La idea detrás de este método es elegir de tal manera que una proyección sobre el sistema esbozado es sustancialmente más simple que la solución del sistema original . El método de Kaczmarz aleatorizado se obtiene seleccionando ser la matriz de identidad, y ser el vector de coordenadas unitarias con probabilidad Diferentes opciones de y conducir a diferentes variantes del método.
2. Restringir y aproximar
Una formulación aparentemente diferente pero completamente equivalente del método (obtenida a través de la dualidad lagrangiana) es
dónde también se permite variar, y donde es alguna solución del sistema Por eso, se obtiene restringiendo primero la actualización al subespacio lineal abarcado por las columnas de la matriz aleatoria , es decir, a
y luego eligiendo el punto de este subespacio que se aproxima mejor . Esta formulación puede parecer sorprendente ya que parece imposible realizar el paso de aproximación debido al hecho de queno se sabe (después de todo, ¡esto es lo que estamos tratando de calcular!). Sin embargo, todavía es posible hacer esto, simplemente porque calculado de esta manera es lo mismo que calculado a través del boceto y la formulación del proyecto y desde no aparece ahí.
5. Actualización aleatoria
La actualización también se puede escribir explícitamente como
donde por Denotamos el pseudoinverso de la matriz de Moore-Penrose . Por lo tanto, el método se puede escribir en la forma, dónde es un vector de actualización aleatorio .
Dejando se puede demostrar que el sistema siempre tiene una solución , y que para todas estas 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 pseudo-inversa conduce solo a una solución en particular. El papel de lo pseudo-inverso es doble:
- Permite que el método se escriba en el formulario explícito de "actualización aleatoria" como se indicó anteriormente,
- Simplifica el análisis a través de la sexta formulación final.
6. Punto fijo aleatorio
Si restamos de ambos lados de la fórmula de actualización aleatoria, denotar
y usa el hecho de que llegamos a la última formulación:
dónde es la matriz de identidad. La matriz de iteración, es aleatorio, de ahí el nombre de esta formulación.
Convergencia
Tomando expectativas condicionales en la sexta formulación (condicionada a ), obtenemos
Tomando de nuevo la expectativa y usando la propiedad de torre de las expectativas, obtenemos
Gower y Richtarik [14] demuestran que
donde la norma matricial está definida por
Además, sin ningún supuesto sobre uno tiene Tomando normas y desenrollando la recurrencia, obtenemos
Teorema [Gower y Richtarik 2015]
Observación . Una condición suficiente para que los residuales 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 también se puede establecer sin la suposición de rango de columna completa de una manera diferente. [15]
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 al mismo ritmo:
Observación . Este segundo tipo de convergencia es más fuerte debido a la siguiente identidad [14] que se aplica a cualquier vector aleatorio y cualquier vector fijo :
Convergencia de Kaczmarz aleatorizados
Hemos visto que el método de Kaczmarz aleatorizado aparece como un caso especial del método de Gower-Richtarik para y siendo el vector de coordenadas unitarias con probabilidad dónde es el fila de Puede comprobarse mediante cálculo directo que
Otros casos especiales
Notas
- ↑ Kaczmarz (1937)
- ^ Gordon, Bender y Herman (1970)
- ↑ Gordon (2011)
- ↑ Herman (2009)
- ^ Censor y Zenios (1997)
- ^ Aster, Borchers y Thurber (2004)
- ^ Ver Herman (2009) y referencias allí.
- ↑ a b c Strohmer y Vershynin (2009)
- ^ Needell, Srebro y Ward (2009)
- ↑ a b Censor, Herman y Jiang (2009)
- ^ Strohmer y Vershynin (2009b)
- ^ Bass y Gröchenig (2013)
- ↑ Gordon (2017)
- ^ a b c Gower & Richtarik (2015) error de harvcoltxt: múltiples objetivos (3 ×): CITEREFGowerRichtarik2015 ( ayuda )
- ^ Gower, Robert M .; Richtarik, Peter (2015). "Doble ascenso estocástico para la resolución de sistemas lineales". arXiv : 1512.06890 [ math.NA ].
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. Classe des Sciences Mathématiques et Naturelles. Serie A, Sciences Mathématiques , 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, doi : 10.1016 / 0022-5193 (70) 90109 -8 , PMID 5492997
- Gordon, Richard (2011), ¡ Alto al cáncer de mama ahora! Imaginar vías de obtención de imágenes hacia la búsqueda, destrucción, curación y espera vigilante del cáncer de mama premetastasis. En: Breast Cancer - A Lobar Disease, 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 la proyección (2a ed.), Springer
- 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 aleatorio 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
- Needell, Deanna; Ward, Rachel; Srebro, Nati (2015), "Descenso de gradiente estocástico, muestreo ponderado y el algoritmo aleatorio de Kaczmarz", Programación matemática , 155 : 549–573, arXiv : 1310.5715 , doi : 10.1007 / s10107-015-0864-7
- Censor, Yair; Herman, Gabor ; Jiang, M. (2009), "Una nota sobre el comportamiento del algoritmo aleatorio 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
- Bass, Richard F .; Gröchenig, Karlheinz (2013), "Muestreo relevante de funciones limitadas por banda", Illinois Journal of Mathematics , 57 (1): 43–58
- Gordon, Dan (2017), "Un enfoque de desaleatorización para recuperar señales de banda limitada en una amplia gama de frecuencias de muestreo aleatorio", Algoritmos numéricos , doi : 10.1007 / s11075-017-0356-3
- Vinh Nguyen, Quang; Lumban Gaol, Ford (2011), Actas del Segundo Congreso Internacional de Aplicaciones y Ciencias Computacionales de 2011 , 2 , Springer, págs. 465–469
- Gower, Robert; Richtarik, Peter (2015), "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
- Gower, Robert; Richtarik, Peter (2015), "Ascenso dual estocástico para resolver sistemas lineales", arXiv : 1512.06890 [ math.NA ]
enlaces externos
- [1] Un algoritmo de Kaczmarz aleatorizado con convergencia exponencial
- [2] Comentarios sobre el método Kaczmarz aleatorizado