📂行列代数

最小二乗法におけるLU、QR、SVDの速度比較

要約 ¹

行列 $A \in \mathbb{R}^{m \times n}$について、$m \ge n$であるとしよう。LU分解とQR分解、そして特異値分解で最小二乗法を行うとき、時間計算量はすべて同じく$O \left( mn^{2} \right)$であるが、実際に必要なflop数はおおよそ次のようになる。

• LU分解²: $$ mn^{2} + {\frac{ 2 }{ 3 }} n^{3} $$
• QR分解³: $$ 2mn^{2} - {\frac{ 2 }{ 3 }} n^{3} $$
• 特異値分解⁴: $$ 4mn^{2} - {\frac{ 4 }{ 3 }} n^{3} $$

ただしこの要約には「意図的に間違った部分」が含まれているので鵜呑みにせず、必ず本文の内容を読んでみることを勧める。

説明

最小二乗法の実質的な実装として行列分解を使う方法はいくつかあるが、一般にはLU分解(コレスキー分解)による方法とQR分解による方法、そしてSVD分解による方法の三つが特に広く使われる。参考までに、LU分解であれコレスキー分解であれガウス消去法であれ、本質的には前進代入と後退代入によって線形システムを解く方法であるため、最小二乗法の実装という側面ではすべて同じものと見なして差し支えない。実際にコレスキー分解のflopsは$mn^{2} + {\frac{ 1 }{ 3 }} n^{3}$でLU分解より少し良いが、現実的には安定性のためにピボッティング^pivotingが含まれたPLU分解を使うことになる。

Julia⁵やMATLAB⁶の実装を見ると、事実上$A$で$m \ne n$のときはQR分解、$m = n$のときはLU分解を使うと見てよい。

実際にflopsの比較で最も重要で支配的な項は$m n^{2}$であり、LUからQR、SVDへと進むにつれて計算量がほぼ2倍ずつ増えていくのが見て取れる。ただしこのような要約は受け入れやすいように整理したものであって、具体的な公式そのものはflopや実装方式によって変わることもある。

LU分解

実はLU分解は$2n^{3}/3$だけのflopsしか必要としないが、最小二乗法のためには$A \mathbf{x} = \mathbf{b}$から$A^{\top} A \mathbf{x} = A^{\top} \mathbf{b}$へと変えなければならないため、$A^{\top} A$を計算するとき$mn^{2}$だけのflopsが追加で必要となる。

当然ながら$m = n$の場合には$A^{\top} A$を計算する必要がないので前の項が消えて$2/3 n^{3}$となり、QR分解に比べて二倍速い。逆に$m \gg n$の場合にも$n^{3}$の比重は減って、結局QR分解に比べて二倍ほど速くなる。本当に良い条件の行列を持っていて速度を優先しなければならないなら、LU分解を使う方が良いときもあるということだ。

QR分解

LU分解に比べて二倍遅く、SVDに比べて二倍速い。ある意味では中途半端だと見ることもできるが、SVDが遅すぎて最小二乗法の実装に基本的に使われることが稀だということを考えてみると、最も無難で良い方法だと見なせる。現実的にこの世界のほとんどの最小二乗問題はQR分解によって解決されているだろう。

SVD

整理されたSVDのflopsはゴラブ・カハン二重対角化^{Golub-Kahan bidiagonalization}を使うとき$4mn^{2}$が先に出てくるが、行列分解だけをするのではなく特異値分解に焦点を合わせると行列分解とは別の計算が増えたり減ったりして次のようになる。 $$ 2 mn^{2} + 11 n^{3} $$ これが先ほど言及した「意図的に間違った部分」である。いずれにせよQRに比べて遅いのは事実であり、文字通り最小二乗法一回のためであればこの方法を使う理由が特にないため、より簡潔な比較をしたのだ。

安定性とのトレードオフ

三つの方法の速度を比較してみて安定性を比較してみると、次のように非常に明確にトレードオフを確認できる。

方法	速度	安定性
LU	速い	不安定
QR	普通	安定的
SVD	遅い	非常に安定的