Matrix Inversion Lemma

드디어 선대의 마지막 파트다.

 

Matrix Inversion Lemma란?

이번에 배울 Matrix Inversion Lemma는 Sherman-Morrison-Woodbury formula라 부른다.

직전에 배운 Sherman-Morrison Formula의 일반화판으로 Sherman-Morrison Formula가 이 Matrix Inversion Lemma의 특별한 경우라고 보면 된다.

 

그럼 뭘 일반화 했다는 것일까?

직전에 배운 Sherman-Morrison formula는 한계점이 있다고 정리했었다. 바로 rank-1 Update. 즉, 데이터가 하나 추가될 때만 사용이 가능한 녀석이라고 배웠었다.

그러나 이번에 배울 Matrix Inversion Lemma는 여러 개의 데이터가 추가될 때에도 사용이 가능한 공식이다.

 

아무튼 Matrix Inversion Formula(Sherman-Morrison-Woodbury formula)는 아래와 같다.

$$
\begin{matrix}
(A + UCV)^{-1} = A^{-1}-A^{-1}U(C^{-1}+VA^{-1}U)^{-1}VA^{-1}\\
(A, C, C^{-1}+VA^{-1}U \text{ are invertible})
\end{matrix}
$$

이때 $A: n\times n, U: n\times k , C:k\times k, V: k\times n$를 만족한다.

공식을 외우기는 상당히 쉽지 않다. ㅋㅋ 필요할때만 쓰면 될 듯 하다.

 

이를 증명해보자.

증명

먼저 행렬 $M = \begin{bmatrix}
A & B \\
C & D
\end{bmatrix}$의 역행렬을 구하는 것을 목표로 시작한다. 이때 $A, B, C, D$는 서로 크기가 다른 행렬이다.

이 행렬 $M$의 역행렬을 간단히 구하기 위해 LDU 분해 후 간단히 역행렬을 구하도록 해보자.

먼저 좌 하단 행렬 C를 제거해보자.

$$
M = \begin{bmatrix}
A & B \\
C & D
\end{bmatrix} \rightarrow
\begin{bmatrix}
I & 0 \\
-CA^{-1} & I
\end{bmatrix}
\begin{bmatrix}
A & B \\
C & D
\end{bmatrix} =
\begin{bmatrix}
A & B \\
0 & D - CA^{-1}B
\end{bmatrix}
$$

여기서 우 하단 $D - CA^{-1}B$를 주목해보자. 이 식을 $A$의 Schur complement($M/A$로 표기)라 부른다. (이건 이 문제와 같이 블록 행렬 $A, B, C, D$들로 이루어진 행렬 $M$이 있을때 정의됨.)

계속 LDU의 형태로 분해를 진행해보자.

$$
\begin{align}
\begin{bmatrix}
A & B \\
C & D
\end{bmatrix} &=
\begin{bmatrix}
I & 0 \\
-CA^{-1} & I
\end{bmatrix}
\begin{bmatrix}
A & B \\
0 & D-CA^{-1}B
\end{bmatrix} \\
&= \begin{bmatrix}
I & 0 \\
-CA^{-1} & I
\end{bmatrix}
\begin{bmatrix}
A & 0 \\
0 &D-CA^{-1}B
\end{bmatrix}
\begin{bmatrix}
I & A^{-1}B \\
0 & I
\end{bmatrix}
\end{align}
$$

위 식에서 양변을 inversion 해주면 다음과 같아질 것이다.

$$
\begin{bmatrix}
A & B \\
C & D
\end{bmatrix}^{-1}
= \begin{bmatrix}
I & -A^{-1}B \\
0 & I
\end{bmatrix}
\begin{bmatrix}
A^{-1} & 0 \\
0 & (D - CA^{-1}B)^{-1}
\end{bmatrix}
\begin{bmatrix}
I & 0 \\
-CA^{-1} & I
\end{bmatrix}
$$

이를 전체 곱해보면 우리가 구하고싶은 행렬의 역행렬을 구할 수 있을 것이다.

$$
\begin{align}
\begin{bmatrix}
A & B \\
C & D
\end{bmatrix}^{-1}
&= \begin{bmatrix}
A^{-1} & -A^{-1}B(D-CA^{-1}B)^{-1} \\
0 & (D-CA^{-1}B)^{-1}
\end{bmatrix}
\begin{bmatrix}
I & 0 \\
-CA^{-1} & I
\end{bmatrix} \\
&= \begin{bmatrix}
A^{-1}+A^{-1}B(D-CA^{-1}B)^{-1}CA^{-1} & -A^{-1}B(D-CA^{-1}B)^{-1} \\
-(D-CA^{-1}B)^{-1}CA^{-1} & (D-CA^{-1}B)^{-1}
\end{bmatrix}
\end{align}
$$

LDU로 분해해 얻은 역행렬의 결과는 위와 같다. 반대로 UDL로 분해해 계산한 역행렬을 구한 후 위 결과와 비교해보자.

$$
\begin{bmatrix}
A & B \\
C & D
\end{bmatrix}
\begin{bmatrix}
I & 0 \\
-D^{-1}C & I
\end{bmatrix}
= \begin{bmatrix}
A-BD^{-1}C & B \\
0 & D
\end{bmatrix}
$$

$$
\begin{bmatrix}
A & B \\
C & D
\end{bmatrix} =
\begin{bmatrix}
I & BD^{-1}\\
0 & I
\end{bmatrix}
\begin{bmatrix}
A-BD^{-1}C & 0 \\
0 & D
\end{bmatrix}\begin{bmatrix}
I & 0 \\
-D^{-1}C & I
\end{bmatrix}^{-1}
$$

여기에 역행렬을 취하면 다음과 같다.

$$
\begin{align}
\begin{bmatrix}
A & B \\
C & D
\end{bmatrix}^{-1}
&= \begin{bmatrix}
I & 0 \\
-D^{-1}C & I
\end{bmatrix}
\begin{bmatrix}
(A-BD^{-1}C)^{-1} & 0 \\
0 & D^{-1}
\end{bmatrix}
\begin{bmatrix}
I & -BD^{-1}\\
0 & I
\end{bmatrix} \\
&= \begin{bmatrix}
(A-BD^{-1}C)^{-1} & 0 \\
-D^{-1}C(A-BD^{-1}C)^{-1} & D^{-1}
\end{bmatrix}
\begin{bmatrix}
I & -BD^{-1}\\
0 & I
\end{bmatrix} \\
&= \begin{bmatrix}
(A-BD^{-1}C)^{-1} & -(A-BD^{-1}C)^{-1}BD^{-1} \\
-D^{-1}C(A-BD^{-1}C)^{-1} & D^{-1}C(A-BD^{-1}C)^{-1}BD^{-1}+D^{-1}
\end{bmatrix}
\end{align}
$$

위 두 정리된 결과 중 (1,1)의 값은 같아야하며 이를 식으로 나타내보자.

$$
(A-BD^{-1}C)^{-1} = A^{-1}+A^{-1}B(D-CA^{-1}B)^{-1}CA^{-1}
$$

이 식은 우리가 처음에 본 아래 식과 매우 비슷하다는 것을 알 수 있다.

$$
\begin{matrix}
(A + UCV)^{-1} = A^{-1}-A^{-1}U(C^{-1}+VA^{-1}U)^{-1}VA^{-1}\\
(A, C, C^{-1}+VA^{-1}U \text{ are invertible})
\end{matrix}
$$

$A = A, U = -B, C = D^{-1}, V = C$로 두면 두 식은 완전히 동일하다는 것을 알 수 있으며 이로써 증명되었다.

 

드디어 선형대수 기초를 전부 간단히 정리해보았다.

복습이나 하자...

 

Reference

• 위키백과 슈어 보수행렬
• 혁펜하임 유튜브 Matrix Inversion Lemma