Sherman-Morrisonの公式の導出

Kalman-filterをはじめとする、逐次的な2乗誤差最小化に基づくリアルタイム信号処理では、損失関数を構成する2次形式の基になる行列の逆行列を高速で求める必要がある。そのような状況で頼りになるSherman-Morrisonの公式を導出する。Woodburyの公式の特別な場合として片付けられるのが一般的だが、本記事ではJordan分解を用いて導出してみる。

補題1(行列式の中身のサイズ変更)

主張

$A\in {\mathbb{R}}^{n\times m},B\in {\mathbb{R}}^{m\times n}$に対して$|I_m-AB|=|I_n-BA|$

導出

$$M:=\left[\begin{array}{cc}{I}_n& A\\ B& I_m\end{array}\right]$$

とすると

$$detM=det\left(M\left[\begin{array}{cc}{I}_n& -A\\ O& I_m\end{array}\right]\right)=det\left[\begin{array}{cc}{I}_n& O\\ B& I_m-BA\end{array}\right]=|I_m-BA|$$

一方で

$$detM=det\left(M\left[\begin{array}{cc}{I}_n& O\\ -B& I_m\end{array}\right]\right)=det\left[\begin{array}{cc}{I}_n-AB& A\\ & I_m\end{array}\right]=|I_n-AB|$$

$\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.1.0/svg/25fb.svg">}$

補題2(Sherman-Morrisonの公式の特別な場合)

主張

$\mathit{u},\mathit{v}\in {\mathbb{C}}^m,1+{\mathit{v}}^{\ast }\mathit{u}\ne 0$とするとき次式が成り立つ。

$$(I+\mathit{u}{\mathit{v}}^{\ast }{)}^{-1}=I–\frac{1}{1+{\mathit{v}}^{\ast }\mathit{u}}\mathit{u}{\mathit{v}}^{\ast }$$

導出

$\mathit{u}{\mathit{v}}^{\ast }=O$のときは定理の主張は明らかに成り立つ。以下では$\mathit{u}{\mathit{v}}^{\ast }\ne O$とする。仮定$1+{\mathit{v}}^{\ast }\mathit{u}\ne 0$と前掲の補題1より$I+\mathit{u}{\mathit{v}}^{\ast }$には逆行列が存在する。$\mathit{u}{\mathit{v}}^{\ast }$の階数は1であり($\mathrm{Img}\left(\mathit{u}{\mathit{v}}^{\ast }\right)=\mathrm{span}\left[\mathit{u}\right]$)、唯一の固有値は${\mathit{v}}^{\ast }\mathit{u}$である(対応する固有ベクトルは$\mathit{u}$)。よって$\mathit{u}{\mathit{v}}^{\ast }$をJordan分解すると、適当な正則行列$J$を用いて次のように表せる。

$$\mathit{u}{\mathit{v}}^{\ast }=J\left[\begin{array}{cc}{\mathit{v}}^{\ast }\mathit{u}& {\mathbf{0}}^{\mathrm{\top }}\\ \mathbf{0}& O\end{array}\right]J^{-1}=:J\mathrm{\Lambda }{J}^{-1}$$

よって

$$\begin{array}{rl}(I+\mathit{u}{\mathit{v}}^{\ast }{)}^{-1}& =J(I+\mathrm{\Lambda }{)}^{-1}{J}^{-1}=J{\left[\begin{array}{cc}1+{\mathit{v}}^{\ast }\mathit{u}& {\mathbf{0}}^{\mathrm{\top }}\\ \mathbf{0}& I\end{array}\right]}^{-1}{J}^{-1}=J\left[\begin{array}{cc}\frac{1}{1+{\mathit{v}}^{\ast }\mathit{u}}& {\mathbf{0}}^{\mathrm{\top }}\\ \mathbf{0}& I\end{array}\right]J^{-1}\\ & =J\frac{1}{1+{\mathit{v}}^{\ast }\mathit{u}}\left[\begin{array}{cc}1& {\mathbf{0}}^{\mathrm{\top }}\\ \mathbf{0}& (1+{\mathit{v}}^{\ast }\mathit{u})I\end{array}\right]J^{-1}=J\frac{1}{1+{\mathit{v}}^{\ast }\mathit{u}}((1+{\mathit{v}}^{\ast }\mathit{u})I–\mathrm{\Lambda })J^{-1}\\ & =I–\frac{1}{1+{\mathit{v}}^{\ast }\mathit{u}}\mathit{u}{\mathit{v}}^{\ast }\end{array}$$

$\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.1.0/svg/25fb.svg">}$

Sherman-Morrisonの公式

主張

$A\in {\mathbb{C}}^{m\times m},\mathit{u},\mathit{v}\in {\mathbb{C}}^m$とする。$A$は可逆であるとし、$1+{\mathit{v}}^{\ast }{A}^{-1}\mathit{u}\ne 0$とする。このとき次式が成り立つ。

$$(A+\mathit{u}{\mathit{v}}^{\ast }{)}^{-1}=\left(I–\frac{1}{1+{\mathit{v}}^{\ast }{A}^{-1}\mathit{u}}{A}^{-1}\mathit{u}{\mathit{v}}^{\ast }\right)A^{-1}$$

導出

$A+\mathit{u}{\mathit{v}}^{\ast }=A(I+A^{-1}\mathit{u}{\mathit{v}}^{\ast })$だから$(A+\mathit{u}{\mathit{v}}^{\ast }{)}^{-1}=(I+A^{-1}\mathit{u}{\mathit{v}}^{\ast }{)}^{-1}{A}^{-1}$であり、1つ目の因子に前掲の補題2を適用すればよい。

$\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.1.0/svg/25fb.svg">}$