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}$

となります。