Rank-one Riemannian Subspace Descent for Nonlinear Matrix Equations

問題設定
本論文は、制御理論、動的計画法、および確率的フィルタリングにおいて発生する非線形行列方程式（NME）の、対称正定値（SPD）解を見つける際の計算上の課題に対処している。これらの方程式には、連続時間および離散時間の代数リッカチ方程式（CARE/DARE）やリアプノフ方程式が含まれ、多くの場合、$G(X, A, C, \dots) = 0$ となる $X \in \mathcal{P}_n$ を見つける問題として定式化される。これは、非線形最小二乗問題 $\min_{X \in \mathcal{P}_n} \|G(X, A, C, \dots)\|_F^2$ として再構成される。

主なボトルネックはスケーラビリティである。高密度な行列方程式に対する標準的なソルバーは、通常、1イテレーションあたり $O(n^3)$ の浮動小数点演算（flops）を要する。$O(n^2)$ の手法も存在するが、それらは一般に、疎性や低ランク解の仮定に依存しており、一般的な高密度問題には当てはまらない。その結果、状態次元が大きい場合（例：$n=10,000$）、標準的な高密度ソルバーは時間およびメモリの制約により計算不能となる。

手法：ランク1・リーマン部分空間降下法 (R1RSD)
著者らは、アフィン不変リーマン計量を備えたSPD行列の多様体（$\mathcal{P}_n$）上で直接動作する、ランク1・リーマン部分空間降下法（R1RSD）を提案している。

1. スペクトル分解による部分空間選択： 固定された座標部分空間への勾配投影を用いる従来の部分空間降下法とは異なり、R1RSDは、変換されたリーマン勾配をランク1の固有成分の和へと分解する。アルゴリズムは、最も支配的な降下方向を定義するために、最も大きな固有値の絶対値に対応する支配的固有成分を選択する。
2. 方向特定のためのべき乗法： $O(n^3)$ のフル固有分解のコストを回避するため、支配的な成分はべき乗法を用いて特定される。著者らは、支配的な方向を効果的に近似するために、少数のべき乗反復（具体的には $r = O(\log n)$）で十分であることを示している。
3. ランク1更新と計算量： 更新則は、ランク1行列の行列指数関数を用いて導出されており、これは閉形式のランク1更新を許容する。$X_t$ のチョレスキー因子 $B_t$ とその逆行列を、ウッドベリーの公式と cholupdate を用いたランク1更新によって維持することで、アルゴリズムは高密度な行列積を回避する。
4. 勾配・ベクトル積： 標準的な行列演算（加算、乗算、逆行列、対数行列式）の合成として定義される目的関数に対して、勾配・ベクトル積 $\nabla f(X)v$ は、計算グラフを辿り、行列・ベクトル積を適用することで $O(n^2)$ の時間で計算可能であり、フル勾配行列の明示的な形成を回避する。
5. ステップサイズの選択： ランク1の構造により、多くのケースで追加コストを最小限に抑えつつ正確なラインサーチが可能であるが、固定ステップサイズやアルモリオ（Armijo）ステップサイズも利用可能である。

主な貢献

• アルゴリズムの革新性： 本論文は、固定された部分空間への投影を用いる手法とは異なり、リーマン勾配から導出された、注意深く選択された単一のランク1方向に対して反復を更新する手法を導入している。
• 計算量の削減： 提案手法は、1イテレーションあたり $O(n^2 \log n)$ の算術コスト（各 $O(n^2)$ の $r$ 回のべき乗反復によって支配される）を達成し、標準的な仮定の下で $O(n)$ 回のイテレーションを必要とする。これは、$O(n^2)$ の毎イテレーション・コストを持つが合計 $O(n^2)$ 回のイテレーションを必要とする最先端の部分空間降下法（例：[43]）や、1イテレーションあたり $O(n^3)$ を要する標準的なソルバーとは対照的である。
• 理論的保証： 著者らは、測地線的に滑らかな（非凸）ケースおよび測地線的に強凸なケースの両方について収束解析を提供している。一般の場合には $O(n)$ のイテレーション境界を確立し、強凸ケースでは改善された境界を確立しており、総演算回数はそれぞれ $O(n^3 \log n)$ および $O(n^3 \kappa \log n)$ である。
• 実践的な実装： 本研究には、効率性を実現するために低ランク更新を利用した公開可能なMATLAB実装が含まれており、これにより $O(n^2)$ の毎イテレーション計算量が実際に実現されている。

数値結果
著者らは、R1RSDを、MATLABの icare、構造保存倍増アルゴリズム（SDA）、およびBurer-Monteiro因子化に基づく座標（BMFC）部分空間降下法を含む最先端のソルバーと比較検証している。

• スケーラビリティ： $n=10,000$ までの次元におけるCARE、DARE、およびその他のNMEに関する実験では、標準的なソルバー（SDA、icare）およびBMFCは、大きな $n$ に対して解を返さないか、メモリ不足になることが示された。一方、R1RSDはこれらのインスタンスを正常に解決した。
• 効率性： $n=100$ において、R1RSDはBMFCと比較して、有意に少ないイテレーション数（1〜2桁少ない）で収束した。
• 堅牢性： アルゴリズムは、最適なステップサイズが大きく変動する場合でも効果的であり、貪欲な部分空間選択（約10回のべき乗反復を使用）は、収束速度と毎イテレーションのコストとの間で強力なバランスを提供している。

意義と主張
本論文は、R1RSDが、従来の高密度ソルバーが困難となる高次元かつ高密度なSPD制約付き行列方程式に対する実用的なアプローチを提供すると主張している。毎イテレーションの計算量を $O(n^2)$ に削減しつつ、妥当なイテレーション回数を維持することで、本手法は理論的なスケーラビリティと大規模な制御問題への実用的な適用可能性の間の溝を埋めるものである。著者らは、このアプローチが、特に、毎ステップでリッカチ方程式を解くことが従来は不可能であった、時変および適応制御のシナリオ（状態依存リッカチ方程式の枠組みなど）において特に重要であると述べている。本研究は、ランク1の多様体更新が、解や係数の疎性または低ランクの仮定に依存することなく、標準的なソルバーが対処できない問題を効果的に扱えることを強調している。