The double splitting iteration method for solving the large indefinite least squares problem

技術的概要：大規模不定最小二乗問題に対する二重分割反復法

問題定義
本論文は、不定二次形式 $(b - Ax)^T J (b - Ax)$ の最小化として定式化される、大規模不定最小二乗（ILS）問題に関連する計算上の課題に取り組む。ここで、$A \in \mathbb{R}^{m \times n}$ は大規模な疎行列、$b \in \mathbb{R}^m$ であり、$J = \text{diag}(I_p, -I_q)$ は $p+q=m$ である署名行列である。$pq > 0$の場合、この問題はヘッセ行列が正定値ではない正規方程式$A^T J A x = A^T J b$を導く。小規模な密行列問題に対しては直接法が存在するが、大規模システムに対しては反復スキームが好まれる。この問題に対する既存の最先端の反復ソルバーは、主に係数行列$A^T J A = M - N$ の「単一分割」戦略に依存しており、分割ベース（SP）法、一般化 SP（GSP）法、および交互方向陰的（ADI）法などがその例である。

手法
著者らは、新しい「二重分割（DS）」反復法を提案する。係数行列を 2 つの部分（$M - N$）に分解する従来のアプローチとは異なり、この手法は 3 つの部分への分解を利用する：
$$A^T J A = P - R - S$$
ここで、$P$ は非特異行列である。GSP 法の構造に触発され、著者らは分割 $A = [A_1; A_2]$ に基づいて特定の行列を定義する：

• $P = \alpha I + A_1^T A_1$（対称正定値、SPD）
• $R = A_2^T A_2$（対称）
• $S = \alpha I$（対称）
  ただし、$\alpha > 0$ は与えられたパラメータである。

この分解は、2 段階定常反復スキームへと導く：
$$x_{k+1} = P^{-1} R x_k + P^{-1} S x_{k-1} + P^{-1} A^T J b$$
この定式化は、2 つの直前の反復値（$x_k$ および $x_{k-1}$）からの情報を組み込んでおり、SP および GSP 法の 1 段階的な性質と区別される。このスキームの収束性は、関連するブロック反復行列 $W$ のスペクトル半径 $\rho(W)$ を調べることで分析される。著者らは $W$ の固有値 $\lambda$ に対するスカラー二次方程式を導出し、二次方程式の根に関する補題を適用して、すべての $\alpha > 0$ に対して $|\lambda| < 1$ であることを証明する。

主要な貢献

1. 新規反復フレームワーク：本論文は、ILS 問題から生じる正規方程式に特化した具体的な二重分割戦略を導入し、支配的な単一分割パラダイムに対する明確な代替案を提供する。
2. 無条件収束証明：著者らは厳密なスペクトル解析を提供し、提案された DS 反復法が任意の正のパラメータ $\alpha$ に対して無条件に収束することを示す。この結果は、先行文献に見られるエルミート正定値行列に対する既存の収束基準と関連付けることで、さらに文脈化されている。
3. アルゴリズム実装：SPD 行列 $P$ の逆行列計算にコレスキー分解を使用することを含む計算手順を概説する、詳細なアルゴリズム（アルゴリズム 2.1）が提示されている。

数値結果
DS 法の性能を SP、GSP、および ADI 法と比較評価するために、2 つの数値実験が実施された：

• 例 3.1（密行列）：ランダムな大規模密行列を用い、DS 法は異なる次元（$m$ は最大 54,000）でテストされた。最適パラメータ $\alpha=1$ を用いた場合、DS 法は正確に2 反復で収束した。SP および GSP も 1 反復で収束したが、DS 法は CPU 時間を著しく短縮した（例：$m=51,000$ の場合、GSP が約 75 秒であるのに対し、DS 法は約 4.8 秒）。
• 例 3.2（疎行列）：総最小二乗問題に由来する行列を用い、DS 法は疎構造でテストされた。最適パラメータ $\alpha=10^{-4}$ を用いた場合、DS 法は再び2 反復で収束した。これは、テストされたすべてのサイズ（最大 $m=8,192$）において計算時間において一貫して単一分割法を上回り、問題規模が増大しても卓越した効率性を示した。

意義と主張
本論文は、提案された二重分割反復パラダイムが、従来の単一分割アプローチに対する建設的な改善を提供すると主張する。主な意義は、大規模 ILS 問題に対して高速な収束速度（CPU 時間における）と頑健性を達成する手法の能力にある。著者らは、この手法が 2 つの直前の反復値を必要とするものの、この歴史的情報の組み込みにより、単一ステップの SP、GSP、および ADI 法と比較して計算コストを大幅に削減できることを強調している。この研究は、二重分割に基づく反復法に関する将来の研究に対する方法論的参考文献を提供し、適応的パラメータ選択や他の種類的不定線形システムへの潜在的な拡張を示唆している。