Sherman-Morrison-Woodburyの公式 (Schur補行列) - いんふらけいようじょのえにっき

行列の積に関する逆行列の公式にSherman-Morrison-Woodburyの公式または単にWoodburyの公式があります。

Sherman-Morrison-Woodburyの公式

正則行列 \(\mathrm{A} \in M(n, n), \mathrm{B} \in M(n, m)\)と行列\(\mathrm{C} \in M(m, n), \mathrm{D} \in M(n, n)\)は次式を満たす。

\[
\left( \mathrm{A} + \mathrm{B} \mathrm{D} \mathrm{C} \right)^{-1} =
\mathrm{A}^{-1} - \mathrm{B} \left( \mathrm{D}^{-1} + \mathrm{C} \mathrm{A}^{-1} \mathrm{B} \right)^{-1} \mathrm{C} \mathrm{A}^{-1}
\]

この公式について本には「証明は省く」だとか「両辺に\(\left( \mathrm{A} + \mathrm{B} \mathrm{D} \mathrm{C} \right)\)を掛けて確かめてみよ」とかしか書いておらず、『証明しなきゃ使っちゃダメ』理論によると証明しないで公式を使うと怖い先生にタバコを投げつけられるのでここに証明します。

またSchur補行列によるブロック行列の逆行列の補題からのアプローチを用いて証明したのでせっかくなのでそっちも示しておきます。

Lemma.ⅰ : Schur補行列

任意の正方行列\(P\)に対し次のような2x2区分行列への変換を行う。
\[
P = \left[ \begin{array}{cc} A & B \\ C & D \end{array} \right]
\]
ここでAは正則にとられているものとする。この時\(P\)の逆行列\(P^{-1}\)は
\[ P^{-1} = \left[ \begin{array}{cc} A^{-1} + A^{-1} B S^{-1} CA^{-1} & -A^{-1}BS^{-1} \\ -S^{-1}CA^{-1} & S^{-1} \end{array} \right]
\]
ただし\( S := D - CA^{-1}B \)であり、これを部分行列Aに対するSchur補行列という。

同様にDを正則にとるとき、\(P^{-1}\)は
\[
P^{-1} = \left[ \begin{array}{cc} S^{-1} & -S^{-1}BD^{-1} \\ -D^{-1}CS^{-1} & D^{-1}+D^{-1}CS^{-1}BD^{-1} \end{array} \right]
\]
ただし\(S := A - BD^{-1}C \)であり、これは部分行列Dに対するSchur補行列である。

証明ここから

\(P\)を同型の区分行列に分割し、そのLDU分解を考える。
\[
P = \left[ \begin{array}{cc} I & O \\ W & I \end{array} \right]
\left[ \begin{array}{cc} X & O \\ O & Y \end{array} \right]
\left[ \begin{array}{cc} I & Z \\ O & I \end{array} \right]
=: LDU
\]

さて、Lの逆行列について考えよう。L行列に対して同型の区分行列の形で逆行列\(L^{-1}\)が存在するとき、
\[
L^{-1} := \left[ \begin{array}{cc} S & T \\ U & V \end{array} \right]
\]
とおく。\(L^{-1}\)について
\[
L L^{-1}=\left[ \begin{array}{cc} I & O \\ W & I \end{array} \right]
\left[ \begin{array}{cc} S & T \\ U & V \end{array} \right]
= \left[ \begin{array}{cc} S & T \\ WS + U & WT + V \end{array} \right]
= \left[ \begin{array}{cc} I & O \\ O & I \end{array} \right]
\]
が成り立ち、要素の対応から\(S = I, T = O, U = -W, V = I\)

これより以下の系が導ける。

Corollary.ⅰ

任意の区分L行列に対し
\[
\left[ \begin{array}{cc} I&O \\ W&I \end{array} \right]^{-1}
= \left[ \begin{array}{cc} I & O \\ -W & I \end{array} \right]
\]

また\(D^{-1}\)について同様に
\[
DD^{-1} = \left[ \begin{array}{cc} X&O \\ O&Y \end{array} \right]
\left[ \begin{array}{cc} S&T \\ U&V \end{array} \right]
=\left[ \begin{array}{cc} XS&XT \\ YU&YV \end{array} \right]
=\left[ \begin{array}{cc} I&O \\ O&I \end{array} \right]
\]
これより以下がいえる。

Corollary.ⅱ

任意の区分D行列に対し、
\[
\left[ \begin{array}{cc} X&O \\ O&Y \end{array} \right]^{-1}
=\left[ \begin{array}{cc} X^{-1}&O \\ O&Y^{-1} \end{array} \right]
\]
U行列についても同様に

Corollary.ⅲ

任意の区分U行列に対し
\[
\left[ \begin{array}{cc} I&Z \\ O&I \end{array} \right]^{-1}
=\left[ \begin{array}{cc} I&-Z \\ O&I \end{array} \right]
\]

LDU分解された\(P^{-1}\)についてその積を計算すると
\begin{eqnarray*}
P^{-1} &=& \left[ \begin{array}{cc} I & O \\ W & I \end{array} \right]
\left[ \begin{array}{cc} X & O \\ O & Y \end{array} \right]
\left[ \begin{array}{cc} I & Z \\ O & I \end{array} \right] \\
&=&
\left[ \begin{array}{cc} X &XZ \\ WX &WXZ + Y \end{array} \right]
\end{eqnarray*}

\(P\)の要素との対応から
\[
\left\{ \begin{array}{l}
A = X \\
B = XZ \\
C = WX \\
D = WXZ+Y
\end{array} \right.
\]
\(A\)は正則であることを用い変形すると、
\[
\left\{ \begin{array}{l}
W = CA^{-1} \\
X = A^{-1} \\
Y = D-CA^{-1}B \\
Z = A^{-1}B
\end{array} \right.
\]

また\(P^{-1}\)について
\begin{eqnarray*}
P^{-1} &=& \left( \left[ \begin{array}{cc} I & O \\ W & I \end{array} \right]
\left[ \begin{array}{cc} X & O \\ O & Y \end{array} \right]
\left[ \begin{array}{cc} I & Z \\ O & I \end{array} \right] \right)^{-1} \\
&=&
\left[ \begin{array}{cc} I & Z \\ O & I \end{array} \right]^{-1}
\left[ \begin{array}{cc} X & O \\ O & Y \end{array} \right]^{-1}
\left[ \begin{array}{cc} I & O \\ W & I \end{array} \right]^{-1}
\end{eqnarray*}
Corollary.ⅰ,ⅱ,ⅲを用い
\begin{eqnarray*}
P^{-1} &=&
\left[ \begin{array}{cc} I&-Z \\ O&I \end{array} \right]
\left[ \begin{array}{cc} X^{-1}&O \\O &Y^{-1} \end{array} \right]
\left[ \begin{array}{cc} I&O \\ -W&I \end{array} \right] \\
&=& \left[ \begin{array}{cc}A^{-1}+A^{-1}B(D-CA^{-1}B)^{-1}CA^{-1} &-A^{-1}B(D-CA^{-1}B)^{-1} \\ -(D-CA^{-1}B)^{-1}CA^{-1} & (D-CA^{-1}B)^{-1} \end{array} \right] \\
&=& \left[ \begin{array}{cc} A^{-1} + A^{-1} B S^{-1} CA^{-1} & -A^{-1}BS^{-1} \\ -S^{-1}CA^{-1} & S^{-1} \end{array} \right]
\end{eqnarray*}
証明終■

Dを正則にとったときについては同様なので省略します。僕でもできるので大丈夫です。

さて、Woodburyの公式の逆行列の中身はなんだかSchur補行列に似てますね。後は一本道です。

証明ここから

\[
M = \left[ \begin{array}{cc} A&B \\ C&-D^{-1} \end{array} \right]
\]
なる区分正方行列Mを考える。ここでA,Dは共に正則である。Dに対するSchur補行列\(S = A + BDC\)を用いて、
\(M^{-1}\)を書き表すと
\[
M^{-1} = \left[ \begin{array}{cc} S^{-1}&S^{-1}BD \\ DCS^{-1}&DCS^{-1}BD-D \end{array} \right]
\]
Aに対するSchur補行列\(S' = -D^{-1}-CA^{-1}B\)を用いてM^{-1}を表すと、
\[
M^{-1} = \left[ \begin{array}{cc} A^{-1}+A^{-1}BS'CA^{-1} & -A^{-1}BS'^{-1} \\ -S'^{-1}CA & S'^{-1} \end{array} \right]
\]
\(M^{-1}_{1, 1}\)の要素の対応から、
\begin{eqnarray*}
S^{-1} &=& A^{-1}+A^{-1}BS'^{-1}CA^{-1} \\
(A+BDC)^{-1} &=& A^{-1}-A^{-1}B(D^{-1}+CA^{-1}B)^{-1}CA^{-1}
\end{eqnarray*}
よりSherman-Morrison-Woodburyの公式が導かれる。

証明終■

この公式はAがおっきいけれど対角行列だったりして逆行列が簡単に求まって、B、Cが疎な縦長横長の行列だったりするときに右辺の評価は左辺より簡単になるよーっていう便利なやつですね。
そうですね主に\(\mathrm{\Sigma}\)あたりに有用なんじゃないでしょうか。