A Variational Equation and Lower Bound for the Linear Least-Squares Backward Error

技術的概要：線形最小二乗問題の後方誤差に関する変分方程式と下限

問題の定義
本論文は、複数の右辺を持つ線形最小二乗問題における後方誤差 $\mu$ の効率的な推定という課題に取り組む：
$$\min_{X \in \mathbb{R}^{n \times d}} \|AX - B\|_F$$
ここで、$A \in \mathbb{R}^{m \times n}$、$B \in \mathbb{R}^{m \times d}$ である。後方誤差 $\mu$ は、近似解 $X$ が摂動系 $(A+E)^T(A+E)X = (A+E)^T(B+F)$ の厳密解となるような摂動 $[E, \theta F]$ の最小ノルムとして定義される。

$\mu$ の直接計算は、大規模な固有値問題または一般化固有値問題の求解を必要とするため、反復解法にとっては過剰に高価である。推定法は存在する（例えば Karlson-Waldén 推定）が、それらは正確に計算するのが高価であったり、保証された境界（すなわち、厳密な上限または下限ではない）を欠いたりすることが多い。本論文は、LSQR や LSMR などの反復法に対する停止基準として機能し得る、信頼性が高く計算コストの低い推定法、特に下限を導出する方法を追求する。

手法
中核となる手法は、不定線形代数の枠組みにおいて、一般化固有値問題を用いて後方誤差を表現することにある。

1. 変分定式化: 本論文はまず、変換された残差行列 $R_\theta$ に対する後方誤差 $\mu(A, R_\theta)$ の変分方程式を確立する。$\mu$ は、制約 $X^T J_{n,d} X = -I_d$ によって定義される不定多様体上での最大化問題として表現される。ここで $J_{n,d} = \text{diag}(I_n, -I_d)$ である。
   $$\mu(A, R_\theta) = \sup_{X^T J_{n,d} X = -I_d} \left( \|R_\theta\|_F^2 - \|[A, R_\theta]X\|_F^2 \right)^{1/2}$$
2. 双曲的 CS 分解: この最適化問題を解くために、著者らは双曲的 CS 分解（ユニタリ行列に対する CS 分解の不定 analogue）を利用する。この分解により、行列 $X$ に関する最適化を、直交行列と対角スケーリング行列に関する最適化に分離できる。
3. 分解定理: この分解を適用することで、本論文は $d$ 個の右辺を持つ問題の後方誤差が、それぞれ単一の右辺を含む $d$ 個のより小さな後方誤差問題の和に分解されることを示す定理を導出する。
4. 下限の構築: この分解を活用し、著者らはスケーリングに基づく下限を提案する。スケーリング行列 $S$ を用いてスケーリングされた行列 $SA$から単一のテストベクトル$p$ を計算することで、単一の右辺に対する後方誤差の式を評価できる。これにより、真の後方誤差に対する証明可能な下限が得られる。

主要な貢献

• 定理 1（分解）: 主要な理論的貢献は、後方誤差 $\mu(A, R_\theta)$ をより小さな項の和に分解することである：
  $$\mu(A, R_\theta) = \max_{P, Q} \left( \sum_{i=1}^k \mu^2(Ap_i, R_\theta q_i) \right)^{1/2}$$
  ここで $P$ と $Q$ は直交列を持つ行列である。これにより、問題の複雑さは一連のスカラー最適化に軽減される。
• 単一の右辺に対する厳密式: 本論文は、単一の右辺の場合の後方誤差 $\mu(a, r)$ に対する安定した閉形式の式を提供する。これはベクトルの和と差のノルムに依存する：
  $$\mu(a, r) = \frac{2|a^T r|}{\|a+r\|_2 + \|a-r\|_2}$$
• スケーリングに基づく下限: 著者らは反復法のための新しい下限を提案する。スケーリング行列 $S$ を用いて近似方向 $p$ を計算し、単一の右辺の式を評価することで、値 $\mu(Ap/\|p\|_2, r_\theta)$ を得る。
  • この値は、真の後方誤差に対する証明可能な下限である。
  • 本論文は、この下限がスケーリングされた Karlson-Waldén 推定と同等の品質であることを証明し、特に以下の不等式を満たすことを示す：
    $$\frac{1-\eta^2}{1+\eta^2} \nu(A, r_\theta) \leq \mu(Ap/\|p\|_2, r_\theta) \leq \mu(A, r_\theta)$$
    ここで $\eta$ はスケーリングの歪みを表し、$\nu$ は Karlson-Waldén 推定である。
• 反復改善と再利用: 本論文は、ベクトル $p$ の反復改善による推定値の向上と、計算コストを削減するために反復間で計算済みベクトル $Ap$ を「再利用」する手法について議論する。

結果
SuiteSparse コレクションから、条件数が非常に高い（$\approx 3.5 \times 10^{16}$）行列を用いて、LSMR ソルバーによる数値実験が行われた。結果は以下の通りである：

• 提案された下限は、スケーリングされた Karlson-Waldén 推定と一貫して同等の精度を示した。
• 安価なスケーリング（より小さな $n_{sketch}$）の場合、提案された下限は、スケーリングされた Karlson-Waldén 推定よりも時として正確であった。
• 「再利用された」下限（反復間で $Ap$ を再利用するもの）は、反復履歴の大部分において真の後方誤差に近接しており、安価な誤差モニターとしての有用性を示唆した。
• ベクトル $p$ の反復改善は、スケーリングサイズが非常に大きい場合（$16n$）にのみ精度を向上させた。標準的なスケーリングサイズでは、追加の計算コストが正当化されない可能性が示唆された。
• 同様の手法を用いて上限を構築する試みは、既存の単純な上限（例えば $\|A^T r\|_2 / \|r\|_2$）よりもわずかに優れているに留まり、真の誤差を依然として大幅に過大評価していた。

意義と主張
本論文の主な意義は理論的であるとする。すなわち、計算可能な下限へと自然につながる後方誤差の分解を提供することである。

• 信頼性: 上限または下限であることが保証されていないスケーリングされた Karlson-Waldén 推定とは異なり、提案された手法は厳密な下限をもたらす。これは停止基準にとって有益であり、真の誤差が推定値以上であることを保証する。
• 効率性: この手法は、スケーリングに基づく推定を、同等の品質を持ちながら、境界であるという保証を付加した下限へ変換することを可能にする。
• 謙虚さ: 著者らは上限に関しては謙虚であり、同様の方法で上限を生成する試みは「一般的に不成功であった」と指摘している。複数の右辺に対する分解は、下限に必要な単一ベクトル最適化よりも複雑な、2 つの行列（$P$ と $Q$）に関する最適化を伴うことを認めている。今後の課題として、複数の右辺の場合への対応と、なぜ良い上限を見つけることが良い下限を見つけることよりも困難に見えるのかの調査が提案されている。