Randomized Methods for Kernelized DMD

技術要約：カーネル化DMDのためのランダム化手法

問題提起
動的モード分解（Dynamic Mode Decomposition: DMD）は、非線形システムの逐次的なスナップショットから支配的なダイナミクスを抽出するために用いられるデータ駆動型手法である。しかし、高次元の状態空間（$N$）および大量のスナップショット（$M$）を持つ大規模なデータセットに対してDMDを適用する場合、重大な計算上のボトルネックが生じる。カーネルトリックを利用することで、カーネル化DMD（Kernelized DMD: KDMD）は大きな$N$の問題を軽減するが、新たな制約を導入する。すなわち、アルゴリズムが2つの$M \times M$固有値問題を解く必要があることである。これにより、スナップショット数に関するスケーリングが悪化し、長い軌跡データへのKDMDの適用性が制限される。Random Fourier Features (RFF) や oASIS アルゴリズムのような既存のランダム化アプローチは、これに対処しようとしているが、収束速度が遅い、あるいは数値的不安定性を抱えている。具体的には、oASISは対角ピボット（diagonal pivoting）に依存しており、特定の反例において正確な近似を返すことができず、ピボット付き部分的部分コレスキー分解（pivoted partial Cholesky factorization）と比較して数値的に不安定である。

手法
本論文は、計算を加速させつつ数値的安定性を高めるために、RPCholeskyアルゴリズム（Randomly Pivoted Partial Cholesky）をKDMDのフレームワークに統合することを提案している。

1. RPCholeskyによるカーネル近似： フルサイズの$M \times M$グラム行列 $G$ を計算して関連する固有値問題を解く代わりに、著者らはRPCholeskyを利用して低ランク近似 $G \approx FF^*$ を生成する。この手法は、純粋な強欲な対角ピボット戦略ではなく、残差行列の対角要素から導出された確率分布に基づいてピボット指数 $I = \{i_1, \dots, i_S\}$ を選択する。これにより、「搾取（exploitation）」としての大きな対角要素の利用と、「探索（exploration）」としての小さな要素の利用のバランスをとっている。
2. アルゴリズムの統合： 提案されているランダムサンプリングを用いたKDMD（アルゴリズム2）は、$G$ のフル固有値分解を、より小さな $S \times S$ 行列 $F^*F$ の固有値分解に置き換える。得られた因子を用いて、縮小されたカーネル行列 $\hat{K}$ を構築し、DMDモードおよび固有関数を計算する。
3. データ駆動型残差： 本手法の重要な構成要素は、ランダム化設定のための特定のデータ駆動型残差公式の導出である。SVDベースのDMDで使用される標準的な残差計算は、ランダム化KDMDの出力には直接適用できないため、著者らはRPCholeskyの実行中に得られたピボット選択情報（$A[:, I]$ および $G[:, I]$）を利用する新しい残差 $r(i)$ （式7）を導出している。これにより、再構成品質に基づいた支配的モードのソートと選択が可能になる。
4. 計算の最適化： 著者らは、逐次的なデータ行列 $X$ と $Y$ に対して、カーネル行列は単一のより大きな行列 $D = [X, Y]$ から組み立て可能であると指摘している。これにより、RPCholeskyアルゴリズムを $D$ に対して一度実行するだけで、 $G$ と $A$ の必要なサブブロックを抽出することができ、これらの行列のフルアセンブリという高コストな作業を回避できる。

主な貢献

• アルゴリズムの提案： 本論文は、KDMDへのRPCholeskyアルゴリズムの適用を紹介しており、oASISアルゴリズムや対角ピボットを用いたNyström近似に対する安定した代替案を提供している。
• 安定性と順序付け： 著者らは、RPCholeskyが従来のランダム化KDMD手法よりも優れた安定性の保証を提供することを実証している。決定的なのは、導出されたデータ駆動型残差が、DMDモードの有意義な順序付けを可能にすることであり、これはoASISベースのピボッティングでは一貫性がないか、あるいは不安定であった特徴である。
• 計算量分析： 本論文は、提案されたランダム化KDMDアプローチが、コストを $O(M^3)$ （標準的なKDMDの場合）から $O(SMN + S^2M + S^3)$ （ここで $S$ はランダムサンプル数）へと削減することを示す計算量分析を提供している。これにより、 $M$ が大きいデータセットの処理が可能となる。
• 残差定式化： ランダム化KDMDモードのための特定の残差指標の導出により、フルカーネル行列を必要とせずに支配的なダイナミクスを選択することを可能にしている。

結果
提案手法の有効性は、3つのベンチマーク問題によって評価された：

1. 円柱周囲の流体： 層流シミュレーション（$N=89351, M=150$）からの圧力データを用い、RPCholeskyベースのKDMDは、標準的なDMDおよびKDMDと視覚的に類似したモードを生成し、残差も標準的なKDMDと同等であった。対照的に、oASIS法はerratic（不安定）な残差を生じ、同じ挙動を反映できなかったため、効果的なモードのソートを妨げた。
2. 非強制ダフィン方程式： 合成データセット（$10000 \times 7700$）を用いたストレス・テストでは、サンプル数 $S$ が増加するにつれて、ランダム化KDMDアルゴリズム（RPCholesky、oASIS、およびRFF）がいずれも同程度の相対再構成誤差を達成した。しかし、RPCholesky法はoASISと比較して、モードの順序付けにおいて優れた安定性を示した。計算時間の分析により、すべてのランダム化バリアントが $S$ に対して同様にスケールすることが確認された。
3. 海面温度データセット： 大規模な実世界のデータセット（$2276$スナップショット、$10^6$ データポイント）に適用したところ、RPCholesky KDMDは支配的なモードを特定することに成功した。特筆すべきは、提案アルゴリズムによって生成されたモードが期待される物理的構造（独立した第1モードに続く複素共役対）に従っていた一方で、RFF EDMDアプローチは、このペアリングによる順序付けを生成できなかった点である。

意義
本論文は、RPCholeskyとKDMDの組み合わせが、既存のランダム化カーネル手法における特定の安定性と順序付けの欠点を解決することを主張している。強欲な対角ピボットを適応的なランダムサンプリングに置き換えることで、情報の「搾取」と「探索」のバランスを実現している。主な意義は、フルサイズの $M \times M$ カーネル行列を組み立てたり保持したりすることなく、データ駆動型残差を用いた信頼性の高いモード選択メカニズムを備え、大規模な（$M$ が大きい）データセットを扱うKDMDを可能にした点にある。著者らは、これを大規模なデータ駆動型力学系解析における高速化のための実行可能なツールとして位置づけている。