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

Resumo Técnico: Método de Kaczmarz de Bloco Aleatorizado Ganancioso para a Equação Matricial $AXB = C$ e Aplicações em Restauração de Imagens Coloridas

Enunciado do Problema
O artigo aborda a solução de equações matriciais de grande escala da forma $AXB = C$, onde $A \in \mathbb{R}^{m \times p}$, $B \in \mathbb{R}^{q \times n}$ e $C \in \mathbb{R}^{m \times n}$. Esta equação surge frequentemente em aplicações de engenharia, incluindo processamento de imagens, análise de estabilidade, teoria de controle e regressão de aprendizado de máquina. Embora métodos diretos sejam impraticáveis para sistemas de grande escala, os métodos iterativos tradicionais (por exemplo, baseados em gradiente, Jacobi, Gauss-Seidel) frequentemente exigem o armazenamento e o cálculo com toda a matriz de coeficientes em cada etapa, criando altas demandas de armazenamento e computação. Os autores focam em métodos de ação por linhas e colunas, especificamente estendendo o método de Kaczmarz, que evita o acesso total à matriz ao operar sobre subblocos.

Metodologia
Os autores propõem um conjunto de algoritmos iterativos baseados na estrutura de Kaczars, adaptados para a equação matricial $AXB = C$:

1. Kaczark de Bloco (ME-BK): Um método cíclico determinístico onde o índice da linha $i_k$ é selecionado sequencialmente ($i_k = (k \mod m) + 1$). A atualização projeta a estimativa atual sobre o hiperplano definido pela linha selecionada de $A$.
2. Kaczark de Bloco Aleatorizado Ganancioso (ME-GRBK): Um método estocástico que seleciona linhas com base em um critério de probabilidade que favorece aquelas com maiores resíduos. Especificamente, define um limiar $\zeta_k$ baseado no resíduo normalizado máximo e no resíduo global. As linhas que satisfazem $\|R_k^{i,:}\|_2^2 \ge \zeta_k \|A_{i,:}\|_2^2 \|R_k\|_F^2$ formam um conjunto candidato $J_k$, do qual uma linha é escolhida com probabilidade proporcional ao seu resíduo ao quadrado.
3. Kaczark de Bloco Aleatorizado Ganancioso Relaxado (ME-RGRBK): Uma extensão do ME-GRBK que introduz um fator de relaxação $\theta \in (0, 1)$ no critério de probabilidade para permitir uma seleção de conjunto de índices mais flexível.
4. Kaczark de Bloco de Resíduo Ponderado Máximo (ME-MWRBK): Uma versão determinística do ME-GRBK que seleciona o índice da linha que maximiza o resíduo ponderado $\frac{\|R_k^{i,:}\|_2^2}{\|A_{i,:}\|_2^2}$.

Os algoritmos utilizam a estrutura do produto de Kronecker implicitamente (via vetorização) e atualizam a matriz de resíduo $R_k = C - AX_kB$ de forma eficiente, pré-calculando $AA^T$ e $B^TB$.

Principais Contribuições

• Convergência de ME-BK: O artigo estabelece que o método determinístico ME-BK converge para a solução $X^* + X_0 - A^+AX_0BB^+$ (onde $X^* = A^+CB^+$ é a solução de menor norma única) quando o sistema é consistente. Isso preenche uma lacuna, pois a convergência do método de Kaczark de bloco para $AXB=C$ não havia sido investigada anteriormente.
• Convergência de Variantes Gananciosas: Os autores provam que os métodos ME-GRBK, ME-RGRBK e ME-MWRBK convergem para a solução única de menor norma $A^+CB^+$ em expectativa quando o sistema é consistente.
• Taxas de Convergência: A análise teórica demonstra que os fatores de convergência para os métodos gananciosos e relaxados são estritamente menores (indicando convergência mais rápida) do que o método de Kaczark de Bloco Aleatorizado (ME-RBK) existente em [12].
• Distinção de Trabalhos Anteriores: Os autores esclarecem que sua abordagem difere do método em [11]. Enquanto [11] transforma a equação em $mn$ subsistemas exigindo dois índices estocásticos, este artigo transforma-a em $m$ subsistemas ($A_{i,:}XB = C_{i,:}$) exigindo apenas um índice estocástico por iteração.

Resultados
Experimentos numéricos foram conduzidos usando MATLAB em vários conjuntos de matrizes (esparsas e densas, de posto completo e de posto deficiente) da coleção da Universidade da Flórida e geradores aleatórios.

• Verificação de Convergência: A convergência teórica do ME-BK para a forma de solução específica foi verificada através de seis conjuntos de matrizes.
• Comparação de Desempenho: Em termos de contagem de iterações (IT) e tempo de CPU, os métodos propostos ME-GRBK, ME-RGRBK e ME-MWRBK superaram consistentemente o método ME-RBK.
  • Para sistemas de posto de coluna/linha completo, as acelerações variaram de aproximadamente 2x a 13x, dependendo do conjunto de matrizes e do método.
  • Para sistemas de posto deficiente, as acelerações variaram de 1,35x a 4,29x.
  • O ME-MWRBK (determinístico) geralmente alcançou as maiores acelerações, seguido de perto pelo ME-RGRBK e ME-GRBK.
• Aplicação à Restauração de Imagem: Os métodos foram aplicados à restauração de imagem colorida (desfoque) modelada como $B = AXA_c^T + E$. Usando imagens de teste ("face", "bird", "mandril", "barbara"), os métodos propostos alcançaram Razão Sinal-Ruído de Pico (PSNR) e Índice de Similaridade Estrutural (SSIM) significativamente superiores ao ME-RBK. Por exemplo, na imagem "face", o ME-RBK rendeu um PSNR de 27,02, enquanto o ME-MWRBK alcançou 33,72.

Significância
O artigo afirma que os métodos propostos oferecem uma abordagem mais eficiente e eficaz para resolver equações matriciais de grande escala $AXB=C$ em comparação com os métodos de Kaczark de bloco aleatorizados existentes. Ao introduzir estratégias de seleção gananciosa e variantes determinísticas, os autores demonstram taxas de convergência superiores tanto teórica quanto numericamente. A aplicação bem-sucedida à restauração de imagem colorida valida a utilidade prática desses algoritmos em problemas de engenharia do mundo real, onde as restrições de dados de grande escala e armazenamento são críticas. O trabalho expande a aplicabilidade dos métodos do tipo Kaczark além de sistemas lineares para equações matriciais gerais.