A fast solver for ill-conditioned linear systems using randomized stable solutions of its blocks

問題提起
本論文は、 $A \in \mathbb{R}^{m \times n}$ および $b \in \mathbb{R}^{m \times 1}$ である一貫性のある線形方程式系 $Ax = b$ を解く際の課題を取り上げている。主な焦点は、スパースなシステム、高密度な最小二乗問題、および著しく過決定または不足決定であるケースを含む、極めて条件数の大きい（ill-conditioned）システムである。著者らは、標準的な反復法（GMRESなど）がこれらのシステムにおいて苦戦することが多い理由として、残差ノルムの最小化が必ずしも不良条件問題における相対誤差の収束を保証するわけではないことを挙げている。さらに、従来のプリコンディショニング技術（ILU、Jacobiなど）は、非常に大きな条件数を持つ行列に適用した場合、数値的不安定性、ピボットの崩壊、あるいは過度なフィルイン（fill-in）に苦しむことがあり、堅牢な加速が最も必要とされる場面でこそ失敗することが多い。

手法
著者らは、Regularized Orthogonality and Residual based Block-Kaczmarz (ROR-BK) と呼ばれる強化されたアルゴリズムを提案している。この手法はランダム化ブロック・カチャルツ（block-Kaczmarz）の枠組みに基づいているが、安定性と収束性を向上させるために3つの具体的な強化策を導入している：

1. 動的な残差ベースの集約（Dynamic Residual-Based Aggregation）: 固定されたブロックに依存する代わりに、本手法は各反復において現在の残差ベクトルに基づいて方程式の部分集合を動的に集約する。具体的には、残差の二乗への寄与が最も大きい行を選択してブロックを形成し、各ステップで残差ノルムをより効果的に最小化することを目指す。
2. 効果的な相互直交性サンプリング（Effective Mutual Orthogonality Sampling）: 本手法は、ブロックペア間の直交性の概念（Simple Orthogonal Block-KaczmarzまたはSOBKで使用されるもの）を、単一のブロックと「他のすべてのブロック」との間の「効果的な直交性」へと一般化している。ブロックの重心間の実効的な角度の余弦を表す対称行列 $C$ が計算される。そして、システム全体に対する累積的な直交性が高いブロックを優先する分布に基づいて、確率的にブロックがサンプリングされる。
3. 正則化（Regularization）: ブロックがランク不足であったり、条件数が悪かったりする場合の数値的安定性を確保するため、ブロック更新には正則化された疑似逆行列を使用する。標準的なムーア・ペンローズ逆行列 $B^\dagger = B^T(BB^T)^{-1}$ の代わりに、本手法は正則化形式 $B^T(BB^T + \mu I)^{-1}$ を使用する。これは、微小な正の定数 $\mu$ を用いた確率的近接点アルゴリズム（stochastic proximal point algorithm）として解釈される。

アルゴリズムは、直交性サンプリングされたブロックを用いた更新と、残差ベースの動的ブロックを用いた更新を交互に行うことで動作する。著者らは、この手法がフレキシブルGMRES（FAB-GMRES）ソルバーの内部反復（プリコンディショナー）として機能することも示している。

主要な貢献

• アルゴリズムの革新性: 残差ベースの動的ブロック選択、グローバルな直交性認識サンプリング、およびTikhonov型の正則化をブロック・カチャルツの枠組みの中に組み合わせたROR-BKの導入。
• 理論的分析: 本手法がブロックが数値的にランク不足であっても安定した収束を達成することを示す収束解析（定理2.3および2.4）を提供している。誤差の減少が正則化パラメータ $\mu$ とブロック行列の最小の非ゼロ固有値によって制限されることを確立している。さらに定理2.4は、最大残差に基づいてブロックを選択することが、誤差の上限および下限を改善することを論じている。
• プリコンディショニング戦略: 明示的で、潜在的に不安定な外部プリコンディショナーを必要とせずに、不良条件システムを加速するための、ROR-BKをGMRESのプレソルバーまたは内部反復として使用する提案。

結果
著者らは、ROR-BKを以下の手法と比較する広範な数値実験を行った：

• ランダム化ソルバー: Simple Orthogonal Block-Kaczmarz (SOBK) および Tail Averaged Regularized Block Kaczmarz (TA-ReBlocK-U)。
• クリロフ部分空間ソルバー: LSQR および Jacobi、ILU、Robust Incomplete Factorization (RIF) などのプリコンディショナを備えた様々なGMRESバリアント (AB/BA-GMRES)。

性能に関する知見:

• 速度と反復回数: 幅広いテスト行列（University of Floridaコレクションからのスパース行列およびランダム生成された高密度行列を含む）において、ROR-BKはSOBKおよびTA-ReBlocK-Uよりも一貫して少ない反復回数と少ないCPU時間を要した。CPU時間の面で、SOBKに対して1.23倍から5.17倍、TA-ReBlocK-Uに対して最大49.08倍の高速化を実現した。
• 不良条件システム: 条件数が $10^{20}$ に達する高度に不良条件なシナリオにおいて、多くのクリロフソルバーおよびそのプリコンディショニング版は、反復制限内に収束できなかったか、あるいは大きな相対誤差を生じた。ROR-BKはこれらのケースでも正常に収束し、多くの場合、より低い相対誤差を達成した。
• 実世界への応用: 本手法は、ノイズを含むデータや深刻に不足決定なシステムを含む画像再構成問題（平行線ビームトモグラフィおよびMRI）に対してテストされた。ROR-BKは、特に他のソルバーが不安定性や失敗に陥るシナリオにおいて、ピーク信号対雑音比（PSNR）および構造的類似性指数（SSIM）の観点から優れた性能を示した。

意義と主張
本論文は、行列 $A$ が不良条件である線形システムを解くための有望な代替案としてROR-BKを提示しており、明示的なプリコンディショニングを必要とせずに効率的な近似を実現すると主張している。著者らは、プリコンディショナは行列の条件数を下げることを目的としているが、問題自体の条件数を下げるわけではなく、むしろ数値的不安定性を導入する場合があると考えている。システムをブロックに分割し、効果的な直交性と正則化を利用することで、ROR-BKは共分散を持つ方程式を、潜在的に良好な条件を持つ部分問題へと分散させる。

著者らは、本手法を正方行列、過決定、および不足決定システムのための堅牢なソルバーとして位置づけている。さらに、標準的なプリコンディショニング技術がピボットの崩壊やランク不足により失敗する場合に、他の反復法（特にGMRES）を加速するためのプレソルバーまたは内部反復としての有用性を提案している。本研究は、残差ベースのダイナミクスと直交性サンプリングの組み合わせが、高条件数の線形システムにおいて高速かつ安定した収束を実現するための、シンプルかつ効果的なメカニズムを提供することを強調している。