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

技術要約：行列方程式 $AXB = C$ に対する強欲型ランダム化ブロック・カチャルツ法と、そのカラー画像復元への応用

問題提起
本論文は、$A \in \mathbb{R}^{m \times p}$、$B \in \mathbb{R}^{q \times n}$、$C \in \mathbb{R}^{m \times n}$ である大規模な行列方程式 $AXB = C$ の解法について扱っている。この方程式は、画像処理、安定性解析、制御理論、機械学習回帰などの工学分野において頻繁に発生する。直接法は大規模なシステムに対しては非現実的であるが、従来の反復法（勾配法、ヤコビ法、ガウス＝ザイデル法など）は、各ステップで係数行列全体を保持し計算する必要があるため、高いストレージおよび計算需要を生じさせる。著者らは、行作用および列作用法、特に、サブブロックによる操作によって行列全体へのアクセスを回避するカチャルツ法の拡張である行作用法に焦点を当てている。

手法
著者らは、行列方程式 $AXB = C$ に適応させたカチャルツの枠組みに基づく一連の反復アルゴリズムを提案している：

1. ブロック・カチャルツ (ME-BK): 行インデックス $i_k$ を逐次的に選択する（$i_k = (k \mod m) + 1$）決定論的な巡回法。更新は、選択された $A$ の行によって定義される超平面への現在の推定値の投影を行う。
2. 強欲型ランダム化ブロック・カチャルツ (ME-GRBK): 残差が大きい行を優先する確率基準に基づいて行を選択する確率論的手法。具体的には、最大正規化残差とグローバルな残差ノルムに基づく閾値 $\zeta_k$ を定義する。$\|R_k^{i,:}\|_2^2 \ge \zeta_k \|A_{i,:}\|_2^2 \|R_k\|_F^2$ を満たす行が候補集合 $J_k$ を形成し、そこから残差の二乗に比例した確率で行が選択される。
3. 緩和型強欲型ランダム化ブロック・カチャルツ (ME-RGRBK): ME-GRBKの拡張であり、より柔軟なインデックス集合の選択を可能にするために、確率基準に緩和係数 $\theta \in (0, 1)$ を導入している。
4. 最大重み残差ブロック・カチャルツ (ME-MWRBK): 重み付き残差 $\frac{\|R_k^{i,:}\|_2^2}{\|A_{i,:}\|_2^2}$ を最大化する行インデックスを選択する、ME-GRBKの決定論的バージョンである。

これらのアルゴリズムは、ベクトル化を通じてクロネッカー積の構造を暗黙的に利用し、$AA^T$ および $B^TB$ を事前計算することで、残差行列 $R_k = C - AX_kB$ を効率的に更新する。

主な貢献

• ME-BKの収束性: 本論文は、システムが一貫している場合、決定論的な ME-BK 法が $X^* + X_0 - A^+AX_0BB^+$ （ここで $X^* = A^+CB^+$ は一意の最小ノルム解）に収束することを確立している。これは、$AXB=C$ に対するブロック・カチャルツ法の収束性がこれまで調査されていなかったという空白を埋めるものである。
• 強欲型変種の収束性: 著者らは、システムが一貫しているとき、ME-GRBK、ME-RGRBK、および ME-MWRBK が期待値において一意の最小ノルム解 $A^+CB^+$ に収束することを証明している。
• 収束率: 理論的解析により、強欲型および緩和型の収束係数は、[12] で提示されている既存のランダム化ブロック・カチャルツ (ME-RBK) 法よりも厳密に小さい（より速い収束を示す）ことが示されている。
• 先行研究との区別: 著者らは、彼らのアプローチが [11] の手法とは異なることを明確にしている。[11] は方程式を2つの確率的インデックスを必要とする $mn$個のサブシステムに変換するが、本論文は方程式を$m$個のサブシステム ($A_{i,:}XB = C_{i,:}$) に変換し、1回の反復につき1つの確率的インデックスのみを必要とする。

結果
数値実験は、フロリダ大学のコレクションおよび乱数生成器を用いた様々な行列セット（疎および密、フルランクおよびランク不足）を用いて MATLAB で実施された。

• 収束の検証: ME-BK の特定の解の形式への理論的収束が、6 つの行列セットにわたって検証された。
• 性能比較: 反復回数 (IT) および CPU 時間において、提案された ME-GRBK、ME-RGRBK、および ME-MWRBK は、ME-RBK 法を一貫して上回った。
  • フル列/行ランクのシステムでは、行列セットと手法に応じて、約 2 倍から 13 倍の高速化が見られた。
  • ランク不足のシステムでは、1.35 倍から 4.29 倍の高速化が見られた。
  • ME-MWRBK（決定論的）が一般に最も高い高速化を達成し、ME-RGRBK と ME-GRBK がそれに僅差で続いた。
• カラー画像復元への適用: 手法は、$B = AXA_c^T + E$ とモデル化されたカラー画像復元（デブラーリング）に適用された。テスト画像（"face", "bird", "mandril", "barbara"）を用いた結果、提案手法は ME-RBK と比較して有意に高いピーク信号対雑音比 (PSNR) および構造類似性指数 (SSIM) を達成した。例えば、"face" 画像において、ME-RBK の PSNR は 27.02 であったのに対し、ME-MWRBK は 33.72 を達成した。

意義
本論文は、提案された手法が、既存のランダム化ブロック・カチャルツ法と比較して、大規模な行列方程式 $AXB=C$ を解くためのより効率的かつ効果的なアプローチを提供すると主張している。強欲な選択戦略と決定論的なバリアントを導入することにより、著者らは理論的および数値的に優れた収束率を実証している。カラー画像復元への適用成功は、大規模なデータとストレージ制約が重要な要素となる、実世界の工学問題におけるこれらのアルゴリズムの実用的な有用性を裏付けている。本研究は、カチャルツ型の手法の適用範囲を、線形システムから一般的な行列方程式へと拡張するものである。