An Improved Incremental Singular Value Decomposition and New Error Bounds

技術的概要：改良された逐次特異値分解と新たな誤差 bound

問題定義
逐次特異値分解（SVD）は、Brand [2, 3] によって当初提案され、Fareed ら [10] によって重み付き内積に拡張されたものであり、完全な行列を格納できないストリーミングデータ状況における低ランク近似の標準的な手法である。このアルゴリズムは、新しい列が到着するたびに、切り捨てられた SVD（$U \approx Q\Sigma R^\top$）を更新する。しかし、浮動小数点演算において、各更新は実行中の特異基底 $Q$ に小さな直交因子を乗算する。個々の乗算は丸め誤差の範囲内で直交性を保持するが、これらの誤差はストリーム長 $n$ に対して蓄積する。最終的に、$Q$ は数値的な直交性を失い、特異値の精度が低下し、切り捨て基準が信頼できなくなる。

標準的な対策は、直交性が劣化した際に（修正 Gram–Schmidt 法などを通じて）周期的な再直交化を行うことである。しかし、所定の精度レベルを維持するために必要な頻度は未解決の問題となっていた。Brand [3, p. 28] が指摘したように、特に計算コストの高い再直交化が必要な重み付き設定（有限要素法に基づく固有直交分解など）において、特定の全体的な数値精度レベルを保証するために再直交化がどの程度の頻度で必要であるかは不明であった。

手法
著者らは、実行中の特異因子への更新を遅らせる逐次 SVD アルゴリズムの再構成を提案する。中核となる手法は、以下の 2 つの観察に基づいている：

1. ランク非増加の支配性：低ランク応用において、流入する列のほとんどは現在の部分空間内（残差 $< \text{tol}$）に存在する。これらの「ランク非増加」列は部分空間を拡大しない。
2. バッチ処理：$s$ 個の連続するランク非増加列の累積効果は、投影係数を含む短く太いバッファ行列の 1 回の薄型 SVD によって再現可能であり、$s$ 回個別の境界付き行列 SVD を実行する必要はない。

提案されたアルゴリズム（アルゴリズム 5）は、ランク非増加列の投影係数のバッファを維持する。これらのステップ中、実行中の因子 $Q$ は変更されない。「ランク増大」列（残差 $\ge \text{tol}$）が到着すると、アルゴリズムは以下の処理を行う：

• 蓄積された係数の単一の薄型 SVD を計算してバッファをフラッシュし、$Q$ と $R$ をバッチで更新する。
• 新しい列を処理し、局所的な境界付き行列の最小特異値に対して 2 番目の切り捨てテストを適用して無視できるランクを破棄する可能性がある。
• 追加された列の $W$-直交性を回復させるため、これらのランク増大イベントのみに 2 回パスの古典的 Gram–Schmidt 法（CGS-2）を適用する。

この再構成により、$Q$ に適用される大規模な直交乗算の回数が、ストリーム長 $O(n)$ から $O(r + J_{E2})$ に削減される。ここで、$r$ は数値的ランク、$J_{E2}$ は切り捨てを伴うランク増大イベントの回数である。

主要な貢献
本論文は、2 つの主要な理論的進展と 1 つの実用的なアルゴリズム的改善を提供する：

1. ストリーム長に依存しない直交性 bound：
   著者らは（定理 4.1）、標準的な確率的丸め誤差モデルの下で、計算された左因子 $Q$ の $W$-直交性の損失が以下によって bound されることを証明した：
   $$\|I - Q^\top W Q\|_2 \leq c_1 (r + J_{E2}) r \sqrt{m} \log(2/\delta) \varepsilon_{\text{mach}} + O(\varepsilon_{\text{mach}}^2)$$
   決定的な点は、この bound がストリーム長 $n$ に依存しないことである。これは、$\sqrt{m}$ 因子を通じてのみ列次元 $m$ に依存する。これにより Brand の未解決問題が解決された：再直交化は各ステップで必要ではなく、提案されたバッチ処理戦略により、$n$ に対して一様に機械精度で直交性が維持されることを保証する。

2. 鋭い前方誤差 bound：
   本論文は、$W$-重み付き作用素ノルムにおける分解に対する新たな前方誤差 bound を確立した（定理 4.5）：
   $$\|U - Q\Sigma R^\top\|_W \leq \sqrt{n} \, \text{tol} + (\text{roundoff terms uniform in } n)$$
   これは Fareed と Singler [9] による既存の bound（$n \, \text{tol}$）を鋭くしたものである。著者らは構成例を通じて、$\sqrt{n}$ 速度が達成可能であることを示し、以前の bound が $\sqrt{n}$ 倍だけ緩いことを実証した。

3. アルゴリズム的効率性：
   高価な再直交化ステップの回数を削減し、更新をバッチ処理することにより、提案されたアルゴリズムは計算オーバーヘッドを大幅に削減する。

結果
数値実験は、2 次元放物型テスト問題（重み付きおよび非重みの有限要素設定の両方）および合成データに対して実施された。

• 直交性：既存のアルゴリズム（Brand の直接更新および Fareed の再直交化更新）は、$n$ に対して増加する直交性の劣化を示し（重み付きケースでは $10^{-3}$ までドリフト）、提案されたアルゴリズムは $n=10,000$ までのストリーム長および $m=100,000$ までの列次元において、機械精度（$\sim 10^{-14}$）で直交性を維持した。
• 誤差 bound：実験は $\sqrt{n} \, \text{tol}$ 切り捨て速度を確認した。構成例において、測定された誤差は $\sqrt{n} \, \text{tol}$ の予測と一致し、Fareed–Singler bound（$n \, \text{tol}$）は $\sqrt{n}$ 倍に成長する因子分だけ緩かった。
• パフォーマンス：提案されたアルゴリズムは、最も近い競合他社と比較して4.5 倍から 34 倍高速に動作した。重み付きケースにおいて、既存のアルゴリズムは時間の 94% を再直交化に費やしたが、提案されたアルゴリズムはこのコストを 3 桁削減した。

重要性
本論文は、逐次 SVD における再直交化の頻度に関する未解決問題を解決したと主張する。ランク非増加更新をバッチ処理するようにアルゴリズムを再構成することで、以下の成果を達成している：

1. 一様な直交性：実行中の基底はストリーム長に関係なく数値的に直交したままとなり、事前保証のないヒューリスティックな周期的再直交化チェックの必要性が排除される。
2. より厳密な誤差解析：$\sqrt{n}$ 倍の因子で最先端を改善する、数学的に厳密で鋭い誤差 bound（$\sqrt{n} \, \text{tol}$）を提供する。
3. 実用的な高速化：有限要素 POD のように再直交化コストが支配的な応用において、精度を犠牲にすることなく大幅な高速化を実現する。

著者らは、このアルゴリズムが既に予備版において時間分数 PDE、積分微分方程式、PDE 制約最適化に適用されており、現在確立された直交性と誤差保証に依存していると指摘している。今後の課題として、直交性のドリフト解析（現在は約 $10^3$ 倍保守的）の厳密化と、現在実行時間を支配している投影ステップの最適化が提案されている。