행렬의 여러가지 분해

지금까지 Eigen Decomposition, Singular Value Decomposition(SVD) 와 같은 분해를 봤는데 이번에 여기서 배우는 분해들도 기존 행렬 $A$를 좀 더 자세히 분석하기 위해서 2개 이상의 간단한 행렬들로 분해하는 방법이다.

여기서 배우는 분해는 다음과 같다.

1. LU 분해
2. PLU 분해
3. LDU 분해
4. QR 분해
5. 춀레스키 분해 (Cholesky Decomposition)

 

LU 분해

LU Factorization이라고도 불리는 LU 분해는 단순히 행렬 $A$가 있을때 이를 $A = LU$로 분해하는 것을 의미한다.

이때 위 그림처럼 행렬 $L$은 Lower Triangular Matrix, $U$는 Upper Triangular Matrix이다.

이렇게 행렬 $A$를 하 삼각 행렬과 상 삼각 행렬의 곱으로 분해를 하게 되면 선형 방정식을 풀 때 매우 편리해진다.

 

LU 분해는 이전에 우리가 배운 가우스-조던 소거법에서 자연스럽게 도출될 수 있다.

이전 가우스-조던 소거법에서 우린 아래와 같이 행렬을 상 삼각 행렬로 바꿔주었다. (augmented 부분은 필요없어서 무시했다.)

$$
\begin{bmatrix}
1 & -1 \\
4 & 2
\end{bmatrix}
\rightarrow \begin{bmatrix}
1 & -1 \\
0 & 6
\end{bmatrix}
$$

위 과정을 행렬의 곱셈으로 생각해보자. 좌측 행렬에서 1번 row에 4배를 해서 2번 row에 뺀 것이 결과인 상 삼각 행렬이 나오게 된다. 이때 이를 해주는 행렬을 기존 행렬에 좌측해 곱해주면 아래와 같은 꼴이 나온다.

$$
\begin{bmatrix}
1 & 0 \\
-4 & 1
\end{bmatrix}
\begin{bmatrix}
1 & -1 \\
4 & 2
\end{bmatrix} = \begin{bmatrix}
1 & -1 \\
0 & 6
\end{bmatrix}
$$

이때 $\begin{bmatrix}
1 & 0 \\
-4 & 1
\end{bmatrix}$ 의 역행렬을 양 변에 곱해주면 아래와 같이 LU 분해가 완성된다.

$$
\begin{bmatrix}
1 & -1 \\
4 & 2
\end{bmatrix} = \begin{bmatrix}
1 & 0 \\
4 & 1
\end{bmatrix} \begin{bmatrix}
1 & -1 \\
0 & 6
\end{bmatrix}
$$

$3\times 3$ 행렬에 대해서도 약간만 진행해보자.

$$
\begin{bmatrix}
2 & 1 & -1 \\
-3 & -1 & 2 \\
-2 & 1 & 2
\end{bmatrix} \rightarrow
\begin{bmatrix}
2 & 1 & -1 \\
0 & \frac{1}{2} & \frac{1}{2} \\
-2 & 1 & 2
\end{bmatrix}
$$

기존 행렬에서 Upper Triangular Matrix를 만들기 위해 먼저 2행 1열 요소를 0으로 만든 결과이다.

이때 기존 행렬의 왼쪽에 아래와 같이 특정 행렬을 곱해주어야 한다.

$$
\begin{bmatrix}
1 & 0 & 0 \\
\frac{3}{2} & 1 & 0 \\
0 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
2 & 1 & -1 \\
-3 & -1 & 2 \\
-2 & 1 & 2
\end{bmatrix} =
\begin{bmatrix}
2 & 1 & -1 \\
0 & \frac{1}{2} & \frac{1}{2} \\
-2 & 1 & 2
\end{bmatrix}
$$

 

$$
\begin{bmatrix}
2 & 1 & -1 \\
-3 & -1 & 2 \\
-2 & 1 & 2
\end{bmatrix} \rightarrow
\begin{bmatrix}
2 & 1 & -1 \\
0 & \frac{1}{2} & \frac{1}{2} \\
0 & 2 & 1
\end{bmatrix}
$$

이후 3행 1열 요소를 0으로 만든 결과는 이전 결과에서 3행 1열 요소를 0으로 만들어주는 행렬을 곱해주면 된다.

$$
\begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
1 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
1 & 0 & 0 \\
\frac{3}{2} & 1 & 0 \\
0 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
2 & 1 & -1 \\
-3 & -1 & 2 \\
-2 & 1 & 2
\end{bmatrix} =
\begin{bmatrix}
2 & 1 & -1 \\
0 & \frac{1}{2} & \frac{1}{2} \\
0 & 2 & 1
\end{bmatrix}
$$

이러한 과정을 우측 행렬을 상 삼각 행렬이 될 때까지 만든 후 좌측에 곱해준 하 삼각 행렬들의 역행렬을 곱해주면 된다.

끝까지 해보면 아래와 같다.

$$
\begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & -4 & 1
\end{bmatrix}
\begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
1 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
1 & 0 & 0 \\
\frac{3}{2} & 1 & 0 \\
0 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
2 & 1 & -1 \\
-3 & -1 & 2 \\
-2 & 1 & 2
\end{bmatrix} =
\begin{bmatrix}
2 & 1 & -1 \\
0 & \frac{1}{2} & \frac{1}{2} \\
0 & 0 & -1
\end{bmatrix}
$$

이를 정리하면 다음과 같다.

$$
\begin{align}
\begin{bmatrix}
2 & 1 & -1 \\
-3 & -1 & 2 \\
-2 & 1 & 2
\end{bmatrix} &=
\begin{bmatrix}
1 & 0 & 0 \\
-\frac{3}{2} & 1 & 0 \\
0 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
-1 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 4 & 1
\end{bmatrix}
\begin{bmatrix}
2 & 1 & -1 \\
0 & \frac{1}{2} & \frac{1}{2} \\
0 & 0 & -1
\end{bmatrix} \\
&=
\begin{bmatrix}
1 & 0 & 0 \\
-\frac{3}{2} & 1 & 0 \\
-1 & 4 & 1
\end{bmatrix}
\begin{bmatrix}
2 & 1 & -1 \\
0 & \frac{1}{2} & \frac{1}{2} \\
0 & 0 & -1
\end{bmatrix}
\end{align}
$$

 

이러한 과정을 일반화 하면 아래와 같아진다.

$$
L_n\dots L_2L_1A = U \\
A = L_1^{-1}L_2^{-1}\dots L_n^{-1}U
$$

이때 좌측에 곱해주는 하 삼각 행렬을 쉽게 구하는 방법은 기존 행렬을 벡터의 벡터라 생각하면 편하다.

$$
\begin{bmatrix}
2 & 1 & -1 \\
-3 & -1 & 2 \\
-2 & 1 & 2
\end{bmatrix} = \begin{bmatrix}
a_1^T \\
a_2^T \\
a_3^T \\
\end{bmatrix}
$$

우리는 2행 1열 요소를 제거하고 싶다. 이때 우린 일반적으로 1행에 $\frac{3}{2}$를 곱해 2행에 더한다.

위와 같이 생각하면 이전에 본 곱셈을 아래와 같이 생각 가능하다.

$$
\begin{bmatrix}
1 & 0 & 0 \\
\frac{3}{2} & 1 & 0 \\
0 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
2 & 1 & -1 \\
-3 & -1 & 2 \\
-2 & 1 & 2
\end{bmatrix} =
\begin{bmatrix}
1 & 0 & 0 \\
\frac{3}{2} & 1 & 0 \\
0 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
a_1^T \\
a_2^T \\
a_3^T \\
\end{bmatrix}
=
\begin{bmatrix}
a_1^T \\
\frac{3}{2}a_1^T + a_2^T \\
a_3^T \\
\end{bmatrix}
$$

즉, $i$행에 $k$를 곱해 $j$행에 더하는 과정을 $I$ 항등 행렬에서 $(j,i)$가 $k$로 바꿔준 행렬을 곱한 것으로 생각할 수 있다.

그렇다면 $L_i$의 역행렬을 구하는 것이 마지막 문제인데, 위와 같이 $I$에서 하나의 요소만 0이 아닌 행렬의 역행렬은 해당 요소에 -1을 곱한 것이다.

$$
\begin{matrix}
\begin{bmatrix}
1 & 0 \\
-4 & 1
\end{bmatrix}
\begin{bmatrix}
1 & -1 \\
4 & 2
\end{bmatrix} = \begin{bmatrix}
1 & -1 \\
0 & 6
\end{bmatrix}\\
\begin{bmatrix}
1 & -1 \\
4 & 2
\end{bmatrix} = \begin{bmatrix}
1 & 0 \\
4 & 1
\end{bmatrix} \begin{bmatrix}
1 & -1 \\
0 & 6
\end{bmatrix}
\end{matrix}
$$

 

아까 말했듯이 LU 분해는 선형 방정식을 쉽게 풀기 위해 해준다고 했다.

$$
Ax = b \rightarrow LUx = b
$$

위 상황에서 $y = Ux$로 두면 아래와 같이 된다.

$$
Ly = b
$$

여기서 우리는 $L$에 대해 알고 있고 $b$도 알고 있다. 이때 $L$은 하 삼각 행렬이기에 매우 쉽게 $y$를 구할 수 있고, $y$를 쉽게 구한 후 $Ux = y$를 이용해 이전처럼 $U$가 상 삼각 행렬이라는 성질을 통해 쉽게 $x$를 구할 수 있다.

이때 하-상 삼각 행렬이면 쉽게 구할 수 있다는 예시를 한번만 들고 가자.

$$
\begin{bmatrix}
a_{1,1} & 0 & 0 \\
a_{2,1} & a_{2,2} & 0 \\
a_{3,1} & a_{3,2} & a_{3,3}
\end{bmatrix}
\begin{bmatrix}
x \\
y \\
z
\end{bmatrix} =
\begin{bmatrix}
e \\
f \\
g
\end{bmatrix}
$$

위 곱셈을 실제로 해보면 직관적으로 $x, y, z$를 순서대로 쉽게 풀 수 있다는 것을 알 수 있다. ($x = \frac{e}{a_{1,1}}, \dots$)

 

PLU 분해

$$
\begin{bmatrix}
0 & 3 & 2 \\
1 & 1 & 4 \\
2 & 2 & 5
\end{bmatrix}
$$

근데 위와 같이 LU 분해가 안될 수 있는 행렬을 만날 수 있다.

과거 가우스 조던 소거법에서 이런 경우 우리는 기본 연산 중 하나인 행의 순서 바꾸기를 이용해 풀었었다. 즉, 위 문제도 행 순서를 바꿔주면 LU 분해가 된다는 의미이다.

이때 행의 순서를 바꿔주는 행렬을 곱해주면 되는데 이러한 행렬을 Permutation 행렬이라 부르며, 이를 Permutation 행렬의 추가로 PLU 분해라고 부른다.

 

Permutation 행렬은 이전처럼 기존 행렬을 벡터의 벡터로 생각하면 편리하게 만들 수 있다.

1행과 2행을 교환할 때의 예시를 살펴보면 직관적으로 이해된다.

$$
P^{-1}A =
\begin{bmatrix}
0 & 1 & 0 \\
1 & 0 & 0 \\
0 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
a_1^T \\
a_2^T \\
a_3^T
\end{bmatrix} =
\begin{bmatrix}
a_2^T \\
a_1^T \\
a_3^T
\end{bmatrix}
$$

즉, 단순히 $i$번 행과 $j$번 행을 교환하고 싶다면, $(j, i) = 1, (i,j) = 1$을 하고 나머지 $k \neq i,j$인 모든 $(k,k)$ 요소가 1인 행렬과 곱해주면 된다.

결과 행렬은 다시 LU로 분해가 되므로 아래와 같이 A를 PLU로 분해 가능하다.

$$
A = PLU
$$

 

LDU 분해

LDU는 솔직히 별거 고 LU를 좀 더 이쁘게 표현한 분해 방법이다.

$$
\begin{align}
\begin{bmatrix}
2 & 1 & -1 \\
-3 & -1 & 2 \\
-2 & 1 & 2
\end{bmatrix} &=
\begin{bmatrix}
1 & 0 & 0 \\
-\frac{3}{2} & 1 & 0 \\
0 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
-1 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 4 & 1
\end{bmatrix}
\begin{bmatrix}
2 & 1 & -1 \\
0 & \frac{1}{2} & \frac{1}{2} \\
0 & 0 & -1
\end{bmatrix} \\
&=
\begin{bmatrix}
1 & 0 & 0 \\
-\frac{3}{2} & 1 & 0 \\
-1 & 4 & 1
\end{bmatrix}
\begin{bmatrix}
2 & 1 & -1 \\
0 & \frac{1}{2} & \frac{1}{2} \\
0 & 0 & -1
\end{bmatrix}
\end{align}
$$

LU 결과를 다시 가져와보면 $L = \begin{bmatrix}
1 & 0 & 0 \\
-\frac{3}{2} & 1 & 0 \\
-1 & 4 & 1
\end{bmatrix}$로 대각 요소들이 1인 반면, $U = \begin{bmatrix}
2 & 1 & -1 \\
0 & \frac{1}{2} & \frac{1}{2} \\
0 & 0 & -1
\end{bmatrix}$로 지저분하다. 이를 1로 바꿔주도록 하는 행렬을 추가한 것이 LDU 분해이다.

즉 대각 요소들을 1로 만들어주어야 하므로 각 행을 대각 요소 크기로 나눠주면 된다. 즉, 아래와 같다.

$$
\begin{align}
\begin{bmatrix}
2 & 1 & -1 \\
-3 & -1 & 2 \\
-2 & 1 & 2
\end{bmatrix}
&= \begin{bmatrix}
1 & 0 & 0 \\
-\frac{3}{2} & 1 & 0 \\
-1 & 4 & 1
\end{bmatrix}
\begin{bmatrix}
2 & 1 & -1 \\
0 & \frac{1}{2} & \frac{1}{2} \\
0 & 0 & -1
\end{bmatrix} \\
&= \begin{bmatrix}
1 & 0 & 0 \\
-\frac{3}{2} & 1 & 0 \\
-1 & 4 & 1
\end{bmatrix}
\begin{bmatrix}
2 & 0 & 0 \\
0 & \frac{1}{2} & 0 \\
0 & 0 & -1
\end{bmatrix}
\begin{bmatrix}
1 & \frac{1}{2} & -\frac{1}{2} \\
0 & 1 & 1 \\
0 & 0 & 1
\end{bmatrix}
\end{align}
$$

이것이 바로 $A = LDU$가 되는 LDU 분해다. 별거 없다.

 

QR 분해

그람-슈미츠 분해를 써먹는 시간이 드디어 왔다.

QR 분해(QR Decomposition)는 이전 분해들과 똑같이 $m \times n (m \ge n)$ 행렬 $A$를 $QR$로 분해를 하는 것이다.

이때 $Q$는 $m \times n$ Orthogonal Matrix고, $R$은 이러한 $Q$에 적절한 연산을 해주어 $A$를 만들어주는 $n \times n$ 상 삼각 행렬이다.

먼저 직교 행렬 $Q$의 column 요소들은 행렬 $A$에 그람-슈미츠 분해를 한 결과 직교 벡터들로 구성된다.

즉, $R$은 적절히 $q_i$들을 조합해 다시 $a_i$를 만들어 주면 된다.

각 $a_i$들을 어떻게 다시 만들 수 있을까?

먼저 그람-슈미츠 분해에서 우린 기본적으로 $a_1$을 기준으로 수직하게 다른 벡터들을 만들어주기 때문에 $a_1 = q_1$이 된다. 이후 나머지 벡터들은 이미 수직하게 만들어준 벡터들에 정사영한 벡터들을 빼주기 때문에 다음과 같이 표현 가능하다. $a_2 - a_2^Tq_1q_1$ 이를 normalize 한 것이 $q_2$이므로 $a_2 - a_2^Tq_1q_1 = a_2^Tq_2q_2$와 같이 표현하며 이를 정리하면 아래와 같다.

$$
a_2 = a_2^Tq_1q_1 + a_2^Tq_2q_2
$$

이를 일반화 해 $a_i$를 구하는 식은 다음과 같이 쓸 수 있을 것이다.

$$
a_i = \sum_{j = 1}^{i} a_i^Tq_jq_j
$$

그러므로 위 예시의 QR 분해는 다음과 같다.

$$
\begin{bmatrix}
a_1 & a_2 & a_3
\end{bmatrix}
=
\begin{bmatrix}
q_1 & q_2 & q_3
\end{bmatrix}
\begin{bmatrix}
a_1^Tq_1 & a_2^Tq_1 & a_3^Tq_1 \\
0 & a_2^Tq_2 & a_3^Tq_2 \\
0 & 0 & a_3^Tq_3 \\
\end{bmatrix}
$$

그럼 이 QR 분해는 어디에서 사용할까? 최소 제곱법을 QR 분해로 풀면 간단하게 풀어낼 수 있다.

 

QR 분해를 이용한 최소 제곱법

최소 제곱법은 앞서 너무 많이 나왔기 때문에 문제는 생략하고 우리는 $||b-A\hat x||^2_2$를 최소화 하는 벡터 $\hat x$를 찾는것이 목표다.

 

$A = QR$로 대체해서 식을 전개해보자.

$$
\begin{align}
||b-A\hat x||^2_2
&=||b-QR\hat x||^2_2 \\
&=||Q(Q^Tb-R\hat x)||^2_2 \\
&=||Q^Tb-R\hat x||^2_2 \\
\end{align}
$$

이때 바깥 $Q$가 사라지는 이유는 2-norm이 $||A||^2_2 = A^TA$라는 사실을 적용해보면 쉽게 알 수 있다.

$$
\begin{align}
||Q(Q^Tb-R\hat x)||^2_2 &= (Q(Q^Tb-R\hat x))^T(Q(Q^Tb-R\hat x)) \\
&= (Q^Tb-R\hat x)^TQ^TQ(Q^Tb-R\hat x) \\
&= (Q^Tb-R\hat x)(Q^Tb-R\hat x) \\
&= ||Q^Tb-R\hat x||^2_2
\end{align}
$$

암튼, $||Q^Tb-R\hat x||^2_2$를 최소화 하면 된다. 이때 $R$은 상 삼각 행렬이기에 Invertible하여 이 식을 0으로 최소화 할 수 있다.

결국 $\hat x= R^{-1}Q^Tb$가 된다. 이는 이전에 우리가 구한 $\hat x = (A^TA)^{-1}A^Tb$에 $A=QR$을 대입하면 동일하다는 것을 확인할 수 있다.

$$
\begin{align}
\hat x &= (A^TA)^{-1}A^Tb \\
&= (R^TQ^TQR)^{-1}R^TQ^Tb \\
&= (R^TR)^{-1}R^TQ^Tb \\
&= R^{-1}(R^T)^{-1}R^TQ^Tb \\
&= R^{-1}Q^Tb
\end{align}
$$

이외에도 특정 행렬 $A$를 그대로 사용하는 것 보다 $QR$로 분해해서 사용하는 것이 연산 시 수치적으로 안정성을 준다는 장점을 가진다. (이러한 수치적 안정성은 조건수와 관련이 있다. 조건수에 대한 내용은 Deeplearning Book에서 정리한 내용(Poor Condition 파트)이 있으니 필요하다면 참고.) (사실 QR 분해를 한다고 조건수가 작아지는 것은 아니지만 직교 행렬의 특성과 내적의 안정성 덕이라고 한다.)

 

춀레스키 분해 (Cholesky Decomposition)

춀레스키 분해는 먼저 조건이 필요하다. 분해되는 행렬이 Positive Semi-definite이어야만 한다.

갑자기 Positive Semi-definite이라는 굉장히 생소한 용어가 나와 당황스러우니 이 용어에 대해서 잠깐 정리하고 춀레스키 분해를 들어가보자.

Positive Semi-definite

어떤 $n \times n$ 행렬 $A$가 Positive Semi-definite라는 얘기는 다음과 같은 조건을 $A$가 만족한다는 이야기이다.

• $A$가 대칭 행렬이다.
• 임의의 벡터 $\textbf{v} \in \mathbb R^n$에 대해 $\textbf{v}^TA\textbf{v} \ge 0$을 만족한다.

아래 조건에서 $\ge$가 >가 되면 semi가 아닌 Positive definite이 된다. 이 부호에 따라 negative (semi)definite도 정의가 가능하다.

이런 Positive Semi-definite은 여러 성질들이 존재하는데 아래 세가지 특징이 모두 동일한 명제다.

1. 행렬 $A$가 Positive Semi-definite이다.
2. 행렬 $A$의 eigen value가 모두 음이 아닌 실수다. (하지만, 컴퓨터 수치적으로는 매우 작은 음수 고유값이 나오는 불안정성이 존재할 수 있음)
3. 어떤 행렬 $B$가 $BB^T = A$를 만족한다.

이러한 특징을 가지는 행렬은 대표적으로 공분산 행렬이 있으며 이러한 특징은 최적화 문제들이 Convex해져 Convex 최적화가 가능하다는 장점이 있다.

3번 특징은 간단히 살펴 볼 수 있는데 $\textbf{v}^TA\textbf{v} = \textbf{v}^TBB^T\textbf{v} =||B^T\textbf{v}||^2_2$이기에 언제나 음이 아닌 수가 되어 임의의 행렬 $B$로 만드는 $A=BB^T$인 모든 $A$는 언제나 Positive Semi-definite이라는 특징을 갖는다.

대충 이러한 것이 Positive Semi-definite이다.

 

다시 춀레스키 분해로 돌아와서 춀레스키 분해란 positive semi-definite 행렬 $A$를 하 삼각 행렬 $L$의 곱 $LL^T$로 분해하는 것이다.

$$
\begin{align}
A = \begin{bmatrix}
a_{1,1} & a_{2,1} & a_{3, 1} \\
a_{2,1} & a_{2,2} & a_{3, 2} \\
a_{3,1} & a_{3,2} & a_{3,3}
\end{bmatrix} = LL^T &= \begin{bmatrix}
L_{1,1} & 0 & 0 \\
L_{2,1} & L_{2,2} & 0 \\
L_{3,1} & L_{3,2} & L_{3,3} \\
\end{bmatrix}
\begin{bmatrix}
L_{1,1} & L_{2,1} & L_{3,1} \\
0 & L_{2,2} & L_{3,2} \\
0 & 0 & L_{3,3} \\
\end{bmatrix} \\
&= \begin{bmatrix}
L_{1,1}^2 & L_{2,1}L_{1,1} & L_{3,1}L_{1,1} \\
L_{2,1}L_{1,1} & L{2,1}^2 + L_{2,2}^2 & L_{3,1}L_{2,1}+L_{3,2}L_{2,2} \\
L_{3,1}L_{1,1} & L_{3,1}L_{2,1}+L_{3,2}L_{2,2} & L_{3,1}^2+L_{3,2}^2+L_{3,3}^2
\end{bmatrix}
\end{align}
$$

결국 위 식을 정리해서 $L$을 구하면 된다.

• $L_{1,1} = \pm\sqrt{a_{1,1}}$이다. 여기서 일반적으로 양수로 잡는다. $L_{1,1} = a_{1,1}$
• $L_{2,1} = a_{2,1}/L_{1,1}$
• $L_{3,1} = a_{3,1}/L_{1,1}$
• $L_{2,2} = \sqrt{a_{2,2} - L_{2,1}^2}$
• $L_{3,2} = (a_{3,2} - L_{3,1}L_{2,1}) / L_{2,2}$
• $L_{3,3} = \sqrt{a_{3,3}-L_{3,1}^2 - L_{3,2}^2}$

$$
\begin{matrix}
L_{i, i} = \sqrt{a_{i,i} - \sum_{k = 1}^{i - 1}L^2_{i,k}} \\
L_{i,j} = (a_{i,j} - \sum^{j - 1}{k = 1} L{i,k}L_{j,k})/L_{j,j}
\end{matrix}
$$

일반화 하면 위와 같이 정리된다. ㅋㅋ… 필요할 때마다 찾아보면 되겠다..

 

이러한 춀레스키 분해는 선형 시스템의 해, 역행렬 계산 등에도 쓰이며, 다변량 정규 분포의 샘플링에서도 사용 가능하다.

다변량 정규분포는 $n \sim N(\mu, R)$과 같이 표현되며, $\mu$는 평균, $R$은 공분산을 나타낸다.

분산은 알겠는데 공분산은 또 뭐냐? 먼저 분산은 $E[(X-\mu)^2]$와 같이 구했었다.

공분산 행렬은 $E[(X-\mu_X)(Y-\mu_Y)]$와 같이 표현하며 두 변수 간의 전반적인 경향성을 나타내는 척도로 두 변수가 함께 어떻게 움직이는 지를 나타낸다.

위 다변량 정규분포에서 공분산 행렬은 $E[(X-\mu)(X-\mu)^T]$로 $LL^T$과 같은 형태이므로 positive semi-definite이다.

 

아무튼 이렇게 정의된 다변량 정규분포에서 샘플링하는 과정은 다음과 같다.

1. 먼저 공분산 행렬 $R$을 cholesky 분해를 한다. $R = LL^T$. 이때 $L$은 하 삼각 행렬
2. 각 변수에 대해서 독립적으로 표준 정규 분포에서 샘플을 추출한다. $n \sim N(0, I)$
3. 샘플링된 $n_{new}$는 $n_{new} = Ln + \mu$와 같이 표현 가능하다.

 

 

Reference

• 유튜브 혁펜하임
• 가우스 조던 소거법과 역행렬
• 위키 백과 - QR 분해
• 선형대수 강의 노트 정리
• 최소 자승법
• 위키 백과 - 춀레스키 분해
• 행렬이 양수다? positive semidefinite