Greedy randomized block Kaczmarz method for matrix equation AXB=C and its applications in color image restoration

Resumen Técnico: Método de Kaczmarz de Bloque Aleatorizado Codicioso para la Ecuación Matricial $AXB = C$ y Aplicaciones en la Restauración de Imágenes en Color

Planteamiento del Problema
El artículo aborda la solución de ecuaciones matriciales de gran escala de la forma $AXB = C$, donde $A \in \mathbb{R}^{m \times p}$, $B \in \mathbb{R}^{q \times n}$ y $C \in \mathbb{R}^{m \times n}$. Esta ecuación surge frecuentemente en aplicaciones de ingeniería, incluyendo el procesamiento de imágenes, análisis de estabilidad, teoría de control y regresión en aprendizaje automático. Dado que los métodos directos son impracticables para sistemas de gran escala, los métodos iterativos tradicionales (por ejemplo, basados en gradientes, Jacobi, Gauss-Seidel) a menudo requieren almacenar y computar con la matriz de coeficientes completa en cada paso, lo que genera altas demandas de almacenamiento y computación. Los autores se centran en métodos de acción por filas y por columnas, específicamente extendiendo el método de Kaczmarz, el cual evita el acceso total a la matriz al operar sobre subbloques.

Metodología
Los autores proponen un conjunto de algoritmos iterativos basados en el marco de Kaczmarz, adaptados para la ecuación matricial $AXB = C$:

1. Kaczmarz de Bloque (ME-BK): Un método cíclico determinista donde el índice de fila $i_k$ se selecciona secuencialmente ($i_k = (k \mod m) + 1$). La actualización proyecta la estimación actual sobre el hiperplano definido por la fila seleccionada de $A$.
2. Kaczmarz de Bloque Aleatorizado Codicioso (ME-GRBK): Un método estocástico que selecciona filas basándose en un criterio de probabilidad que favorece aquellas con residuos más grandes. Específicamente, define un umbral $\zeta_k$ basado en el residuo normalizado máximo y la norma del residuo global. Las filas que satisfacen $\|R_k^{i,:}\|_2^2 \ge \zeta_k \|A_{i,:}\|_2^2 \|R_k\|_F^2$ forman un conjunto candidato $J_k$, del cual se elige una fila con una probabilidad proporcional a su residuo al cuadrado.
3. Kaczmarz de Bloque Aleatorizado Codicioso Relajado (ME-RGRBK): Una extensión de ME-GRBK que introduce un factor de relajación $\theta \in (0, 1)$ en el criterio de probabilidad para permitir una selección de conjunto de índices más flexible.
4. Kaczmarz de Bloque de Residuo Ponderado Máximo (ME-MWRBK): Una versión determinista de ME-GRBK que selecciona el índice de fila que maximiza el residuo ponderado $\frac{\|R_k^{i,:}\|_2^2}{\|A_{i,:}\|_2^2}$.

Los algoritmos utilizan la estructura del producto de Kronecker implícitamente (vía vectorización) y actualizan la matriz de residuo $R_k = C - AX_kB$ de manera eficiente mediante la precomputación de $AA^T$ y $B^TB$.

Contribuciones Clave

• Convergencia de ME-BK: El artículo establece que el método determinista ME-BK converge a la solución $X^* + X_0 - A^+AX_0BB^+$ (donde $X^* = A^+CB^+$ es la solución única de norma mínima) cuando el sistema es consistente. Esto llena un vacío, ya que la convergencia del método de Kaczmarz de bloque para $AXB=C$ no había sido investigada previamente.
• Convergencia de las Variantes Codiciosas: Los autores demuestran que los métodos ME-GRBK, ME-RGRBK y ME-MWRBK convergen a la solución única de norma mínima $A^+CB^+$ en esperanza cuando el sistema es consistente.
• Tasas de Convergencia: El análisis teórico demuestra que los factores de convergencia para los métodos codiciosos y relajados son estrictamente menores (indicando una convergencia más rápida) que los del método de Kaczmarz de Bloque Aleatorizado (ME-RBK) existente en [12].
• Distinción de Trabajos Previos: Los autores aclaran que su enfoque difiere del método en [11]. Mientras que [11] transforma la ecuación en $mn$ subsistemas que requieren dos índices estocásticos, este artículo la transforma en $m$ subsistemas ($A_{i,:}XB = C_{i,:}$) que requieren solo un índice estocástico por iteración.

Resultidos
Se realizaron experimentos numéricos utilizando MATLAB con diversos conjuntos de matrices (dispersas y densas, de rango completo y de rango deficiente) de la colección de la Universidad de Florida y generadores aleatorios.

• Verificación de Convergencia: La convergencia teórica de ME-BK hacia la forma de solución específica fue verificada a través de seis conjuntos de matrices.
• Comparación de Desempeño: En términos de número de iteraciones (IT) y tiempo de CPU, los métodos propuestos ME-GRBK, ME-RGRBK y ME-MWRBK superaron consistentemente al método ME-RBK.
  • Para sistemas de rango completo de columna/fila, las aceleraciones oscilaron aproximadamente entre 2x y 13x, dependiendo del conjunto de matrices y el método.
  • Para sistemas de rango deficiente, las aceleraciones oscilaron entre 1.35x y 4.29x.
  • El ME-MWRBK (determinista) generalmente logró las mayores aceleraciones, seguido de cerca por ME-RGRBK y ME-GRBK.
• Aplicación a la Restauración de Imágenes: Los métodos se aplicaron a la restauración de imágenes en color (desenfoque) modelada como $B = AXA_c^T + E$. Utilizando imágenes de prueba ("face", "bird", "mandril", "barbara"), los métodos propuestos alcanzaron una Relación Señal-Ruido Pico (PSNR) e Índice de Similitud Estructural (SSIM) significativamente más altos en comparación con ME-RBK. Por ejemplo, en la imagen "face", ME-RBK produjo un PSNR de 27.02, mientras que ME-MWRBK alcanzó 33.72.

Significancia
El artículo afirma que los métodos propuestos ofrecen un enfoque más eficiente y efectivo para resolver ecuaciones matriciales de gran escala $AXB=C$ en comparación con los métodos de Kaczmarz de bloque aleatorizados existentes. Al introducir estrategias de selección codiciosa y variantes deterministas, los autores demuestran tasas de convergencia superiores tanto teórica como numéricamente. La aplicación exitosa a la restauración de imágenes en color valida la utilidad práctica de estos algoritmos en problemas de ingeniería del mundo real donde los datos de gran escala y las restricciones de almacenamiento son factores críticos. El trabajo expande la aplicabilidad de los métodos de tipo Kaczmarz más allá de los sistemas lineales hacia ecuaciones matriciales generales.