Sholesky 분해의 개요 - 소프트웨어 융합

대칭 행렬과 양의 정부호 행렬

대칭 행렬

대칭 행렬(Symmetric matrix)은 다음과 같은 성질을 만족하는 행렬이다. 행렬 $\mathbf{A}$ 가 대칭 행렬이 되기 위해서는 다음 조건을 만족해야 한다:

$\mathbf{A} = \mathbf{A}^T$

여기서 $\mathbf{A}^T$ 는 행렬 $\mathbf{A}$ 의 전치 행렬을 나타낸다. 즉, 모든 $i$ 와 $j$ 에 대해, $a_{ij} = a_{ji}$ 를 만족한다. 다음은 대칭 행렬의 예이다:

$\mathbf{A} = \begin{pmatrix} 2 & 1 & 3 \\ 1 & 4 & 5 \\ 3 & 5 & 6 \end{pmatrix}$

대칭 행렬의 성질:

특성값 특성: 대칭 행렬의 모든 특성값은 실수이다.
대각화 가능성: 대칭 행렬은 항상 직교 행렬에 의해 대각화 가능하다.
기타 성질:
대칭 행렬의 모든 대각 원소는 항상 실수이다.
대칭 행렬의 곱(두 대칭 행렬의 곱)은 일반적으로 대칭이 아니다. 단, 두 행렬이 교환법칙을 따를 경우 곱셈 결과는 대칭 행렬이 된다.

양의 정부호 행렬

양의 정부호 행렬(Positive definite matrix)은 다음과 같은 성질을 만족하는 대칭 행렬이다. 행렬 $\mathbf{A}$ 가 양의 정부호 행렬이 되기 위해서는 다음 조건을 만족해야 한다:

$\mathbf{x}^T \mathbf{A} \mathbf{x} > 0 \quad \forall \mathbf{x} \neq \mathbf{0}$

여기서 $\mathbf{x}$ 는 0벡터가 아닌 모든 벡터를 나타낸다. 양의 정부호 행렬의 예를 살펴보자:

$\mathbf{A} = \begin{pmatrix} 2 & -1 \\ -1 & 2 \end{pmatrix}$

이를 살펴보면, 벡터 $\mathbf{x} = \begin{pmatrix} x_1 \\ x_2 \end{pmatrix}$ 에 대해:

$\mathbf{x}^T \mathbf{A} \mathbf{x} = \begin{pmatrix} x_1 & x_2 \end{pmatrix} \begin{pmatrix} 2 & -1 \\ -1 & 2 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = 2x_1^2 - 2x_1x_2 + 2x_2^2 = 2(x_1^2 - x_1x_2 + x_2^2) > 0$

양의 정부호 행렬의 성질:

특성값 특성: 양의 정부호 행렬의 모든 특성값은 양수이다.
대칭성: 양의 정부호 행렬은 항상 대칭 행렬이다.
역행렬: 양의 정부호 행렬의 역행렬도 양의 정부호 행렬이다.

이와 같이 대칭 행렬과 양의 정부호 행렬은 Sholesky 분해의 중요한 전제 조건을 이룬다.

Sholesky 분해의 개념

정의와 기초 원리

Sholesky 분해(Cholesky decomposition) 또는 Sholesky 인수분해(Cholesky factorization)는 대칭 양의 정부호 행렬을 두 개의 하삼각행렬 또는 한 하삼각행렬과 그 전치 행렬로 분해하는 기법이다. 구체적으로, 행렬 $\mathbf{A}$ 가 대칭 양의 정부호 행렬일 때, 이를 다음과 같이 분해할 수 있다:

$\mathbf{A} = \mathbf{L} \mathbf{L}^T$

여기서 $\mathbf{L}$ 은 하삼각행렬(Lower triangular matrix)이다. 분해 결과 $\mathbf{L}$ 의 주 대각 원소들은 모두 양수이다.

다시 말해, $\mathbf{A}$ 가 $n \times n$ 행렬일 때, $\mathbf{L}$ 도 $n \times n$ 행렬이며, 이러한 분해는 단일 해를 가지게 된다.

Sholesky 분해의 목적

Sholesky 분해는 특히 선형 방정식 시스템을 해결하거나 행렬의 역행렬을 계산하는 데 유용하다. 주로 다음과 같은 응용에서 많이 사용된다:

선형 시스템의 해 구하기: 벡터 $\mathbf{b}$ 에 대해 $\mathbf{A}\mathbf{x} = \mathbf{b}$ 의 해를 찾는 작업.
역행렬 계산: $\mathbf{A}^{-1}$ 구하기.
최소자승문제(Least Squares Problems): 특히 과적합 방지와 정규화의 경우 사용.
확률 및 통계: 공분산 행렬의 분해.

알고리즘과 구현

알고리즘 단계

Sholesky 분해는 다음 단계를 통해 수행된다:

초기 설정: 행렬 $\mathbf{L}$ 을 $0$ 으로 초기화한다.
하삼각행렬 원소 계산:
주 대각 원소 계산: $l_{ii} = \sqrt{ a_{ii} - \sum_{k=1}^{i-1} l_{ik}^2 }$
비대각 원소 계산: $l_{ij} = \frac{1}{l_{jj}} \left( a_{ij} - \sum_{k=1}^{j-1} l_{ik} l_{jk} \right) \quad (i > j)$

이해를 돕기 위해, 다음은 간단한 $3 \times 3$ 행렬의 Sholesky 분해를 예시로 들겠다.

예시: $3 \times 3$ 행렬

주어진 행렬 $\mathbf{A}$ :

$\mathbf{A} = \begin{pmatrix} 4 & 12 & -16 \\ 12 & 37 & -43 \\ -16 & -43 & 98 \end{pmatrix}$

이 행렬을 Sholesky 분해하면:

초기 설정: $\mathbf{L} = \begin{pmatrix} l_{11} & 0 & 0 \\ l_{21} & l_{22} & 0 \\ l_{31} & l_{32} & l_{33} \end{pmatrix}$
$l_{11} = \sqrt{4} = 2$
$l_{21} = \frac{12}{2} = 6$
$l_{31} = \frac{-16}{2} = -8$
$l_{22} = \sqrt{37 - 6^2} = 1$
$l_{32} = \frac{-43 - 6 \cdot -8}{1} = 5$
$l_{33} = \sqrt{98 - (-8)^2 - 5^2} = 3$

따라서:

$\mathbf{L} = \begin{pmatrix} 2 & 0 & 0 \\ 6 & 1 & 0 \\ -8 & 5 & 3 \end{pmatrix}$

$\mathbf{A} = \mathbf{L} \mathbf{L}^T$ 임을 확인할 수 있다.

Sholesky 분해의 계산 복잡도

Sholesky 분해의 주요 장점 중 하나는 계산의 효율성이다. 분해 과정은 $O(n^3)$ 복잡도를 가지며, 이는 일반적인 행렬 곱셈의 계산 복잡도와 같은 수준이다. 이는 특히 대규모 데이터에서 중요한 성능 이점을 제공한다.

구현 예시

간단한 파이썬 코드를 통해 Sholesky 분해를 직접 구현해볼 수 있다.

import numpy as np

def cholesky_decomposition(A):
    n = A.shape[0]
    L = np.zeros_like(A)

    for i in range(n):
        for j in range(i + 1):
            if i == j:
                L[i, j] = np.sqrt(A[i, i] - np.sum(L[i, :j] ** 2))
            else:
                L[i, j] = (A[i, j] - np.sum(L[i, :j] * L[j, :j])) / L[j, j]

    return L

A = np.array([[4, 12, -16],
              [12, 37, -43],
              [-16, -43, 98]])

L = cholesky_decomposition(A)
print("L:\n", L)
print("L^T:\n", L.T)

이 코드는 주어진 대칭 양의 정부호 행렬 $\mathbf{A}$ 의 Sholesky 분해를 수행하여 하삼각행렬 $\mathbf{L}$ 을 출력하는 예시이다.

Sholesky 분해는 대칭 양의 정부호 행렬을 하삼각행렬과 그 전치 행렬로 분해하는 효율적이고 강력한 기법이다. 이 알고리즘은 선형 시스템 해법, 역행렬 계산, 확률 및 통계 응용 등 다양한 분야에서 유용하게 사용된다.