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}\)あたりに有用なんじゃないでしょうか。
perlにおけるprivateなメンバ関数
最近MooseやMouseから離れて、かみさまの祝福にあやかったコードを書いています。
そこでプライベート関数の書き方を忘れていたのでめもめも。とその過程で生まれた疑問があるのでそれについて。
さてここはperlの夢と魔法の国です。もちろんこんな邪悪なコードは動きません。
package Hoge; ~~~ private sub SecretMethod { ~~~ }
サブルーチンは全部神様の祝福を受けてblessされてしまいます。
そこでクラスメソッドの呼び出し規則の影響を受けないように無名関数のリファレンスにてこれを実現します。
素敵なコード例は以下
package Hoge; sub new { my $class = shift; return bless {}, $class; } # private method my $secret_method = sub{ #code reference print "試験始まる前と比べて体重が5kgも増えました(実話)\n"; } sub expose_secret { my $self = shift; $self->$secret_method; #秘密を暴いてやる！！ } 1; package main; use Hoge; my $obj = new Hoge::; $obj->expose_secret; # lady's secret has been exposed! # $obj->secret_method, $obj->{secret_method} .... can't call, woohoo :-D
といった具合です。乙女の秘密は守られました。
まあこの用途では隠す必要もないでしょうが、十分に入用だと思います。
この方法で生成したプライベートメソッドはむりやりblessでもしない限りインスタンス側から不可視です。一応直接呼ぶとするなら
sub new{ my $class = shift; return bless { secret => $secret_method, }, $class; } ~~ # main側 &{$obj->{secret}}; # yikes!!
ぐらい無理矢理な手段になります。まあ my $hoge = sub{ を sub hoge{にしてやれば外から見えますけどね。
とまあ、こういった具合でprivateなメソッドが書けるわけですが
「じゃあprotectedなメソッドってどうやって書くんだろう、Attribute::Protectedじゃなくこの形で出来ないのかな」
と思いまして、少し試行錯誤してわからなかったので投げます。ちょっと長くなりそうなので続きは以下。
頭の使いすぎで限界感あるのでこのIssueに関しては明日別のエントリで。
Macのタイル型ウィンドウマネージャDivvyがステキ
こないだMBPをOSから綺麗さっぱりクリーンインストールした際に、@kyubuns氏が一時期騒いでいたDivvyというものを導入してみました。
Divvyは画面をタイル型に分割してそのタイル部分にアクティブなウィンドウをその大きさにリサイズしてくれるという品。
これを
こうすると
こうなって
こんなことが簡単にできる素敵っぷり
もちろんDivvyは作業中ショートカットキー一発で呼び出せて
よく使う分割比(左右1:1とか)はDivvyをホットキーで呼び出したあとにもう一発ホットキーでリサイズ可能。
更にその動作自体をグローバルなショートカットにできるのでアプリケーションによってMaximizeの動作が違うMacちゃんに大変お誂え向きなものとなっています。
僕は＜C-S-Space＞にDivvyの呼び出しを割り当てて50%上下左右に＜hjkl＞を… そしてどこからでも＜C-S-m＞でウィンドウを画面いっぱいに最大化 なんて設定にしています。
Divvyは有料($14.00)ですが、Demo版が機能無制限（たぶん）で使えて、起動時と時たまに購入を促すポップアップが出るくらいでまずはどれだけ便利かためしてみるのもアリかなーと。
AppStoreでも購入できてこれなら複数台のMacで同一ライセンスを使いまわせるのでいいかも。
ちなみにWindows版も同価格で出ているようです。
Divvy、薦めた人みんな面白いように絶賛するしAppStoreで\1200という価格分には働いてくれると思います。
