論文「Stabilizing the Rayleigh–Ritz procedure by randomization」の技術的サマリー

1. 研究の背景と課題

固有値問題において、与えられた部分空間から近似固有対（固有値と固有ベクトル）を抽出することは極めて重要です。Krylov 部分空間法や reduced-basis 法など、多くの数値手法は、真の固有ベクトル $v$ に近い部分空間 $W_\epsilon$ を生成しますが、この部分空間から高精度な近似固有対をどのように抽出するかが鍵となります。

従来の標準的なRayleigh-Ritz 法（RR 法）は、部分空間上の圧縮された行列の固有値問題を解くことで近似固有対を得る手法ですが、以下の重大な安定性の問題を抱えています：

• 収束性の劣化: 対象の固有値が Hermitian 行列の内部固有値（exterior ではない）である場合、Ritz 値の収束が二次から一次に劣化することがあります。
• 収束の失敗: 非エルミート行列や一般化固有値問題（Generalized Eigenvalue Problems）の場合、Ritz 値が収束しない、あるいは Ritz ベクトルが全く精度を失う（発散する）現象が起きることがあります。
• 特異性の問題: 圧縮された行列（または行列のペンシル）が、元の行列が正則であっても、近似的に特異（defective）またはゼロ行列に近づき、数値的に不安定になります。

これらは長年のオープン問題であり、Stewart なども「結果が目的の固有対を近似する保証はない」と指摘しています。

2. 提案手法：ランダム化 Rayleigh-Ritz 法 (RRR)

著者は、この問題を解決するために**ランダム化 Rayleigh-Ritz 法（Randomized Rayleigh-Ritz, RRR）**を提案しました。この手法は、部分空間への射影条件をランダムな行列を用いて緩和（Petrov-Galerkin 条件）することで、安定性を確保します。

アルゴリズムの概要

1. 入力: 行列 $A_0$（または非線形関数 $A(\xi)$）と、正規直交基底 $W_\epsilon$（次元 $m$）。
2. ランダム化: 複素ガウス乱数行列 $\Omega \in \mathbb{C}^{n \times m}$ を生成する。
3. 圧縮固有値問題の求解:
   • 標準 RR 法では $W_\epsilon^H A_0 W_\epsilon y = \mu y$ を解くが、RRR 法では以下の一般化固有値問題を解く：
     $$\Omega^H A_0 W_\epsilon y = \mu \Omega^H W_\epsilon y$$
   • これにより得られる $(\mu, W_\epsilon y)$ を「ランダム化 Ritz 対」と呼ぶ。
4. 値の精緻化（Refinement）:
   • ランダム化 Ritz 値 $\mu$ を、通常の Rayleigh 商（または非線形問題における Rayleigh 汎関数・停留点探索）を用いて $\rho$ に精緻化する。
   • $\rho = \frac{(W_\epsilon y)^H A_0 (W_\epsilon y)}{(W_\epsilon y)^H (W_\epsilon y)}$

非線形固有値問題への拡張

標準的な固有値問題だけでなく、$A(\lambda)v=0$ 形式の非線形固有値問題にも拡張可能です。この場合、圧縮された非線形問題 $B_\epsilon(\xi) = \Omega^H A(\xi) W_\epsilon$ を解き、得られたベクトルを用いて Rayleigh 汎関数または停留点探索（$\frac{d}{d\bar{\rho}}\|A(\rho)W_\epsilon y\|^2 = 0$）を行うことで、高精度な固有値近似を得ます。

3. 主要な理論的貢献と結果

3.1 収束性の保証

RRR 法の最大の特徴は、理想的な射影（$W_\epsilon W_\epsilon^H v$）と同等の収束速度を、高い確率で達成することです。

• ランダム化 Ritz 値: 誤差は $O(\epsilon)$ で収束（$\epsilon$ は部分空間と真の固有ベクトルのなす角）。
• 精緻化された Ritz 値:
  • Hermitian 行列の場合：二次収束 $O(\epsilon^2)$。
  • 非 Hermitian 行列の場合：一次収束 $O(\epsilon)$。
• ランダム化 Ritz ベクトル: 誤差は $O(\epsilon)$ で収束。

これらの結果は、**非漸近的（non-asymptotic）**な確率論的 bound として示されており、対象固有値が単純（simple）であることのみを仮定しています。

3.2 安定化のメカニズム

標準 RR 法が失敗する原因は、圧縮行列 $W_\epsilon^H (A_0 - \lambda I) W_\epsilon$ が特異になることです。一方、RRR 法ではランダム行列 $\Omega$ による圧縮 $\Omega^H (A_0 - \lambda I) W_\epsilon$ を行います。

• ランダム行列は、ゼロ特異値の「単純性（simplicity）」を高い確率で保持します。
• 圧縮された問題の条件数（固有値・固有ベクトル）が、元の行列の条件数と比べて過度に悪化しないことが証明されています（Lemma 3）。
• これにより、標準 RR 法で発生する「Ritz 値の収束劣化」や「Ritz ベクトルの発散」が回避されます。

3.3 既存手法との比較

• Sketched Rayleigh-Ritz: 過剰サンプリング（oversampling）が必要であり、事後評価（a posteriori）に留まります。RRR は過剰サンプリング不要で、事前収束保証（a priori）を持ちます。
• Refined/Harmonic RR: 追加計算（SVD や QR 分解）が必要ですが、一般化・非線形問題に対する収束保証は未解決でした。RRR はこれらに対しても理論的保証を提供します。

4. 数値実験結果

論文では、以下のシナリオで RRR 法の有効性を検証しています。

1. ハミルトニアン系の中立モード（Neutral Modes）:
   • 標準 RR 法では圧縮ペンシルがゼロになり計算不能になるケースにおいて、RRR は安定して動作し、ベクトルは部分空間角度に比例する精度、値は二次収束（または一次収束）を示しました。
2. Butterfly 非線形固有値問題:
   • Hermitian な場合、精緻化された RRR 値が二次収束を示すことを確認。
   • 非 Hermitian な場合、標準 RR 法よりも約 2 桁高い精度を達成しました。
3. 過剰サンプリングの効果:
   • 多くのランダム化アルゴリズム（ランダム化 SVD など）では過剰サンプリングが有効ですが、RRR 法においては過剰サンプリングを行っても収束率の定数項（$1/\sqrt{\delta}$）を改善できず、理論的な bound が鋭い（sharp）ことを示しました。

5. 意義と結論

この論文は、固有値計算における長年の課題であった「部分空間からの安定した固有対抽出」に対して、ランダム化を用いた解決策を提示しました。

• 理論的意義: 標準 RR 法の不安定性を克服し、非漸近的な確率的収束保証を初めて確立しました。特に、一般化固有値問題や非線形固有値問題においても、単純な固有値に対してのみ条件を満たせば、安定した収束が保証される点は画期的です。
• 実用的意義: 追加的な計算コスト（SVD など）を必要とせず、既存の部分空間生成手法（Krylov 法など）と組み合わせるだけで、より信頼性の高い近似解を得ることができます。
• 将来の展望: Hermitian 問題におけるエルミート性の保持や、行列関数の評価など、他の文脈でのランダム化の安定化効果への応用が期待されます。

総じて、RRR 法は、数値線形代数における固有値問題の求解において、理論的保証と実用性の両面から大きな進歩をもたらす手法と言えます。