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

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

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

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

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

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

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

$$\begin{array}{}(\ast )& (A+\mathbf{u}{\mathbf{v}}^{\mathsf{T}}{)}^{-1}=A^{-1}-\frac{A^{-1}\mathbf{u}{\mathbf{v}}^{\mathsf{T}}{A}^{-1}}{1+{\mathbf{v}}^{\mathsf{T}}{A}^{-1}\mathbf{u}}.\end{array}$$

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

$$\begin{array}{rl}XY& =(A+\mathbf{u}{\mathbf{v}}^T)(A^{-1}-\frac{A^{-1}\mathbf{u}{\mathbf{v}}^T{A}^{-1}}{1+{\mathbf{v}}^T{A}^{-1}\mathbf{u}})\\ & =A{A}^{-1}+\mathbf{u}{\mathbf{v}}^T{A}^{-1}-\frac{A{A}^{-1}\mathbf{u}{\mathbf{v}}^T{A}^{-1}+\mathbf{u}{\mathbf{v}}^T{A}^{-1}\mathbf{u}{\mathbf{v}}^T{A}^{-1}}{1+{\mathbf{v}}^T{A}^{-1}\mathbf{u}}\\ & =I+\mathbf{u}{\mathbf{v}}^T{A}^{-1}-\frac{\mathbf{u}{\mathbf{v}}^T{A}^{-1}+\mathbf{u}{\mathbf{v}}^T{A}^{-1}\mathbf{u}{\mathbf{v}}^T{A}^{-1}}{1+{\mathbf{v}}^T{A}^{-1}\mathbf{u}}\\ & =I+\mathbf{u}{\mathbf{v}}^T{A}^{-1}-\frac{\mathbf{u}(1+{\mathbf{v}}^T{A}^{-1}\mathbf{u}){\mathbf{v}}^T{A}^{-1}}{1+{\mathbf{v}}^T{A}^{-1}\mathbf{u}}\\ & =I+\mathbf{u}{\mathbf{v}}^T{A}^{-1}-\mathbf{u}{\mathbf{v}}^T{A}^{-1}\\ & =I\end{array}$$

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

$$YX=(A^{-1}-\frac{A^{-1}\mathbf{u}{\mathbf{v}}^{\mathsf{T}}{A}^{-1}}{1+{\mathbf{v}}^{\mathsf{T}}{A}^{-1}\mathbf{u}})(A+\mathbf{u}{\mathbf{v}}^{\mathsf{T}})=I.$$

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

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

$$0\ne det(A+\mathbf{u}{\mathbf{v}}^{\mathsf{T}})=det(A)(1+{\mathbf{v}}^{\mathsf{T}}{A}^{-1}\mathbf{u})$$

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

우드버리 공식(Woodbury formula)

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

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

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

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

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

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

$$\begin{array}{}(\ast \ast )& {(A+UC{V}^{\mathsf{T}})}^{-1}=A^{-1}-A^{-1}U{(C^{-1}+V^{\mathsf{T}}{A}^{-1}U)}^{-1}{V}^{\mathsf{T}}{A}^{-1}.\end{array}$$

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

$$\left[\begin{array}{cc}A& U\\ V^{\mathsf{T}}& -C^{-1}\end{array}\right]\left[\begin{array}{c}X\\ Y\end{array}\right]=\left[\begin{array}{c}I\\ O\end{array}\right].$$

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

$$AX+UY=I,V^{\mathsf{T}}X-C^{-1}Y=O.$$

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

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

$$X=A^{-1}-A^{-1}U{(C^{-1}+V^{\mathsf{T}}{A}^{-1}U)}^{-1}{V}^{\mathsf{T}}{A}^{-1}$$

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

$$(A+UC{V}^{\mathsf{T}}{)}^{-1}=X=A^{-1}-A^{-1}U{(C^{-1}+V^{\mathsf{T}}{A}^{-1}U)}^{-1}{V}^{\mathsf{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^{\mathsf{T}}{A}^{-1}U{)}^{-1}$의 존재성이 보장되어야 한다. 하지만 행렬 $C$와 $C^{-1}+V^{\mathsf{T}}{A}^{-1}U$의 크기가 모두 $k\times k$이므로, 만약 $k$값이 작다면 이 두 행렬의 역행렬의 존재성을 확인하는 것이 $(A+UC{V}^{\mathsf{T}}{)}^{-1}$의 역행렬의 존재성을 직접 확인하는 것보다 계산적으로 이득임을 알 수 있다.