📂행렬대수

양의 정부호 행렬의 콜레스키 분해

개요

가역행렬에서 대각행렬로 조건이 강화되면서 LDU 분해를 할 수 있었듯 양의 정부호 행렬로 조건이 강화되면 더욱 효율적인 행렬 분해인 콜레스키 분해^{cholesky decomposition}를 할 수 있다.

빌드업

$m \times m$ 양의 정부호 행렬 $A : = \begin{bmatrix} a_{11} & \mathbf{w}^{T} \\ \mathbf{w} & K \end{bmatrix} > 0$ 을 생각해보면 $a_{11}$ 은 양수, $\mathbf{w} \in \mathbb{R}^{m-1}$ 이고 $K \in \mathbb{R}^{(m-1) \times (m-1)}$ 이다. 만약 $a_{11} \le 0$ 이면 $\mathbf{e}_{1} = (1, 0, \cdots , 0)$ 에 대해 $\mathbf{e}_{1}^{T} A \mathbf{e}_{1} = a_{11} \le 0$ 이므로 $A$ 는 양의 정부호가 될 수 없다. 한편 임의의 벡터 $\mathbb{0 } \ne \mathbf{x} \in \mathbb{R}^{m-1}$ 에 대해서

$$ \mathbf{x}^{T} K \mathbf{x} = \begin{bmatrix} 0 & \mathbf{x}^{T} \end{bmatrix} \begin{bmatrix} a_{11} & \mathbf{w}^{T} \\ \mathbf{w} & K \end{bmatrix} \begin{bmatrix} 0 \\ \mathbf{x} \end{bmatrix} > 0 $$

이므로 $K > 0$ 다. 편의상 $a_{11} = 1$ 이라 두면

$$ A_{0} : = \begin{bmatrix} 1 & \mathbf{w}^{T} \\ \mathbf{w} & K \end{bmatrix} = \begin{bmatrix} 1 & \mathbb{0} \\ \mathbf{w} & I \end{bmatrix} \begin{bmatrix} 1 & \mathbb{0} \\ \mathbb{0} & K - \mathbf{w} \mathbf{w}^{T} \end{bmatrix} \begin{bmatrix} 1 & \mathbf{w}^{T} \\ \mathbb{0} & I \end{bmatrix} $$

으로 나타낼 수 있다. 여기서 $L_{1} := \begin{bmatrix} 1 & \mathbf{w}^{T} \\ \mathbf{w} & K \end{bmatrix}$ 은 상삼각행렬, $A_{1} := \begin{bmatrix} 1 & \mathbb{0} \\ \mathbb{0} & K - \mathbf{w} \mathbf{w}^{T} \end{bmatrix}$ 은 양의 정부호이므로 $K - \mathbf{w} \mathbf{w}^T > 0$ 다. 따라서 이러한 프로세스 $A_{n-1} = L_{n} A_{n} L_{n}^{T}$ 를 $n=m$ 까지 반복하면

$$ A_{0} = L_{1} \cdots L_{m} I_{m} L_{m}^{T} \cdots L_{1}^{T} $$

와 같이 나타낼 수 있다.

일반화

이제 $a_{11}>0$ 인 경우에 대해서 일반화해보자. $A := A_{0}$ 라 하면

$$ \begin{align*} A_{0} &= \begin{bmatrix} a_{11} & \mathbf{w}^{T} \\ \mathbf{w} & K \end{bmatrix} \\ =& \begin{bmatrix} \sqrt{a_{11}} & \mathbb{0} \\ \mathbb{0} & I \end{bmatrix} \begin{bmatrix} 1 & {{1} \over {\sqrt{a_{11}}}} \mathbf{w}^{T} \\ {{1} \over {\sqrt{a_{11}}}} \mathbf{w} & K \end{bmatrix} \begin{bmatrix} \sqrt{a_{11}} & \mathbb{0} \\ \mathbb{0} & I \end{bmatrix} \end{align*} $$

$\begin{bmatrix} 1 & {{1} \over {\sqrt{a_{11}}}} \mathbf{w}^{T} \\ {{1} \over {\sqrt{a_{11}}}} \mathbf{w} & K \end{bmatrix}$은 $a_{11}=1$ 인 경우에서 다룬 꼴이므로

$$ \begin{bmatrix} 1 & {{1} \over {\sqrt{a_{11}}}} \mathbf{w}^{T} \\ {{1} \over {\sqrt{a_{11}}}} \mathbf{w} & K \end{bmatrix} = \begin{bmatrix} 1 & \mathbb{0} \\ {{1} \over {\sqrt{a_{11}}}} \mathbf{w} & I \end{bmatrix} \begin{bmatrix} 1 & \mathbb{0} \\ \mathbb{0} & K-{{ \mathbf{w} \mathbf{w}^{T} } \over {a_{11}}} \end{bmatrix} \begin{bmatrix} 1 & {{1} \over {\sqrt{a_{11}}}} \mathbf{w}^{T} \\ \mathbb{0} & I \end{bmatrix} $$

$$ L_{1} := \begin{bmatrix} \sqrt{a_{11}} & \mathbb{0} \\ \mathbb{0} & I \end{bmatrix} \begin{bmatrix} 1 & \mathbb{0} \\ {{1} \over {\sqrt{a_{11}}}} \mathbf{w} & I \end{bmatrix} $$

그리고

$$ A_{1} := \begin{bmatrix} 1 & \mathbb{0} \\ \mathbb{0} & K-{{ \mathbf{w} \mathbf{w}^{T} } \over {a_{11}}} \end{bmatrix} $$

으로 두면

$$ \begin{align*} A_{0} =& \begin{bmatrix} \sqrt{a_{11}} & \mathbb{0} \\ \mathbb{0} & I \end{bmatrix} \begin{bmatrix} 1 & \mathbb{0} \\ {{1} \over {\sqrt{a_{11}}}} \mathbf{w} & I \end{bmatrix} \begin{bmatrix} 1 & \mathbb{0} \\ \mathbb{0} & K-{{ \mathbf{w} \mathbf{w}^{T} } \over {a_{11}}} \end{bmatrix} \begin{bmatrix} 1 & {{1} \over {\sqrt{a_{11}}}} \mathbf{w} \\ \mathbb{0} & I \end{bmatrix} \begin{bmatrix} \sqrt{a_{11}} & \mathbb{0} \\ \mathbb{0} & I \end{bmatrix} \\ =& L_{1} A_{1} L_{1}^{T} \end{align*} $$

마찬가지로 프로세스 $A_{n-1} = L_{n} A_{n} L_{n}^{T}$ 를 $n=m$ 까지 반복하면

$$ A_{0} = L_{1} \cdots L_{m} I_{m} L_{m}^{T} \cdots L_{1}^{T} $$

를 얻는다. $L_{1} , L_{2} , \cdots L_{m}$ 은 하삼각행렬이므로 이들의 곱 $L : = L_{m} L_{m-1} \cdots L_{1}$ 역시 하삼각행렬이고, $A_{0} = A = L L^{T}$ 로 표현된다.

이렇듯 하삼각행렬 $L$ 만으로 $A = L L^{T}$ 를 표현하는 것을 콜레스키 분해라고 한다. 양의 정부호라는 조건이 상당히 강력하지만 그 분해는 놀랍도록 단순하면서 굉장히 적은 계산으로 구해낼 수 있게 된다. 이제 구체적으로

$$ L : = \begin{bmatrix} l_{11} & 0 & 0 & \cdots & 0 \\ l_{21} & l_{22} & 0 & \cdots & 0 \\ l_{31} & l_{32} & l_{33} & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ l_{n1} & l_{n2} & l_{n3} & \cdots & l_{nn} \end{bmatrix} $$

을 찾기 위해 $A = (a_{ij}) = LL^{T}$ 를 직접 계산해보자. 대각성분 뒤로는 계산할 필요가 없으므로

$$ a_{ij} = \sum_{s=1}^{n} l_{is} l_{sj}^{T} = \sum_{s=1}^{\min (i,j)} l_{is} l_{js} $$

$i=j=k$ 면 $$ a_{kk} = \sum_{s=1}^{k-1} l_{ks}^{2} + l_{kk}^2 \\ l_{kk} = \sqrt{ a_{kk} - \sum_{s=1}^{k-1} l_{ks}^{2} } $$

$j=k$ 면 $i = k+1, \cdots , n$ 에 대해 $$ a_{ik} = \sum_{s=1}^{k-1} l_{is} l_{ks} + l_{ik} l_{kk} \\ l_{ik} = {{1} \over {l_{kk}}} \left( a_{ik} - \sum_{s=1}^{k-1} l_{is} l_{ks} \right) $$

알고리즘

$(a_{ij}) \in \mathbb{R}^{n \times n}$ 가 양의 정부호 행렬이라고 하자.

Step 1. $k = 1$

$d_{11} = \sqrt{a_{11}}$ 을 대입하고 $\displaystyle l_{i1} = {{1} \over {d_{11}}} a_{i1}$ 을 계산한다.

---

Step 2. $k = 2, 3, \cdots , n-1$ 에 대해 다음을 계산한다.

• Step 2-1. $$ l_{kk} = \sqrt{ a_{kk} - \sum_{s=1}^{k-1} l_{ks}^{2} } $$

• Step 2-2. $i = k+1 , k+2 , \cdots , n-1$ 에 대해 다음을 계산한다. $$ l_{ik} = {{1} \over {l_{kk}}} \left( a_{ik} - \sum_{s=1}^{k-1} l_{is} l_{ks} \right) $$

---

Step 3. $k = n$ 에 대해 다음을 계산한다. $$ l_{nn} = \sqrt{ a_{nn} - \sum_{s=1}^{n-1} l_{ns}^{2} } $$

---

• LU 분해나 LDU 분해에 비해 계산량이 눈에 띄게 줄어들었음을 확인할 수 있다. 그나마 하는 계산도 복잡하지 않고 내적과 놈을 구하는 것과 흡사해졌다는 것에 주목하자.

코드

이제 콜레스키 분해를 실제로 해보자.

아래의 코드는 위의 알고리즘을 실제로 R 에서 구현한 것이다.

B <- matrix(c(2,1,0,1,2,1,0,1,2), ncol= 3); B
Cholesky<-function(A){ 
    n=length(A[,1])
    L<-diag(0,n)
    k=1
    L[1,1] = sqrt(A[1,1])
    L[,1] = A[,1]/L[1,1]
    for(k in 2:(n-1))  {
        L[k,k] = sqrt(A[k,k] - sum(L[k,1:(k-1)])^2 )
        for(i in (k+1):n)    {
            L[i,k] = ( A[i,k] - sum( L[i,1:(k-1)] * L[k,1:(k-1)] ) )/L[k,k]
        }
    }
    L[n,n] = sqrt( A[n,n] - sum(L[n,1:(n-1)]^2) )
    return(list(L=L))
}

Cholesky(B)
t(chol(B))

실행결과는 다음과 같다.

R 에 내장된 콜레스키 분해의 결과와 비교해보면 정확하게 일치함을 확인할 수 있다.