Método de Kaczmarz

Tenemos

Usando

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

podemos escribir ( 2 ) como

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

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

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

${\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${\displaystyle P}$sobre el espacio de soluciones de una ecuación aleatoria de${\displaystyle Ax=b}$es dado por${\displaystyle Pz=z-\langle z-x,Z\rangle Z.}$

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

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

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

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

dónde${\displaystyle Z_{1},Z_{2},\ldots }$son realizaciones independientes del vector aleatorio${\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 esperanza de ambos lados condicionada a la elección de los vectores aleatorios.${\displaystyle Z_{1},\ldots ,Z_{k-1}}$(por lo tanto, fijamos la elección de las proyecciones aleatorias)${\displaystyle P_{1},\ldots ,P_{k-1}}$y por lo tanto los vectores aleatorios${\displaystyle x_{1},\ldots ,x_{k-1}}$y promediamos sobre el vector aleatorio${\displaystyle Z_{k}}$). Entonces

${\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}}.}$

Tomando en cuenta las expectativas 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 ancho de banda limitado a partir de sus valores de muestreo espaciados de forma no uniforme. Sin embargo, se ha señalado ^{[ 10 ]} que el éxito reportado por Strohmer y Vershynin depende de las elecciones específicas que se hicieron allí al traducir el problema subyacente, cuya naturaleza geométrica consiste en 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 ]} tendrá un desempeño 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 escalado de las ecuaciones es irrelevante; también se puede ver en ( 1 ) que cualquier escalado (distinto de cero) de las ecuaciones se cancela. Así, en RK, se puede usar${\displaystyle \|a_{i}\|}$o cualquier otro peso que pueda ser relevante. Específicamente, en el ejemplo de reconstrucción mencionado anteriormente, las ecuaciones se eligieron con una probabilidad proporcional a la distancia promedio de cada punto de muestra a 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í citadas.

Entre las nuevas e interesantes perspectivas sobre el método aleatorio de Kaczmarz que se pueden obtener del análisis del método se incluyen:

• La tasa general del algoritmo de Gower-Richtarik recupera con precisión la tasa del método aleatorio de Kaczmarz en el caso especial en que se reduce a este.
• La elección de probabilidades para la cual se formuló y analizó originalmente el algoritmo aleatorio de Kaczmarz (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 aleatorio de Kaczmarz con las probabilidades óptimas puede ser arbitrariamente mejor que la complejidad para las probabilidades estándar. Sin embargo, la magnitud de esta mejora depende de la matriz.${\displaystyle A}$Existen problemas para los que las probabilidades estándar son óptimas.
• Cuando se aplica a un sistema con matriz${\displaystyle A}$que es definida positiva, el método aleatorio de Kaczmarz 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.${\displaystyle f(x)={\tfrac {1}{2}}x^{T}Ax-b^{T}x.}$Tenga en cuenta que desde${\displaystyle f}$es convexo, los minimizadores de${\displaystyle f}$debe satisfacer${\displaystyle \nabla f(x)=0}$, lo cual es equivalente a${\displaystyle Ax=b.}$El "tamaño de paso especial" es el tamaño de paso que conduce a un punto que en la línea unidimensional generada por el gradiente estocástico minimiza la distancia euclidiana desde el minimizador desconocido (!) de${\displaystyle f}$, es decir, de${\displaystyle x^{*}=A^{-1}b.}$Esta perspectiva 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").

El método de 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 muchas variantes, incluido el método aleatorio de Kaczmarz):

• 1. Punto de vista del boceto: Boceto y proyecto
• 2. Punto de vista de la optimización: Restringir y aproximar
• 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 dos parámetros:

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

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

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

Dado el iterado anterior${\displaystyle x^{k},}$el nuevo punto${\displaystyle x^{k+1}}$se calcula extrayendo una matriz aleatoria${\displaystyle S}$(de forma i.i.d. a partir de alguna distribución fija), y estableciendo

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

Eso es,${\displaystyle x^{k+1}}$se obtiene como la proyección de${\displaystyle x^{k}}$sobre el sistema dibujado al azar${\displaystyle S^{T}Ax=S^{T}b}$La idea detrás de este método es elegir${\displaystyle S}$de tal manera que una proyección sobre el sistema esbozado sea sustancialmente más simple que la solución del sistema original.${\displaystyle Ax=b}$El método aleatorio de Kaczmarz se obtiene seleccionando${\displaystyle B}$ser la matriz identidad y${\displaystyle S}$ser el${\displaystyle i^{th}}$vector de coordenadas unitarias con probabilidad${\displaystyle p_{i}=\|a_{i}\|_{2}^{2}/\|A\|_{F}^{2}.}$Diferentes opciones de${\displaystyle B}$y${\displaystyle S}$dan lugar a diferentes variantes del método.

Una formulación del método aparentemente diferente pero totalmente equivalente (obtenida mediante 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,}$

dónde${\displaystyle y}$También se permite variar, y donde${\displaystyle x^{*}}$¿Existe alguna solución al sistema?${\displaystyle Ax=b.}$Por eso,${\displaystyle x^{k+1}}$se obtiene restringiendo primero la actualización al subespacio lineal generado por las columnas de la matriz aleatoria.${\displaystyle B^{-1}A^{T}S}$, es decir, a

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

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

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 por${\displaystyle M^{\dagger }}$denotamos la pseudoinversa de Moore-Penrose de la matriz${\displaystyle M}$Por lo tanto, el método se puede escribir de la forma${\displaystyle x^{k+1}=x^{k}+h^{k}}$, dónde${\displaystyle h^{k}}$es un vector de actualización aleatoria .

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

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

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

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

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

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

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

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

${\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 esperanza y utilizando la propiedad de torre de las esperanzas, 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\|IB^{-{\frac {1}{2}}}\mathbb {E} [Z]B^{-{\frac {1}{2}}}\right\|_{B}=\lambda _{\max }\left(IB^{-1}\mathbb {E} [Z]\right),}

donde la norma de la matriz se define por

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

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

${\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:${\displaystyle \rho <1.}$Esto se puede lograr si${\displaystyle A}$tiene rango de columna completo y bajo condiciones muy suaves en${\displaystyle S.}$La convergencia del método también puede establecerse de otra manera sin la suposición de rango de columna completo. ^{[ 15 ]}

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

Las normas al cuadrado esperadas (en lugar de las normas de expectativas) convergen al mismo ritmo:

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

Nota : Este segundo tipo de convergencia es más fuerte debido a la siguiente identidad ^{[ 14 ]} que se cumple para cualquier vector aleatorio.${\displaystyle x}$y cualquier vector fijo${\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].}$

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

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