VMLS 10.4 QR分解

線形代数

テキスト→Introduction to Applied Linear Algebra – Vectors, Matrices, and Least Squares

10.4 QR分解

正規直交列を持つ行列

グラム行列の応用として、我々は {\displaystyle n } 次元ベクトル {\displaystyle a_1,...,a_k } が正規直交であることを、行列表示を用いて次のように簡潔に示すことができる。

{\displaystyle A^T A=I }

ここで、{\displaystyle A } は列ベクトル {\displaystyle a_1,...,a_k } を持つ {\displaystyle n\times k } 型行列である。正規直交列を持つ行列に正式な名称はないが、{\displaystyle A^T A=I } を満足する正方行列は直交行列と呼ばれ、その列は正規直交基底をなす。直交行列は様々な場面に応用される。
　我々はすでに単位行列、二次元の反転・回転行列 (129ページ)、置換行列 (132ページ) といった直交行列に出会っている。

ノルム、内積、角度に関する性質

{\displaystyle m\times n } 型行列 {\displaystyle A } の各行が正規直交であるとし、{\displaystyle x } と{\displaystyle y } を任意の {\displaystyle n } 次元ベクトルとする。いま、{\displaystyle z } を {\displaystyle Az } に移す関数 {\displaystyle f: R^n\rightarrow R^m } を定義すると、次の性質を得る。

  • {\displaystyle ||Ax||=||x||.\quad } よって、{\displaystyle f } はノルムを保存する。
  • {\displaystyle (Ax)^T(Ay)=x^T y.\quad } {\displaystyle f } は2ベクトルの内積を保存する。
  • {\displaystyle \angle (Ax,Ay)=\angle (x,y).\quad } {\displaystyle f } はベクトル間の角度を保存する。

上記の三つの方程式において、左右のベクトルの次元が異なっていることに注意されたい。左側は {\displaystyle m } 次元、右側は {\displaystyle n } 次元である。
　これらの性質は簡単な行列の性質を用いて証明できる。まず、二つ目の性質「{\displaystyle A } の乗算は内積を保存する」から始める。

{\displaystyle \begin{eqnarray} (Ax)^T(Ay) &=& (A^T x^T)(Ay)\\ &=& x^T (A^T A)y\\ &=& x^T Iy\\ &=& x^T y. \end{eqnarray} }
一行目で、我々は転置行列の積の性質を用いた。二行目では、四つの行列を再び結合した (行ベクトル {\displaystyle x^T } と列ベクトル {\displaystyle y } を行列とみなしている)。三行目では、{\displaystyle A^T A=I } を用いた。最後に、{\displaystyle Iy=y } を用いた。
　二つ目の性質から、我々は一つ目の性質を導くことができる。{\displaystyle y=x } とおくと {\displaystyle (Ax)^T(Ax)=x^T x } となり、両辺の平方根をとると {\displaystyle ||Ax||=||x|| } が得られる。三つ目の角度の保存は、一つ目と二つ目の性質から得られる。
{\displaystyle \angle(Ax,Ay)=arccos(\frac{(Ax)^T(Ay)}{||Ax|| ||Ay||})=arccos(\frac{x^T y}{||x|| ||y||})=\angle(x,y). }

QR分解

我々は {\displaystyle {\S}5.4 } で示したグラム-シュミットの正規直交化法*1 を行列を用いて簡潔に表現することができる。{\displaystyle n\times k } 型行列 {\displaystyle A } の各列 {\displaystyle a_1,...,a_k } は互いに線形独立であるとする。独立な次元の非対称性により、{\displaystyle A } は縦長の行列となる。つぎに、{\displaystyle n } 次元ベクトル {\displaystyle a_1,...,a_k } にグラム-シュミットの正規直交化法を適用したベクトル {\displaystyle q_1,...,q_k } を列ベクトルにもつ {\displaystyle n\times k } 型行列 {\displaystyle Q } を定義する。{\displaystyle q_1,...,q_k } の正規直交性は行列表示で {\displaystyle Q^T Q=I } と表現できる。我々は {\displaystyle a_i } と {\displaystyle q_i } の関係を次のような方程式

{\displaystyle a_i=(q_1^T a_i)q_1+\cdots+(q_{i-1}^T a_i)q_{i-1}+||\tilde{q}_i||q_i }
で表すことができる。{\displaystyle \tilde{q}_i } はグラム-シュミットの正規直交化法のはじめの操作で
{\displaystyle a_i=(R_{1i}q_1+\cdots+R_{ii}a_i)q_i }
として得られるベクトルである。ここで、{\displaystyle i < j } において {\displaystyle R_{ij}=q_i^T a_j }、{\displaystyle R_{ii}=||\tilde{q}_i|| } である。{\displaystyle i > j } において {\displaystyle R_{ij}=0 } と定義することで、我々は上記の方程式を簡潔な行列表示で次のように表すことができる。
{\displaystyle A=QR }
これは行列 {\displaystyle A } を二つの行列 {\displaystyle Q } と {\displaystyle R } の積で表すため、QR分解 (QR factorization) と呼ばれる。
　{\displaystyle n\times k } 型行列 {\displaystyle Q } は正規直交な列をもち、{\displaystyle k\times k } 型行列 {\displaystyle R } は正の対角成分をもつ上三角行列である。{\displaystyle A } が線形独立な列をもつ正方行列であるとき、{\displaystyle Q } は直交行列であり、QR分解は {\displaystyle A } を二つの正方行列の積で表現する。
　QR分解における行列 {\displaystyle Q } と {\displaystyle R } の性質はグラム-シュミットの正規直交化法から直接導かれる。{\displaystyle Q^T Q=I } はベクトル {\displaystyle q_1,...,q_i } の正規直交性から得られる。また、{\displaystyle A } の各列ベクトル {\displaystyle a_i } は {\displaystyle q_1,...,q_i } の線形結合であるため、行列 {\displaystyle R } は上三角行列となる。
　グラム-シュミットの正規直交化法はQR分解の唯一のアルゴリズムではない。他にもいくつかのQR分解のアルゴリズムが存在し、それらは丸め誤差が存在する場合はより信頼性が高い (これらのQR分解の手法では {\displaystyle A } の列を処理する順番が変わることがある)。

スパースQR分解

　行列 {\displaystyle A } が疎行列 (sparse matrix)*2 であるとき、これを効率的に扱ういくつかのQR分解のアルゴリズムがある。このとき、行列 {\displaystyle Q } は一般の {\displaystyle nk } 個の要素を持つ {\displaystyle n\times k } 型行列とよりも要求メモリ量が少ない特別なフォーマットで記憶される。これらのスパースQR分解の flop count*3 もまた {\displaystyle 2nk^2 } より少ない。

*1:グラム-シュミットの正規直交化法の説明はこのブログが最高にわかりやすい。

*2:成分の殆どが零である行列。

*3:この flop は flip-flop のことでしょうか。わかりませんでした。