技術要約：行列方程式 $AXB = C$ に対する決定論的およびランダム化カッツマルツ法

問題設定

本論文は、以下の形式の整合的な線形行列方程式の解法を取り扱っている：
$$AXB = C$$
ここで、$A \in \mathbb{R}^{m \times p}$、$B \in \mathbb{R}^{q \times n}$、$C \in \mathbb{R}^{m \times n}$ である。目的は $X \in \mathbb{R}^{p \times q}$ を求めることである。この方程式は、画像処理、制御理論、コンピュータビジョンを含む様々な工学応用において発生する。強調されている具体的な応用例は、ノイズのないカラー画像の復元に関するフォワードモデルであり、$AXA_c^T = C$（ここで $A$ はチャネル内ブラーリング、$A_c$ はチャネル間ブラーリングを表す）として表現される。

著者らは、これらの方程式を解くための直接的な手法は、計算量が3乗のオーダー（cubic complexity）であり、解が一意でない場合やノイズが存在する場合に失敗する可能性があると指摘している。既存の反復法（勾配ベースの反復法（GI）など）は存在するものの、多くの場合、各反復において係数行列全体を保持しアクセスする必要があり、高い計算コストを招く。本論文は、一度の反復で $A$ の1行のみにアクセスする**行作用法（row-action methods）**に焦 نیزしており、これはメモリ利用効率とノイズに対する堅牢性の面で利点を持つ。

手法

本論文は、線形システム $Ax=b$に対して伝統的に用いられるカッツマルツ型の手法を、行列方程式$AXB=C$ へと拡張している。提案された手法は、決定論的な巡回型バリアントと、ランダム化/貪欲（greedy）バリアントに分類される。

1. ブロック・カッツマルツ (BK) 法

著者らはまず、決定論的な巡回型バリアントであるブロック・カッツマルツ (BK) 法を提案する。方程式をスカラーの部分系へと分解する従来の手法とは異なり、BK法は行列 $B$ 全体を利用しながら、$A$ の1行（および対応する $C$ の行）を一度に処理する。

• 一般BK (アルゴリズム2): あらゆるサイズの $B$ に適用可能である。$A$ の第 $i_k$ 行に基づいたランク1更新を用いて $X$ を更新する。著者らは、$0 < \alpha < \|B\|^{-2}$ である限り、任意の初期値 $X_0$ に対して特定の解 $X^*_0 = A^+CB^+ + X_0 - A^+AX_0BB^+$ に収束することを証明している。
• フル列ランクを持つBK (アルゴリズム3): $B$ がフル列ランクを持つ場合、QR分解 ($B=QR$) を通じて方程式は$AXQ = \tilde{C}$ へと変換される。これにより、手法の完全な1サイクル（スイープ）に関する簡潔な行列公式の導出が可能となる。
• フル行ランクを持つBK (アルゴリズム4): $B$ がフル行ランクを持つ場合、方程式は $AX = \hat{C}$ として再定式化される。これは複数の右辺を持つ線形システムとして扱われる。著者らはスイープ公式を導出し、複数の右辺を持つ標準的なカッツマルツ法と同様の収束特性を証明している。
• 等価性: 命題3.7は、$B$ が正則であるとき、アルゴリズム3と4が等価であることを確立している。

2. 貪欲およびランダム化バリアント

BKの枠組みに基づき、著者らは線形システムから得られた貪欲およびランダム化戦略を行列方程式の文脈へと拡張している。

• 貪欲ランダム化ブロック・カッツマルツ (GRBK, アルゴリズム5): 最大重み付き残差ノルムと平均重み付き残差ノルムの両方を含む閾値に基づいて行を選択することで、GRK法を拡張したものである。
• 緩和貪欲ランダム化ブロック・カッツマルツ (RGRBK, アルゴリズム6): 最大残差戦略と平均残差戦略のバランスをとるための調整可能なパラメータ $\theta \in [0, 1]$ を導入している。
  • $\theta = 1/2$ のとき、GRBKと一致する。
  • $\theta = 1$ のとき、決定論的なMWRBKと一致する。
• 最大重み付き残差ブロック・カッツマルツ (MWRBK, アルゴリズム7): 各ステップで最大の重み付き残差を持つ行を選択する決定論的手法である。

収束解析

本論文は、提案されたすべての手法に対して厳密な収束解析を提供している。

• BK法: 解 $X^*_0$ （または $X_0=0$ かつ特定の範囲条件を満たす場合の最小ノルム解 $X^* = A^+CB^+$）への収束が証明されている。
• GRBK, RGRBK, MWRBK: 初期行列がゼロの場合、一意の最小ノルム解 $X^*$ への期待値としての収束が証明されている。
• 収束係数: 著者らは収束係数の上界を導出している。貪欲/ランダム化バリアント（GRBK, RGRBK, MWRBK）の上界は、標準的なランダム化ブロック・カッツマルツ (RBK) 法の境界よりも小さくなるか、あるいは等しいことを示している。具体的には、RGRBKの上界は $\theta$ が増加するにつれて減少することを示しており、これは決定論的なMWRBK ($\theta=1$) が最もタイトな理論的境界を持つことを示唆している。
• 最適ステップサイズ: 解析によれば、緩和パラメータ $\alpha = \|B\|^{-2}$ のときに収束係数の上界が最小となる。

主な貢献

1. カッツマルツ法の拡張: 決定論的な巡回型、貪欲ランダム化、および最大重み付き残差のカッツマルツ戦略を、一般的な行列方程式 $AXB=C$ へと見事に拡張した。
2. 新しいブロック定式化: $B$ がフル列ランクまたはフル行ランクを持つ場合のための特定の定式化（アルゴリズム3および4）を導入し、完全なスイープに関するエレガントな行列公式の導出を可能にした。
3. 理論的保証: 提案されたすべての手法について、収束特性（最小ノルム解への収束条件や明示的な誤差界を含む）が確立されている。
4. 複雑度解析: 提案された手法は、1反復あたりの計算量が二次式（$O(q(p+n))$ など）であり、GI法による3乗の計算量よりも大幅に低いことが示されている。
5. 画像復元への応用: 提案された手法をノイズのないカラー画像復元モデルに適用し、その実用性を実証した。

数値結果

著者らは、数値実験を通じて理論的知見を検証している。

• 合成データ: 様々な行列構成（過決定、不足決定、ランク不足）を用いたテストにより、BK法の線形漸近収束が確認された。
• RBKとの比較: RBK、GRBK、RGRBK、およびMWRBKを比較したテストでは、貪欲バリアントは（残差計算によるコストがわずかに高いにもかかわらず）標準的なRBKよりも少ない反復回数と総CPU時間を一貫して必要とした。
• 画像復元: ブラーのかかったカラー画像（顔、鳥、マンドリル）の復元に適用した結果、提案手法（特にMWRBKおよびRGRBK）は、総計算時間の面でGI法を凌駕し、反復回数の面では標準的なBKおよびRBKを上回った。
• 性能傾向: 結果は、MWRBK法（決定論的、$\theta=1$）が、反復回数と実行時間の両面で最も速い収束を実現することが多く、これは収束境界が $\theta$ とともに改善するという理論的予測を裏付けている。

意義と主張

本論文は、提案されたカッツマルツ型の手法が、線形行列方程式に対する既存の反復ソルバーに代わる計算効率の高い選択肢となることを主張している。

• 効率性: ランク1更新と行作用戦略を利用することで、提案手法はGI法で必要とされる高価な行列・行列積を回避し、計算量を3乗から2乗へと低減させている。
• 堅牢性: 行作用の性質により、大規模な問題に適しており、潜在的にノイズに対しても堅牢である（ただし、本論文はノイズのないケースに焦点を当てている）。
• 貪欲戦略の優位性: 数値実験は、純粋なランダム選択や巡回選択と比較して、貪欲選択戦略（GRBK, RGRBK, MWRBK）を組み込むことが収束を大幅に加速させることを示唆しており、決定論的なMWRBKが反復回数と実行時間の観点から最も魅力的な選択肢として浮上している。
• 理論的洞察: $B$ の特定のランク条件に対するスイープ公式の導出は、ブロック・カッツマルツ法の挙動に関する深い理論的洞察を提供している。

著者らは、BK法が行選択の効果を理解する上で価値がある一方で、貪欲な拡張（特にMWRBK）が一貫して実用面でより速い収束を実現することを結論づけている。また、本研究はノイズのない方程式に限定されていることを認め、ノイズを含む右辺に対してこれらの手法を適用することが今後の研究課題であるとしている。