Cholesky Decomposition

머신러닝에서는 행렬을 특별한 타입으로 분해하는 여러 방법들을 사용합니다. Positive read number에서는 숫자를 동일한 구성요소로 분해하는 제곱근과 같은 연산(e.g., $9 = 3\cdot3$)이 있습니다. 행렬의 경우에서는 양수에 대해 제곱근과 같은 연산을 할 때 주의해야 합니다. 대칭이면서 positive definite(양의 정부호)인 행렬(3.2.3장 참조)의 경우, 여러 square-root equivalent operations 중 선택할 수 있습니다. 그중 Cholesky decomposition/Cholesky factorization은 symmetric, positive definite matrix에 대해 square-root equivalent operation을 제공하며, 실제로 유용합니다.

Thorem 4.18 (Cholesky Decomposition)

Symmetric, positive definite matrix $\boldsymbol{A}$ 는 $\boldsymbol{A} = \boldsymbol{LL}^\top$ 으로 인수분해할 수 있으며, 이때 $\boldsymbol{L}$ 은 positive diagonal delements를 갖는 lower-triangular matrix 입니다.

\[\begin{bmatrix}a_{11} & \cdots & a_{1n} \\ \vdots & \ddots & \vdots \\ a_{n1}&\cdots&a_{nn}\end{bmatrix} = \begin{bmatrix}l_{11}&\cdots&0\\\vdots&\ddots&\vdots\\l_{n1}&\cdots&l_{nn}\end{bmatrix}\begin{bmatrix}l_{11}&\cdots&l_{1n}\\\vdots&\ddots&\vdots\\0&\cdots&l_{nn}\end{bmatrix} \tag{4.44}\]

$\boldsymbol{L}$ 을 $\boldsymbol{A}$ 의 Cholesky factor 라고 하며, $\boldsymbol{L}$ 은 유일합니다.

Example 4.10& (Cholesky Factorization)
Symmetric, positive definite matrix $\boldsymbol{A}\in\mathbb{R}^{3\times3}$ 일 때, 이 행렬의 Cholesky factorization $\boldsymbol{A} = \boldsymbol{LL}^\top$ 을 찾아보도록 하겠습니다. Cholesky Factorization을 표현하면 다음과 같습니다.

\[\boldsymbol{A} = \begin{bmatrix}a_{11}&a_{21}&a_{31}\\a_{21}&a_{22}&a_{32}\\a_{31}&a_{32}&a_{33}\end{bmatrix} = \boldsymbol{LL}^\top = \begin{bmatrix}l_{11}&0&0\\l_{21}&l_{22}&0\\l_{31}&l_{32}&l_{33}\end{bmatrix}\begin{bmatrix}l_{11}&l_{21}&l_{31}\\0&l_{22}&l_{32}\\0&0&l_{33}\end{bmatrix} \tag{4.45}\]

위 식의 우항을 풀면, 다음과 같습니다.

\[\boldsymbol{A} = \begin{bmatrix}l_{11}^2 & l_{21}l_{11} & l_{31}l_{11} \\ l_{21}l_{11}&l_{21}^2+l_{22}^2&l_{31}l_{21} + l_{32}l_{22}\\l_{31}l_{11}&l_{31}l_{21}+l_{32}l_{22}&l_{31}^2+l_{32}^2+l_{33}^2\end{bmatrix} \tag{4.46}\]

이를 식 (4.45)의 좌항과 비교하면, diagonal elements $l_{ii}$ 에서 다음의 간단한 패턴이 있다는 것을 볼 수 있습니다.

\[l_{11} = \sqrt{a_{11}}, \quad l_{22} = \sqrt{a_{22}-l_{21}^2}, \quad l_{33} = \sqrt{a_{33} - (l_{31}^2 + l_{32}^2)} \tag{4.47}\]

대각 요소 아래에 있는 요소들도 유사하게 다음과 같이 반복되는 패턴을 갖습니다.

\[l_{21}=\frac{1}{l_{11}}a_{21}, \quad l_{31} = \frac{1}{l_{11}}a_{31}, \quad l_{32} = \frac{1}{l_{22}}(a_{32} - l_{31}l_{21}) \tag{4.48}\]

이렇게 positive definit $3\times3$ 행렬에 대해 Cholesky decomposition을 구성할 수 있습니다. Cholesky decomposition의 핵심은 $a_{ij}$ 의 값과 이전에 계산된 $l_{ij}$ 값을 알고 있다면 $l_{ij}$ 를 역으로 계산할 수 있다는 것입니다.

Cholesky Decomposition은 머신러닝의 기반이 되는 수치적 계산을 위한 중요한 tool 입니다. Symmetric positive definite matrix를 다루는 경우가 종종 있는데, 예를 들어, multivariate Gaussian variable(다변량 가우시안 변수, 6.5장 참조)의 covariance matrix(공분산 행렬)는 symmetric, positive definite 합니다. 이 공분산 행렬의 Cholesky factorization은 가우시안 분포로부터 샘플을 생성하도록 합니다. 또한, VAE(variational auto-encoder)와 같은 deep stochastic model에서 기울기를 계산할 때 많이 사용되는 확률 변수의 linear transformation을 수행할 수 있도록 합니다.

Cholesky decomposition을 통해 determinants를 매우 효율적으로 계산할 수도 있습니다. Cholesky Decomposition $\boldsymbol{A} = \boldsymbol{LL}^\top$ 가 주어지면, $\det(\boldsymbol{A}) = \det(\boldsymbol{L})\det(\boldsymbol{L}^\top) = \det(\boldsymbol{L})$ 이라는 것을 알 수 있습니다. $\boldsymbol{L}$ 이 triangular matrix이기 때문에, determinant는 대각 요소들의 곱으로 간단히 구할 수 있습니다 ($\det(\boldsymbol{A}) = \prod_i l_{ii}^2$). 그러므로, 많은 수치 계산 SW 라이브러리들은 Cholesky Decomposition을 사용하여 연산을 효율적으로 수행합니다.