シューア補行列

$A \in \mathbb{C}^{n \times n}, $ $B \in \mathbb{C}^{n \times m}, $ $C \in \mathbb{C}^{m \times n}, $ $D \in \mathbb{C}^{m \times m}, $ $M = \begin{pmatrix} A & B \\ C & D \end{pmatrix}$ とする。このとき、

  • $D$ が正則ならば $M$ は $(1)$ のようにブロック UDL 分解できる。ただし $S_D \equiv A - BD^{-1}C$ とする。さらに $S_D$ も正則ならば $M$ も正則であり $M^{-1}$ は $(2)$ の行列積でかける[注釈1]。
    $$ M = \begin{pmatrix} I & BD^{-1} \\ O & I \end{pmatrix} \begin{pmatrix} S_D & O \\ O & D \end{pmatrix} \begin{pmatrix} I & O \\ D^{-1}C & I \end{pmatrix} \tag{1} $$ $$ M^{-1} = \begin{pmatrix} I & O \\ -D^{-1}C & I \end{pmatrix} \begin{pmatrix} S_D^{-1} & O \\ O & D^{-1} \end{pmatrix} \begin{pmatrix} I & -BD^{-1} \\ O & I \end{pmatrix} \tag{2} $$
  • $A$ が正則ならば $M$ は $(3)$ のようにブロック LDU 分解できる。ただし $S_A \equiv D - CA^{-1}B$ とする。さらに $S_A$ も正則ならば $M$ も正則であり $M^{-1}$ は $(4)$ の行列積でかける[注釈2]。
    $$ M = \begin{pmatrix} I & O \\ CA^{-1} & I \end{pmatrix} \begin{pmatrix} A & O \\ O & S_A \end{pmatrix} \begin{pmatrix} I & A^{-1}B \\ O & I \end{pmatrix} \tag{3} $$ $$ M^{-1} = \begin{pmatrix} I & -A^{-1}B \\ O & I \end{pmatrix} \begin{pmatrix} A^{-1} & O \\ O & S_A^{-1} \end{pmatrix} \begin{pmatrix} I & O \\ -CA^{-1} & I \end{pmatrix} \tag{4} $$
が成り立つ。この $S_D$ を $M$ の $D$ に関するシューア補行列といい、$S_A$ を $M$ の $A$ に関するシューア補行列という。$(2)$ に着目すると、$S_D$ とは、「$M$ の逆行列の左上 $n \times n$ ブロックの逆行列」といえる。

さらに $D, \; S_D, \; A, \; S_A$ が全て正則なとき、$(2), (4)$ の左上 $n \times n$ ブロックの比較から以下が成り立ち、これを Sherman-Morrison-Woodbury の公式という。

$$ \begin{align} S_D^{-1} &= A^{-1} + A^{-1} BS_A^{-1}CA^{-1} \\ (A - BD^{-1}C)^{-1} &= A^{-１} + A^{-1} B(D - CA^{-1}B)^{-1}CA^{-1} \end{align} $$


参考文献

  1. Sherman-Morrison-Woodburyの公式 (Schur補行列) - いんふらけいようじょのえにっき
    • Sherman-Morrison-Woodbury の公式の証明があり、本記事の証明はこの文献の証明と全く同じである。文字の定義は多少異なる。
  2. C. M. ビショップ. パターン認識と機械学習 上. 丸善出版, 2012.[amazon.co.jp]
    • 82ページ（初版第5刷）に「2.3.1 条件付きガウス分布」がある。
  3. 雑記： 分散共分散行列のベイズ更新の話 - クッキーの日記
  4. Christopher Williams, Matthias Seeger. Using the Nyström Method to Speed Up Kernel Machines. In NIPS 2000.[link]
    • グラム行列の Nyström 近似の原論文である。
  5. Schur complement - Wikipedia
    • 英語版 Wikipedia のシューア補行列の記事である。
  6. シューア補行列 - Wikipedia
    • 日本語版 Wikipedia のシューア補行列の記事である。

線形ガウスモデルのベイズ推定におけるシューア補行列

ベイズ推定では観測 $y$ を得た下での状態 $x$ の事後共分散に興味がある。状態 $x$ の事後共分散とは、状態 $x$ と観測 $y$ の同時分布の $y$ を固定して $x$ の共分散のみを取り出したものといえる。$x \in \mathbb{R}^n$ と $y \in \mathbb{R}^m$ の同時分布が多変量正規分布にしたがう場合、同時密度関数は以下のようになる。

$$ p(x, y) \propto \exp \left( - \frac{1}{2} \begin{pmatrix} (x - \mu_x)^{\top} & (y - \mu_y)^{\top} \end{pmatrix} M^{-1} \begin{pmatrix} x - \mu_x \\ y - \mu_y \end{pmatrix} \right) $$
このとき $y$ を固定した $x$ の分布を求めるには上式を平方完成すればよいが、共分散行列については平方完成するまでもなく単に「$M^{-1}$ の左上 $n \times n$ ブロックの逆行列」になる。そしてこれは先述の $S_D$ 、つまり、「$M$ の右下 $m \times m$ ブロックに関するシューア補行列」に他ならない [2]。

具体的に、カルマンフィルタの状況を考える。$x \in \mathbb{R}^n$ を $\mathcal{N}(0, V)$ にしたがう状態、$w \in \mathbb{R}^m$ を $\mathcal{N}(0, R)$ にしたがう状態と独立なノイズ、$H \in \mathbb{R}^{m \times n}$ を観測行列、$y = H x + w$ を観測とする。このときある $y$ を観測した下での $x$ の事後共分散行列を知りたい。$x$ と $y$ の同時密度関数を計算すると以下のようになる [3]。

$$ p(x, y) \propto \exp \left( - \frac{1}{2} \begin{pmatrix} x^{\top} & y^{\top} \end{pmatrix} \begin{pmatrix} V & VH^\top \\ HV & HVH^\top + R \end{pmatrix}^{-1} \begin{pmatrix} x \\ y \end{pmatrix} \right) $$
この共分散行列 $\begin{pmatrix} V & VH^\top \\ HV & HVH^\top + R \end{pmatrix}$ の右下 $m \times m$ ブロックに対するシューア補行列は $V - V H^{\top} (H V H^{\top} + R)^{-1} HV$ である。もっとも、同時分布を考えなくともカルマンフィルタの条件付き分布はベイズの定理よりただちに $(V^{-1} + H^{\top} R^{-1} H)^{-1}$ となり、これに Sherman-Morrison-Woodbury の公式を適用しても同じ結果になる。


グラム行列の Nyström 近似におけるシューア補行列

グラム行列 $K^{(n+m)}$ の左上 $n \times n$ ブロックに関するシューア補行列が、グラム行列の Nyström 近似 $\tilde{K}^{(n+m,n)}$ の右下 $m \times m$ ブロックの近似誤差になっている [4]。

グラム行列 $K^{(n+m)}$ の左上 $n \times n$ ブロックに関するシューア補行列とは、ベイズ推定風に解釈すれば、「仮に $n+m$ 個のデータの分散共分散行列がグラム行列 $K^{(n+m)}$ そのものであったときに、最初の $n$ 個のデータを観測した下での残り $m$ 個のデータの分散共分散行列」といえる。実際、最初の $n$ 個のデータで残り $m$ 個のデータの不確かさ・依存関係が完全に特定できていれば零行列になるはずだし、最初の $n$ 個のデータと残り $m$ 個のデータの内積がゼロであれば（最初の $n$ 個のデータから残り $m$ 個のデータの情報を少しも特定できない状況） $D$ に等しくなるはずである。

結局ベイズ推定でもグラム行列の Nyström 近似でも、シューア補行列とは「一部をみて残りを推定（近似）しようとしたときに残る不確かさ」といえるだろう。


注釈

  1. $M$ を UDL 分解するには以下を $M$ の区分けと比較し $X, Y, Z, W$ を求める。
    $$ M = \begin{pmatrix} I & Z \\ O & I \end{pmatrix} \begin{pmatrix} X & O \\ O & Y \end{pmatrix} \begin{pmatrix} I & O \\ W & I \end{pmatrix} = \begin{pmatrix} I & Z \\ O & I \end{pmatrix} \begin{pmatrix} X & O \\ YW & Y \end{pmatrix} = \begin{pmatrix} X + ZYW & ZY \\ YW & Y \end{pmatrix} $$
    $M$ の逆行列を得るには以下を利用する。
    $$ \begin{pmatrix} I & Z \\ O & I \end{pmatrix}^{-1} = \begin{pmatrix} I & -Z \\ O & I \end{pmatrix}, \; \begin{pmatrix} X & O \\ O & Y \end{pmatrix}^{-1} = \begin{pmatrix} X^{-1} & O \\ O & Y^{-1} \end{pmatrix}, \; \begin{pmatrix} I & O \\ W & I \end{pmatrix}^{-1} = \begin{pmatrix} I & O \\ -W & I \end{pmatrix} $$
  2. $M$ を LDU 分解するには以下を $M$ の区分けと比較する。[注釈1] の $X, Y, Z, W$ とは異なる。
    $$ M = \begin{pmatrix} I & O \\ W & I \end{pmatrix} \begin{pmatrix} X & O \\ O & Y \end{pmatrix} \begin{pmatrix} I & Z \\ O & I \end{pmatrix} = \begin{pmatrix} I & O \\ W & I \end{pmatrix} \begin{pmatrix} X & XZ \\ O & Y \end{pmatrix} = \begin{pmatrix} X & XZ \\ WX & WXZ + Y \end{pmatrix} $$
    $M$ の逆行列を得るには [注釈1] と同様である。