Convergence rates for pivoted QR and LU

技術要約：ピボット付きQRおよびLUの収束率

問題提起
ピボット付きQRおよびピボット付きLU分解は、行列や関数の低ランク近似を計算するための広く用いられている貪欲法（greedy algorithms）である。これらの手法は実用面で強力な性能を示すが、その理論的正当化は、歴史的に指数関数的に増大する因子（例：$4^k$ や $2^k$）を含む最悪ケースの境界に依存してきた。これらの境界は、収束が保証されるためには、指数関数的な因子（例：$\rho < 1/4$）を克服できるほど十分な速度で特異値が幾何学的に減少する必要があることを示唆している。しかし、実際には、これらのアルゴリズムはより緩やかな特異値の減少（代数的またはより緩やかな幾何学的減少）の下でも効果的に収束することが多い。本論文は、これらの悲観的な最悪ケースの境界と観察される実用的な挙動との間の乖離に対処するため、指数関数的なペナルティ因子を含まず、特異値の減少や関数の正則性に直接依存する収束率を導出する。

手法
分析の核心は、主に以下の2つの構成要素に基づいている：

1. 近似貪欲ピボット選択（Approximate Greedy Pivoting）: 著者らは、厳密な貪欲ピボット選択（絶対的な最大成分または列ノルムの選択）の要件を、近似貪欲ピボット選択へと緩和している。このスキームでは、選択されたピボット $p_{k+1}$ は、$|p_{k+1}| \ge \gamma \|E^{(k)}\|_{\max}$ （LUの場合）、または $\rho_{k+1} \ge \gamma \|E^{(k)}\|_{2,\infty}$ （QRの場合）を満たす（ここで $0 < \gamma \le 1$ は品質定数である）。
2. ピボット積の恒等式と行列式の境界: 分析では、選択されたインデックスによって形成される部分行列の行列式と、ピボットの積を結びつける古典的な恒等式を利用している。
   • LUの場合、$\det(A_{I_n, J_n}) = \prod_{j=1}^n p_j$。
   • QRの場合、$(\det(G_n))^{1/2} = \prod_{j=1}^n \rho_j$ （ここで $G_n$ は選択された列のグラム行列である）。

これらの恒等式を近似ピボット条件と組み合わせることで、著者らは最初の $n$ 回の反復における最小残差を、最初の $n$ 個の特異値の幾何平均（行列の場合）、またはサンプリングされた部分行列の行列式の境界（関数の場合）によって抑え込んでいる。

主要な貢献と結果

1. 行列の場合（ピボット付きQRおよびLU）
本論文は、これらのアルゴリズムの誤差が、先頭の特異値の幾何平均 $\left(\prod_{j=1}^n \sigma_j(A)\right)^{1/n}$ によって制御されることを確立している。

• 代数的減少: 特異値が $\sigma_k(A) = O(k^{-p})$ として代数的に減少する場合、LUおよびQRの両方の残差は、同じ代数的レート $O(k^{-p})$ で収束する。これは、収束を保証するために指数関数的な減少を必要とした従来の境界とは対照的である。
• 幾何学的減少: 特異値が $\sigma_k(A) = O(\rho^k)$ として幾何学的に減少する場合、残差は幾何学的レート $O(\rho^{k/2})$ で収束する。
• 堅牢性: これらの結果は、近似貪引ピボット選択の下でも成立し、誤差境界は定数 $\gamma^{-1}$ 倍のスケールのみを受ける。

2. 関数の場合（関数のためのピボット付きLU）
この分析は、分離可能展開による二変数関数 $f(x, y)$ の近似へと拡張されている。アルゴリズムは、$L^\infty$ ノルムにおける残差を最小化するようにピボット点 $(x_k, y_k)$ を選択する。

• 正則性に基づくレート: 関数 $f$ の滑らかさに基づいて、サンプリングされた部分行列 $[f(x_i, y_j)]$ の行列式を境界付けることで、収束率が導出される。
  • ヘルダー連続または微分可能な関数: 一方の変数において $q_x$ 回の微分が可能（ヘルダー連続性 $\alpha_x$）であり、他方の変数において $q_y$ 回の微分が可能な関数について、論文は代数的な収束率を導出している。具体的には、$f$ が一方の変数において単に $\alpha_x$-ヘルダー連続（$\alpha_x > 1/2$）である場合でも、収束が保証される。混合正則性は、改善されたレートをもたらす（例：混合微分を持つ $q$ 回微分可能な関数に対して $O(n^{-(2q-1/2)})$）。
  • 解析関数: パラメータ $\rho_x, \rho_y > 1$ を持つベルンシュタイン楕円体内で解析的な関数に対して、論文は幾何学的収束を確立している。片側解析性の下では、レートは $O(\rho^{-n/2})$ であり、同時解析性の下では $O((\rho_x \rho_y)^{-n/2})$ に向上する。これらの結果は、任意の $\rho > 1$ に対して成立し、従来の $\rho > 4$ という要件を改善している。

意義と主張
本論文は、従来の最悪ケースの境界が情報を持たないような領域においても、ピボット付きQRおよびLUアルゴリズムが堅牢な性能を発揮することに対する理論的な説明を提供すると主張している。

• 新しい理論的境界: 著者らは、特異値の減少下でのLUの収束率は新しいものであると述べている。QRについては、縮小基底（reduced-basis）の文献において同様のレートが存在するが（コルモゴロフ幅を介して）、本研究は、二次的な依存関係ではなく、ピボットの品質 $\gamma^{-1}$ に対する線形な依存関係を持ち、より小さな明示的な定数を持つ推定値を提供している。
• 関数近似: 本論文は、解析性や正定値性の仮定を必要としない、関数に適用されたピボット付きLUに関する最初の一般的な収束率の結果を提示している。
• アルゴリズムの堅牢性: 重要な知見は、分析が近似貪欲ピボット選択をシームレスに許容していることである。これは、計算コストを削減するために（実務で一般的な）ヒューリスティックなピボット選択戦略を用いても、定数倍の違いを除いて、厳密なピボット選択と同じ収束率を維持できることを示唆している。

著者らは、これらのアルゴリズムにおける支配的なコストはしばしばピボット探索であると結論付けており、彼らの結果は、収束率を犠牲にすることなく近似ピボット戦略を使用することを支持している。今後の課題として、これらの滑らかさに基づく推定を高次元およびより広い関数クラスへ拡張することが挙げられている。