셔먼-모리슨-우드버리 공식(Sherman–Morrison-Woodbury formula)

      Comments Off on 셔먼-모리슨-우드버리 공식(Sherman–Morrison-Woodbury formula)

지난 글에서는 주어진 행렬 $A$의 행렬식과 역행렬을 알고 있을 때, 이 행렬을 계수(rank)가 1인 행렬 $\mathbf{u}_n \mathbf{v}_n^\T$을 이용하여 갱신한 새로운 행렬 $A + \mathbf{u}_n \mathbf{v}_n^\T$의 행렬식을 구하는 방법에 대하여 알아보았다. 이번 글에서는 이 새로운 행렬의 역행렬을 구하는 방법을 제공하는 셔먼-모리슨 공식(Sherman–Morrison formula)에 대해서 알아보도록 하자.

 

셔먼-모리슨 공식(Sherman–Morrison formula)

1949년 셔먼(Jack Sherman)과 모리슨(Winifred J. Morrison)이 발표한 이 공식은 주어진 행렬 $A$의 역행렬을 알고 있을때, $A + \mathbf{u} \mathbf{v}^{\T}$의 역행렬을 비교적 빠르게 구할 수 있는 방법을 제공한다.

 

정리. 셔먼-모리슨 공식(Sherman–Morrison formula)

$A \in \R^{n \times n}$가 가역행렬(invertible matrix)이고, $\mathbf{u},\, \mathbf{v} \in \R^n$가 열벡터라 하자. 그러면 $A + \mathbf{u} \mathbf{v}^\T$의 역행렬이 존재할 필요충분조건은 $1 + \mathbf{v}^\T A^{-1} \mathbf{u} \neq 0$인 것이다.

나아가 $A + \mathbf{u} \mathbf{v}^\T$의 역행렬이 존재한다면 다음 공식이 성립한다.

\[ (A + \mathbf{u} \mathbf{v}^{\T})^{-1} = A^{-1} - \frac{A^{-1} \mathbf{u} \mathbf{v}^{\T}A^{-1}}{1 + \mathbf{v}^{\T} A^{-1} \mathbf{u}}. \tag*{$(\ast)$}\]

 

증명. 먼저 $1 + \mathbf{v}^\T A^{-1} \mathbf{u} \neq 0$이라 가정하자. (이 경우, 사실 행렬식 보조정리(matrix determinant lemma)에 의해 행렬 $A + \mathbf{u} \mathbf{v}^{\T}$의 역행렬이 존재한다는 사실은 바로 얻을 수 있지만, 역행렬이 실제로 어떻게 구해지는지는 알 수 없다.) 그러면 식 $(\ast)$가 잘 정의된다. 이제 $X = (A + \mathbf{u} \mathbf{v}^{\T})$이고 $Y$를 식 $(\ast)$의 오른변으로 정의하자. 그러면 $1 + \mathbf{v}^\T A^{-1} \mathbf{u}$가 스칼라(scalar)라는 사실로부터

\begin{align*} XY &= (A+\mathbf{u}\mathbf{v}^{T}) \left(A^{-1}-{A^{-1}\mathbf{u}\mathbf{v}^{T}A^{-1} \over 1+\mathbf{v}^{T}A^{-1}\mathbf{u}}\right) \\[6pt] &= AA^{-1}+\mathbf{u}\mathbf{v}^{T}A^{-1}-{AA^{-1}\mathbf{u}\mathbf{v}^{T}A^{-1}+\mathbf{u}\mathbf{v}^{T}A^{-1}\mathbf{u}\mathbf{v}^{T}A^{-1} \over 1+\mathbf{v}^{T}A^{-1}\mathbf{u}} \\[6pt] &= I+\mathbf{u}\mathbf{v}^{T}A^{-1}-{\mathbf{u}\mathbf{v}^{T}A^{-1}+\mathbf{u}\mathbf{v}^{T}A^{-1}\mathbf{u}\mathbf{v}^{T}A^{-1} \over 1+\mathbf{v}^{T}A^{-1}\mathbf{u}} \\[6pt] &= I+\mathbf{u}\mathbf{v}^{T}A^{-1}-{\mathbf{u}(1+\mathbf{v}^{T}A^{-1}\mathbf{u})\mathbf{v}^{T}A^{-1} \over 1+\mathbf{v}^{T}A^{-1}\mathbf{u}} \\[6pt] &= I+\mathbf{u}\mathbf{v}^{T}A^{-1}-\mathbf{u}\mathbf{v}^{T}A^{-1} \\[6pt] &= I \end{align*}

를 얻는다. 마찬가지 방법으로

\[ YX = \left( A^{-1} - \frac{A^{-1} \mathbf{u} \mathbf{v}^{\T}A^{-1}}{1 + \mathbf{v}^{\T} A^{-1} \mathbf{u}} \right) (A+\mathbf{u} \mathbf{v}^{\T}) = I. \]

따라서 $XY = YX = I$이므로 $X = A + \mathbf{u} \mathbf{v}^{\T}$의 역행렬이 존재함을 알 수 있다.

이제 반대로 $A + \mathbf{u} \mathbf{v}^\T$의 역행렬이 존재한다고 가정하자. 그러면 $A + \mathbf{u} \mathbf{v}^\T$의 행렬식이 $0$이 아님을 알수 있다. 이제 행렬식 보조정리에 의해

\[ 0 \neq \det(A + \mathbf{u}\mathbf{v}^\T) = \det(A) (1 + \mathbf{v}^\T A^{-1} \mathbf{u}) \]

이므로 $1 + \mathbf{v}^\T A^{-1} \mathbf{u} \neq 0$를 바로 얻는다..

 

우드버리 공식(Woodbury formula)

셔먼-모리슨 공식은 우드버리 공식의 특수한 경우로 볼 수 있는데, 이 공식은 1950년 우드버리(Max A. Woodbury)에 의해 처음으로 발표되었다. 셔먼-모리슨 공식은 주어진 행렬 $A$를 계수가 1인 행렬로 갱신했을 경우를 다루었지만, 더 나아가 우드버리 공식은 주어진 행렬 $A$를 계수가 $1 \leq k \leq n$인 행렬로 갱신했을 경우를 다룬다.

 

먼저 다음의 사실을 증명 없이 받아들이기로 하자.

  1. $A \in \R^{n \times n}$, $B \in \R^{n \times k}$, $C \in \R^{k \times n}$, $D \in \R^{k \times k}$라 하자. 만약 $A$의 역행렬이 존재하는 경우, \[ \det {\begin{pmatrix} A & B \\ C & D \end{pmatrix}} = \det(A) \det(D - CA^{-1}B). \] 만약 $D$의 역행렬이 존재하는 경우, \[ \det {\begin{pmatrix} A & B \\ C & D \end{pmatrix}} = \det(D) \det(A - BD^{-1}C). \]

 

정리. 우드버리 공식(Woodbury formula)

$A \in \R^{n \times n}$와 $C \in \R^{k \times k}$ 가역행렬(invertible matrix)이고, $U,\, V \in \R^{n \times k}$라 하자. 그러면 $A + UCV^{\T}$의 역행렬이 존재할 필요충분조건은 $C^{-1} + V^{\T}A^{-1}U$의 역행렬이 존재하는 것이다.

나아가 다음 공식이 성립한다.

\[ \left(A+UCV^{\T} \right)^{-1} = A^{-1} - A^{-1}U \left(C^{-1}+V^{\T}A^{-1}U \right)^{-1} V^{\T}A^{-1}. \tag*{$(\ast\ast)$} \]

 

증명. 셔먼-모리슨 공식을 증명했을 때와 비슷하게 직접 계산을 통해 위 공식이 성립함을 보일 수도 있지만, 이번에는 다른 방법을 이용하여 공식 $(\ast\ast)$을 증명해 보도록 하자. 먼저 아래와 같이 블록행렬(block matrix)들로 이루어진 방정식을 생각해 보자.

\[ \begin{bmatrix} A & U \\ V^{\T} & -C^{-1} \end{bmatrix}\begin{bmatrix} X \\ Y \end{bmatrix} = \begin{bmatrix} I \\ O \end{bmatrix}. \]

이 때, $X \in \R^{n \times n}$이고 $Y \in \R^{k \times n}$이다. 또한 위 방정식의 왼변에 있는 블록행렬의 행렬식이 $0$이 아니므로 위 방정식의 해가 (유일하게) 존재한다는 사실을 알 수 있다. 이제 위 방정식을 전개하면,

\[ AX + UY = I, \qquad V^{\T}X - C^{-1}Y = O. \]

여기서 두번째 식을 먼저 풀면, $Y = CV^{\T}X$를 얻고 이를 첫번째 식에 대입하면, $(A + UCV^{\T})X = I$를 얻는다. 따라서 $X$가 우리가 원하는 $A + UCV^{\T}$의 역행렬이 됨을 알 수 있다.

 

이제 $X$를 다른 방법으로 구해보자. 이번에는 첫번째 식을 먼저 풀어 $X = A^{-1}(I-UY)$를 얻는다. 이제 이를 두번째 식에 대입하고 $Y$에 대하여 정리하면, $Y = (C^{-1}+ V^{\T}A^{-1}U)^{-1}V^{\T}A^{-1}$를 얻는다. 이제 마지막으로 이 $Y$ 값을 첫번째 식에 다시 대입하고 $X$에 대하여 정리하면,

\[ X = A^{-1}-A^{-1}U \left( C^{-1} + V^{\T}A^{-1}U \right)^{-1} V^{\T} A^{-1} \]

를 얻는다. 따라서 방정식의 해의 유일성에 의해,

\[ (A+UCV^{\T})^{-1} = X = A^{-1} - A^{-1}U \left( C^{-1} + V^{\T}A^{-1}U \right)^{-1} V^{\T} A^{-1}. \]

따라서 공식 $(\ast\ast)$가 성립한다..

 

참고1. 우드버리 공식의 특수한 경우로, $k=1$이고 $C = [1]$이라고 가정하면, 셔먼-모리슨 공식을 얻을 수 있다. 이과 같은 이유로 셔먼-모리슨 공식과 우드버리 공식을 합쳐서 셔먼-모리슨-우드버리 공식(Sherman-Morrison-Woodbury formula), 또는 간단히 역행렬 보조정리(matrix inversion lemma)라고도 한다.

 

참고2. 우드버리 공식이 성립하기 위해서는 $A^{-1}$의 존재성과 함께 $C^{-1}$과 $(C^{-1} + V^{\T}A^{-1}U)^{-1}$의 존재성이 보장되어야 한다. 하지만 행렬 $C$와 $C^{-1} + V^{\T}A^{-1}U$의 크기가 모두 $k \times k$이므로, 만약 $k$값이 작다면 이 두 행렬의 역행렬의 존재성을 확인하는 것이 $(A + UCV^{\T})^{-1}$의 역행렬의 존재성을 직접 확인하는 것보다 계산적으로 이득임을 알 수 있다.