一般逆行列
目次
一般逆行列とは
高校生の時に逆行列を用いて解いた行列の問題は、正則行列であることが前提でした。ですが、実際の問題において正則行列であるとは限りません。そのような非正方・非正則行列へと逆行列を拡張したものを一般逆行列と呼びます。つまり、解けない問題に対して尤もらしい解を提供しますということです。
場合分け
一般に線形方程式は以下の式で記述できます。
\begin{align}
Ax = b
\end{align}
$A \in {\mathbb{R}}^{m \times n}$、$b \in {\mathbb{R}}^{m \times 1}$、$x \in {\mathbb{R}}^{n \times 1}$であり、$ m $は方程式の数、$n$は未知数の数を示す。
このとき以下の4つに場合分けできます。
- $ rank(A) = m = n $
- $ rank(A) = n < m $
- $ rank(A) = m < n $
- $ rank(A) < min(m, n) $
2. の場合（列フルランク）
$ rank(A) = n < m $の場合、未知数の数より方程式の数が多い場合です。この場合、解が不能になります。つまり、全ての方程式を満たすことができる解がないということです。
このような場合は、全方程式の二乗誤差が最小となる点を解とします。つまり、以下の最適化問題を解くことになります。
\begin{align}
x^{*} = {\rm argmin}_{x} \frac{1}{2} {|Ax - b|}^2
\end{align}
目的関数の偏微分が0になる点を求めます。
\begin{align}
\frac{\partial f(x)}{\partial x} = A^T (Ax - b) = 0 \\
x = {({A}^{T} A)}^{-1} {A}^{T} b
\end{align}
ここで$ A^T A $は正則であるので、解は求めることができます。
3. の場合（行フルランク）
$ rank(A) = m < n $の場合、方程式の本数より未知数の方が多い場合です。このとき、解は不定になります。つまり、解が一意に定まりません。
このような場合、L2ノルムが最小の点を解とします。つまり、以下の最適化問題を解くことになります。
\begin{align}
x^* = {\rm argmin}_x \frac{1}{2} {|x|}^2 \;\; s.t. \;\; Ax = b
\end{align}
これをLagrangeの未定乗数法で解きます。
\begin{align}
L(x, \lambda) = \frac{1}{2} x^T x - {\lambda}^{T} (Ax - b)
\end{align}
これを$x$と$ \lambda $で微分します。
\begin{align}
\frac{\partial L}{\partial x} = x - A^T \lambda = 0 \in {\mathbb{R}}^{n} \\
\frac{\partial L}{\partial \lambda} = -Ax + b = 0 \in {\mathbb{R}}^{m}
\end{align}
したがって、以下のように解が求まります。
\begin{align}
x = A^T (AA^T)^{-1} b
\end{align}
4. の場合（ランク落ち）
この場合はランク落ちと言われます。この場合は、多数ある最小二乗点のうち最小ノルム点を解とします。ただし、ランク落ちの場合は$ (A^T A)^{-1} $や$ (AA^T)^{-1} $の計算ができないため、$A$を列フルランク行列$B$と行フルランク行列$C$に分解します。
このとき、2. の場合と3. の場合を利用して、以下のように求まります。
\begin{align}
Ax & = BCx = b \\
x & = C^T (CC^T)^{-1} (B^T B)^{-1} B^T b
\end{align}
階数分解
一般逆行列の話は一旦終わりましたが、4. の場合の$A=BC$に分解する部分はあまりきちんと説明していませんでした。これは階数分解というものです。
Wikipediaには以下のように書かれています。
数学の線型代数学の分野において、階数が$ r $のある与えられた$ m \times n $行列$ A $の階数因数分解（かいすういんすうぶんかい、英: rank factorization）あるいは階数分解（rank decomposition）とは、ある$ m \times r $行列$ C $と$ r \times n $行列$ F $の積としての表示$ A = CF $のことを言う。
階数分解をする方法として、特異値分解を利用する方法があります。特異値分解自体の解説はまた今度記事にします。
ランク$ r $の$ m \times n $行列$ A $を特異値分解すると、直交行列$ U $と$ V $と対角行列$ S $に分解することできます（シグマが上手く変換されないので、Sを代わりに使います）。
\begin{align}
A &= U S V^T \\
S &=
\begin{pmatrix}
S_r & 0 \\
0 & 0
\end{pmatrix} \\
S_r &= diag(s_1, s_2, \cdots, s_r)
\end{align}
ここで、$ A \in {\mathbb{R}}^{m \times n} $、$ U \in {\mathbb{R}}^{m \times m} $、$ S \in {\mathbb{R}}^{m \times n} $、$ V \in {\mathbb{R}}^{n \times n} $、$ S_r \in {\mathbb{R}}^{r \times r} $です。
ここで以下のようにすると、階数分解することができます。
\begin{align}
A &= U S V^T =
\begin{bmatrix}
U_r & U_{m-r}
\end{bmatrix}
\begin{bmatrix}
S_r & 0 \\
0 & 0
\end{bmatrix}
\begin{bmatrix}
{V_r}^T \\ {V_{n-r}}^T
\end{bmatrix}
= U_r S_r {V_r}^T \\
&= U_r (S_r {V_r}^T) = (U_r S_r) {V_r}^T = BC
\end{align}
特異値分解で一般逆行列を表現する
先程の階数分解から、$ B = U_r $、$ C = S_r {V_r}^{T} $を代入すると、以下の式が得られる。
\begin{align}
A^{-} &= C^T (C C^T)^{-1} (B^T B)^{-1} B^T \\
&= V_r S_r (S_r {V_r}^{T} V_r S_r)^{-1} ({U_r}^{T} U_r)^{-1} {U_r}^{T} = V_r {S_r}^{-1} {U_r}^{T}
\end{align}
