グラムシュミットの直交化によるQR分解と固有値問題

機械学習用の線形代数の復習まとめ。

QR分解(QR Factorization)

QR分解は線型最小二乗問題や固有値問題を解く際に必要な処理です。

その中でも一番シンプルなグラムシュミットの直交化によるQR分解についてまとめていきます。

プロセス

$A = \begin {pmatrix}1&-1&2\\1&0&1\\-1&1&2\\0&1&1\end{pmatrix}$

について考えていきます。

この時、

$\left\{ \begin{align} &\mathbf w_1 = (1,1,-1,0)^\mathrm{T} \\ &\mathbf w_2 = (-1,0,1,1)^\mathrm{T} \\ &\mathbf w_3= (2,-1,2,1)^\mathrm{T}  \end{align} \right.$

$\mathbf v_1 = \mathbf w_1$

$\mathbf v_2 = \mathbf w_2 – \frac{\langle \mathbf w_2 , \mathbf v_1 \rangle}{\|\mathbf v_1\|^2}\mathbf v_1=\mathbf w_2+\frac{2}{3}\mathbf v_1$

$\mathbf v_2 = \mathbf w_3 – \frac{\langle \mathbf w_3 , \mathbf v_1 \rangle}{\|\mathbf v_1\|^2}\mathbf v_1-\frac{\langle \mathbf w_3 , \mathbf v_2 \rangle}{\|\mathbf v_2\|^2}\mathbf v_1=\mathbf w_3+\frac{1}{3}\mathbf v_1 -\frac{1}{5}\mathbf v_2$

よって、

$\left\{ \begin{align} &\mathbf w_1 = \mathbf v_1 \\ &\mathbf w_2 = \mathbf v_2- \frac{2}{3}\mathbf v_1\\ &\mathbf w_3=\mathbf v_3 + \frac{1}{5}\mathbf v_2-\frac{1}{3}\mathbf v_1 \end{align} \right.$

ここで、

$R’ = \begin {pmatrix}1&-\frac{2}{3}&-\frac{1}{3}\\0&1&\frac{1}{5}\\0&0&1\end{pmatrix}$

また、

$\mathbf V = \mathbf U\begin {pmatrix}\|\mathbf v_1\|&0&0\\0&\|\mathbf v_2\|&0\\0&0&\|\mathbf v_3\|\end{pmatrix}=\begin {pmatrix}\frac{1}{\sqrt{3}}&-\frac{1}{\sqrt{15}}&\frac{3}{\sqrt{15}}\\ \frac{1}{\sqrt{3}}&\frac{2}{\sqrt{15}}&-\frac{1}{\sqrt{15}}\\ -\frac{1}{\sqrt{3}}&\frac{1}{\sqrt{15}}&\frac{2}{\sqrt{15}}\\0&\frac{3}{\sqrt{15}}&\frac{1}{\sqrt{15}}\end{pmatrix}\begin {pmatrix}\sqrt{3}&0&0\\0&\frac{\sqrt{15}}{3}&0\\0&0&\frac{4\sqrt{15}}{5}\end{pmatrix}$

$R$について、

$R=\begin {pmatrix}\sqrt{3}&0&0\\0&\frac{\sqrt{15}}{3}&0\\0&0&\frac{4\sqrt{15}}{5}\end{pmatrix}R’$

より、

$R=\begin {pmatrix}\sqrt{3}&\frac{-2\sqrt{3}}{3}&\frac{-\sqrt{3}}{3}\\0&\frac{\sqrt{15}}{3}&\frac{\sqrt{15}}{15}\\0&0&\frac{4\sqrt{15}}{5}\end{pmatrix}$

よって、

$A = QR =\begin {pmatrix}\frac{1}{\sqrt{3}}&-\frac{1}{\sqrt{15}}&\frac{3}{\sqrt{15}}\\ \frac{1}{\sqrt{3}}&\frac{2}{\sqrt{15}}&-\frac{1}{\sqrt{15}}\\ -\frac{1}{\sqrt{3}}&\frac{1}{\sqrt{15}}&\frac{2}{\sqrt{15}}\\0&\frac{3}{\sqrt{15}}&\frac{1}{\sqrt{15}}\end{pmatrix} \begin {pmatrix}\sqrt{3}&\frac{-2\sqrt{3}}{3}&\frac{-\sqrt{3}}{3}\\0&\frac{\sqrt{15}}{3}&\frac{\sqrt{15}}{15}\\0&0&\frac{4\sqrt{15}}{5}\end{pmatrix}$