Accelerating operator Sinkhorn iteration with overrelaxation

技術的概要：過緩和による演算子シンクホーン反復の加速

問題定義
本論文は、与えられた行列の集合 $A_1, \dots, A_k \in \mathbb{R}^{m \times n}$ を「スケーリングされた」形式 $\bar{A}_i = L A_i R^\top$ へと変換する、可逆な正方行列 $L \in GL_m(\mathbb{R})$ および $R \in GL_n(\mathbb{R})$ を求める「演算子スケーリング問題」を取り扱います。ここで目指すのは、以下の 2 つの条件を同時に満たすことです：

1. $\sum_{i=1}^k \bar{A}_i \bar{A}_i^\top = \frac{1}{m} I_m$
2. $\sum_{i=1}^k \bar{A}_i^\top \bar{A}_i = \frac{1}{n} I_n$

この問題は、古典的な行列スケーリングを一般化したものであり、非可換多項式恒等式テスト、不変量理論、信号処理などの応用分野で生じます。標準的な解法は、交互固定点アルゴリズムである**演算子シンクホーン反復（OSI）です。OSI は特定の条件下で大域的に収束しますが、その収束は遅い場合があります。著者らは、線形システムでは確立されているが、この特定の非線形演算子スケーリングの文脈ではあまり研究されていない逐次過緩和法（SOR）**を用いて、このプロセスを加速することを目指します。

手法
著者らは、正定値（PD）行列の錐体上での交互最小化として問題を解釈する、演算子シンクホーン反復に対する 3 つの異なる過緩和バリアントを提案します。

1. ユークリッド過緩和（PD-OR）： このアプローチは、反復点 $(X_t, Y_t)$（ここで $X_t = L_t^\top L_t$、$Y_t = R_t^\top R_t$）に標準的なアフィン結合を適用します。更新則は $(1-\omega)X_t + \omega S_1(Y_t)$ であり、ここで $S_1$ はスケーリング写像です。計算が単純である一方、緩和パラメータ $\omega > 1$ の場合、結果として得られる行列が正定値性を保つという理論的保証は欠如しています。
2. 座標変換過緩和（Cholesky-OR）： 反復点が PD 錐体内に留まることを保証するため、著者らは変換された座標空間で過緩和を適用することを提案します。具体的には、PD 行列のコレスキー因子（$L$ および $R$）を利用します。コレスキー因子は線形空間（三角行列）に属するため、アフィン結合が適切に定義され、アルゴリズムに必要な構造を保持します。このバリアントは、数値的に最も効率的であるとされています。
3. 測地線過緩和（Geodesic-OR）： この手法は、ヒルベルト計量によって誘導される PD 錐体の双曲幾何学を尊重します。アフィン結合の代わりに、著者らは演算子幾何平均 $X \#_\omega \tilde{X}$ を用いて測地線に沿った更新を定義します。このアプローチは理論的に堅牢であり、問題の軌道等変性を保持し、反復点が PD 錐体内に留まることを保証します。

主要な貢献と理論的結果

• 局所収束解析： 著者らは、固定点の近くにおいて、これら 3 つの過緩和バリアントは1 次同値であることを示します。反復を線形化し、軌道等変性（解の軌道のスケーリングに対する不変性）を利用することで、漸近的な局所収束率の統一式を導出します。

  • 線形化された SOR 反復のスペクトル半径が、古典的なヤングの SOR 定理のパターンに従うことを確立します。
  • 標準的な（緩和されていない）演算子シンクホーン反復のスペクトル半径 $\beta$ に依存する漸近的に最適な緩和パラメータ $\omega_{opt}$ の式を提供します：$\omega_{opt} = \frac{2}{1 + \sqrt{1-\beta^2}}$。
  • この解析は、基底となる測地線凸目的関数のヘッセ行列が、スケーリング軌道に対応する 1 次元の零空間を持つという事実に依存しており、著者らはこれを厳密に証明しています。

• 測地線 SOR の大域収束： 非線形 SOR の大域収束は一般的に困難ですが、著者らは特定の $\omega$ の範囲内においてGeodesic-ORバリアントの大域収束を証明します。

  • ヒルベルト計量と標準シンクホーン反復の縮約性を利用します。
  • 新たな貢献として、PD 行列上のヒルベルト計量に対する計量不等式（補題 3.4）が提示されます。これは、測地線上の点と第 3 の点との距離を評価するものです。この不等式により、縮約性の結果を過緩和の場合に拡張することが可能となり、$\omega \in (0, \frac{2}{1+\sqrt{\Lambda_1 \Lambda_2}})$ における収束が証明されます。ここで $\Lambda_1, \Lambda_2$ はスケーリング写像のリプシッツ定数です。

• 適応的パラメータ選択： 最適な $\omega$ は、特定のインスタンスの未知の収束率に依存することを認識し、著者らは適応的な戦略を採用します。標準的な手法の初期反復から収束率 $\beta$ を推定し、$\omega$ を $\omega_{opt}$ に動的に更新します。これは行列スケーリングに関する最近の研究から適応された手法です。

数値結果
著者らは 2 種類のインスタンスで実験を行いました：

1. フレームスケーリング： この応用において、SOR 手法（特に Cholesky-OR と Geodesic-OR）は、標準 OSI よりも著しく速い収束を示しました。これらの手法は、OSI が $10^{-8}$ に到達するために必要な反復回数の約半分程度で、$10^{-14}$ 程度の誤差を達成しました。観測された収束率は理論予測と密接に一致しました。
2. 条件の悪い演算子： ヒルベルト行列を入力として使用したところ、SOR は初期段階で収束を加速しましたが、標準 OSI（$10^{-11}$）と比較して低い精度（$10^{-6}$）で停滞することが観察されました。その原因は、「半スケーリング」された中間行列に基づく SOR バリアントは、標準 OSI における完全な交互更新ほどには、初期の条件悪化を十分に補償できないという点にあると著者らは帰結しています。

意義と主張
本論文は、行列スケーリングに関する既存の結果（特に Thibault らおよび Lehmann らの研究）を、より複雑な演算子スケーリングの設定に一般化することを主張します。

• 理論的洞察： 著者らは、群等変性に起因するヘッセ行列の非正定値性を扱う厳密な局所収束解析が、演算子スケーリング問題の構造に対する新たな洞察を提供することを強調しています。
• 実用的有用性： 数値実験は、条件の良いシナリオ（フレームスケーリングなど）において、過緩和が計算オーバーヘッドをほとんど増やすことなく、演算子スケーリングを数桁加速し得ることを示唆しています。特にコレスキーベースのアプローチを使用する場合に顕著です。
• 限界： 著者らは控えめに、測地線バージョンの大域収束証明がカバーする $\omega$ の範囲は、おそらく過度に悲観的（しばしば 1 に近い）であり、現在の SOR 実装は条件の悪い入力において数値精度が低下する可能性があることを認めています。より広い範囲の $\omega$ に対する大域収束の確立と、条件の悪い問題における精度の向上を、今後の課題として挙げています。