機械学習に詳しくなりたいブログ

機械学習や数学について勉強した内容を中心に書きます。100%趣味です。記事は数学的に厳密でなかったり誤りを含んでいるかもしれません。ご指摘頂ければ幸いです。

Woodburyの公式

以下の式


(\mathbf{A}+\mathbf{B}\mathbf{C}\mathbf{D})^{-1} = \mathbf{A}^{-1} - \mathbf{A}^{-1}\mathbf{B}(\mathbf{C}^{-1}+\mathbf{D}\mathbf{A}^{-1}\mathbf{B})^{-1}\mathbf{D}\mathbf{A}^{-1} \tag{1}

は、Woodburyの公式と呼ばれます。左辺の計算より、右辺の計算が楽な場合において用いられるようです。

以下、導出を確認しました。

まず、(\mathbf{I}+\mathbf{P})^{-1}を考えます。


\begin{eqnarray*}
(\mathbf{I}+\mathbf{P})^{-1} &=& (\mathbf{I}+\mathbf{P})^{-1}(\mathbf{I}+\mathbf{P}-\mathbf{P}) \tag{3} \\
&=& (\mathbf{I}+\mathbf{P})^{-1} \left\{(\mathbf{I}+\mathbf{P})-\mathbf{P} \right\} \tag{4} \\
&=& \mathbf{I}-(\mathbf{I}+\mathbf{P})^{-1}\mathbf{P} \tag{5}
\end{eqnarray*}

です。次に \mathbf{P}+\mathbf{P}\mathbf{Q}\mathbf{P}を考えます。


\begin{eqnarray*}
\mathbf{P}+\mathbf{P}\mathbf{Q}\mathbf{P} &=& \mathbf{P}(\mathbf{I}+\mathbf{Q}\mathbf{P}) \tag{6} \\
&=& (\mathbf{I}+\mathbf{P}\mathbf{Q})\mathbf{P} \tag{7} \\
\end{eqnarray*}

ですから、式(6)、(7)より


 \mathbf{P} = (\mathbf{I}+\mathbf{P}\mathbf{Q}) \mathbf{P}  (\mathbf{I}+\mathbf{P}\mathbf{Q})^{-1} \tag{8}


 (\mathbf{I}+\mathbf{P}\mathbf{Q})^{-1} \mathbf{P} = \mathbf{P}  (\mathbf{I}+\mathbf{P}\mathbf{Q})^{-1} \tag{9}

です。

ここからが本題で、(\mathbf{A}+\mathbf{B}\mathbf{C}\mathbf{D})^{-1}を変形していきます。


\begin{eqnarray*}
(\mathbf{A}+\mathbf{B}\mathbf{C}\mathbf{D})^{-1} &=& \left\{ \mathbf{A}(\mathbf{I}+\mathbf{A}^{-1}\mathbf{B}\mathbf{C}\mathbf{D})\right\}^{-1} \tag{10}
\end{eqnarray*}

で、逆行列の定理の式(1)より、


式(10)= (\mathbf{I}+\mathbf{A}^{-1}\mathbf{B}\mathbf{C}\mathbf{D})^{-1}\mathbf{A}^{-1} \tag{11}

です。ここで式(5)を使えば、


式(11)= \left\{ \mathbf{I}-(\mathbf{I}+\mathbf{A}^{-1}\mathbf{B}\mathbf{C}\mathbf{D})^{-1}\mathbf{A}^{-1}\mathbf{B}\mathbf{C}\mathbf{D} \right\}\mathbf{A}^{-1} \tag{12}

となります。これを展開すれば


式(12)= \mathbf{A}^{-1}  - ( \mathbf{I}+\mathbf{A}^{-1}\mathbf{B}\mathbf{C}\mathbf{D})^{-1}\mathbf{A}^{-1}\mathbf{B}\mathbf{C}\mathbf{D} \mathbf{A}^{-1} \tag{13}

です。ここで式(9)の関係を2回繰り返し使って、


\begin{eqnarray*}
式(13) &=&  \mathbf{A}^{-1}  - \mathbf{A}^{-1}( \mathbf{I}+\mathbf{B}\mathbf{C}\mathbf{D}\mathbf{A}^{-1})^{-1}\mathbf{B}\mathbf{C}\mathbf{D} \mathbf{A}^{-1}  \tag{14} \\
&=&  \mathbf{A}^{-1}  - \mathbf{A}^{-1}\mathbf{B}( \mathbf{I}+\mathbf{C}\mathbf{D}\mathbf{A}^{-1}\mathbf{B})^{-1}\mathbf{C}\mathbf{D} \mathbf{A}^{-1} \tag{15}
\end{eqnarray*}

となります。ここで式(15)の( \mathbf{I}+\mathbf{C}\mathbf{D}\mathbf{A}^{-1}\mathbf{B})^{-1}\mathbf{C}について変形していくと、


\begin{eqnarray*}
( \mathbf{I}+\mathbf{C}\mathbf{D}\mathbf{A}^{-1}\mathbf{B})^{-1}\mathbf{C} &=& ( \mathbf{C}\mathbf{C}^{-1}+\mathbf{C}\mathbf{D}\mathbf{A}^{-1}\mathbf{B})^{-1}\mathbf{C} \tag{16} \\
&=&   \left\{ \mathbf{C} (\mathbf{C}^{-1}+\mathbf{D}\mathbf{A}^{-1}\mathbf{B}) \right\} ^{-1}\mathbf{C}  \tag{17} \\
&=&  (\mathbf{C}^{-1}+\mathbf{D}\mathbf{A}^{-1}\mathbf{B})^{-1} \mathbf{C}^{-1}\mathbf{C} \tag{18} \\
&=&  (\mathbf{C}^{-1}+\mathbf{D}\mathbf{A}^{-1}\mathbf{B})^{-1} \tag{19}
\end{eqnarray*}

となります。途中で逆行列の定理の式(1)を使っています。そして式(19)と式(15)より、


(\mathbf{A}+\mathbf{B}\mathbf{C}\mathbf{D})^{-1} = \mathbf{A}^{-1} - \mathbf{A}^{-1}\mathbf{B}(\mathbf{C}^{-1}+\mathbf{D}\mathbf{A}^{-1}\mathbf{B})^{-1}\mathbf{D}\mathbf{A}^{-1} \tag{20}

となります。