ごるごの勉強記録

電気タイプの大学生

VMLS 11.5 疑似逆行列

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

11.5 Pseudo-inverse

列の線形独立性とグラム行列の正則性

 はじめに、{\displaystyle m\times n } 型行列 {\displaystyle A } はグラム行列 {\displaystyle A^T A } が正則である場合のみ線形独立な列をもつことを証明する。
 まず、{\displaystyle A } の各列が線形独立であるとする。{\displaystyle x }{\displaystyle (A^T A)x=0 } を満足するある {\displaystyle n } 次元ベクトルとする。左側から {\displaystyle x^T } を掛けると

{\displaystyle 0=x^T=x^T(A^T Ax)=x^T A^T Ax=||Ax||^2, }
すなわち {\displaystyle Ax=0 } を得る。{\displaystyle A } の各列は線形独立であるから、{\displaystyle x=0 } を得る。{\displaystyle (A^T A)x=0 } の唯一の解は {\displaystyle x=0 } であるため、{\displaystyle A^T A } は正則である。
 つぎに逆を証明する。{\displaystyle A } の各列が線形従属である、すなわち、{\displaystyle Ax=0 } を満たす {\displaystyle n } 次元の非零ベクトル {\displaystyle x } が存在するとする。左側から {\displaystyle A^T } を掛けると {\displaystyle (A^T A)x=0 } を得る。これはグラム行列 {\displaystyle A^T A } が正則ではないことを意味する。

正方行列または縦長の行列の疑似逆行列

 {\displaystyle A } が線形独立な列をもつ (すなわち、{\displaystyle A } が正方行列か縦長の行列である) とき、{\displaystyle A } が左逆行列をもつことを示す (我々はすでにこの逆、すなわち左逆行列をもつ行列が線形独立な列をもつことを知っている)。{\displaystyle A } が線形独立な列をもつとすると、{\displaystyle A^T A } は正則である。ここで、

{\displaystyle ((A^T A)^{-1}A^T)A=(A^T A)^{-1}(A^T A)=I }
より、{\displaystyle (A^T A)^{-1}A^T }{\displaystyle A } の左逆行列である。
 この特定の {\displaystyle A } の左逆行列{\displaystyle A } の疑似逆行列 (pseudo-inverse of {\displaystyle A }) とよばれ、{\displaystyle A^{\dagger} } と表記される。
{\displaystyle A^{\dagger}=(A^T A)^{-1}A^T.\quad (11.5) }
疑似逆行列は二人の数学者に因んでムーア・ペンローズ逆行列 (Moore-Penrose inverse) とも呼ばれる。
 {\displaystyle A } が正方行列であるとき、疑似逆行列 {\displaystyle A^{\dagger} } は元の逆行列となる。
{\displaystyle A^{\dagger}=(A^T A)^{-1}A^T=A^{-1}A^{-T}A^T=A^{-1}I=A^{-1}. }
ただし、{\displaystyle A } が正方行列でないとき、この方程式は成立しない。

他の場合での疑似逆行列

 疑似逆行列 {\displaystyle A^{\dagger} } は、縦長であるがその列が線形従属な行列や横長でありその行が線形従属な行列、正方行列であるが正則ではない行列を含むどのような行列に対しても定義できる。しかし、これらの場合には疑似逆行列は左逆行列ではなく、それぞれ右逆行列または逆行列となる。(これらの場合に {\displaystyle A^{\dagger} } が何を意味するのかについては例題 15.11 で紹介する。)

QR分解による疑似逆行列

 QR分解は疑似逆行列についての簡単な公式を与える。{\displaystyle A } が左逆行列をもつとき、その列は線形独立であり、QR分解 {\displaystyle A=QR } が存在する。ここで、

{\displaystyle A^T A=(QR)^T(QR)=R^T Q^T QR=R^T R }
より、
{\displaystyle A^{\dagger}=(A^T A)^{-1} A^T=(R^T R)^{-1}(QR)^T=R^{-1}R^{-T}R^T Q^T=R^{-1}Q^T }
を得る。
 QR分解を用いて、{\displaystyle Q^T } の列について back substitution を適用して疑似逆行列を計算できる (これは11.3の {\displaystyle A }正則行列であるときのアルゴリズムと全く同一である)。この手法の複雑性はQR分解に要する {\displaystyle 2n^2 m } フロップと back substitusion に要する {\displaystyle mn^2 } フロップである。したがって合計は {\displaystyle 3mn^2 } フロップとなる。
 同様に、{\displaystyle A } が右逆行列であるとき、その転置行列のQR分解 {\displaystyle A^T=QR } が存在する。{\displaystyle AA^T=(QR)^T(QR)=R^T Q^T QR=R^T R } であり、
{\displaystyle A^{\dagger}=A^T(A^T A)^{-1}=(QR)(R^T R)^{-1}=QRR^{-1}R^{-T}=QR^{-T} }
を得る。上記の手法を用いて計算すると、次の公式を得る。
{\displaystyle (A^T)^{\dagger}=(A^{\dagger})^T. }

優決定・劣決定な連立一次方程式の解法

 この疑似逆行列は、係数行列の各列が線形独立な優決定系、または各行が線形独立な劣決定系の解法を与える。{\displaystyle A } の各列が線形独立であるとき、優決定の方程式 {\displaystyle Ax=b } は解 {\displaystyle x=A^{\dagger}b } をもつ。{\displaystyle A } の各行が線形独立であるとき、劣決定の方程式 {\displaystyle Ax=b } は任意の {\displaystyle b } に対して解をもち、{\displaystyle x=A^{\dagger}b } が解である。

Numerical Example

 これらのアイデアを、199ページと201ページの例題で用いられた {\displaystyle 3\times 2 } 型行列

{ \displaystyle A=\begin{bmatrix} -3&-4\\ 4& 6\\ 1& 1 \end{bmatrix}. }
を用いた簡単な計算例で説明する。この行列は線形独立な列をもち、QR分解は
{ \displaystyle Q=\begin{bmatrix} -0.5883&0.4576\\ 0.7845&0.5230\\ 0.1961&-0.7191 \end{bmatrix},\quad R=\begin{bmatrix} 5.0990&7.2563\\ 0&0.5883 \end{bmatrix} }
となる。{\displaystyle A } は疑似逆行列をもち、
{ \displaystyle A^{\dagger}=R^{-1}Q^T=\begin{bmatrix} -1.2222&-1.1111&1.7778\\ 0.7778&0.8889&-1.2222 \end{bmatrix}. }
となる。我々は疑似逆行列を用いて {\displaystyle b=(1,-2,0) } のとき優決定な方程式 {\displaystyle Ax=b } が解をもつかを調べることができ、もしも解をもつならばその解を求めることができる。{\displaystyle x=A^{\dagger}(1,-2,0)=(1,1) } を計算し {\displaystyle Ax=b } が成り立つかどうかを調べればよい。いま、{\displaystyle Ax=b } が成立するので、{\displaystyle x }{\displaystyle Ax=b } の唯一の解である。