[선형대수] 4. LU 분해 (LU Decomposition / Factorization)

이번 포스팅에서는 행렬의 $A=LU$ 분해 (LU decomposition or factorization)에 대해 살펴보자.

 

이러한 행렬의 분해들은 컴퓨터에서의 계산이 편리하고 주어진 행렬이 무엇인지 분석하기 쉽게 만들어 준다.

 

1. 곱셈의 역 (Inverse)

LU 분해의 이해를 돕기 위해 지난시간에 다루었던 행렬 곱셈의 inverse에 대해 짧게 살펴보자.

Invertible하고 son-singular인 두 행렬 $A$와 $B$가 있을때, 행렬 곱 $AB$의 뒤에 그것들의 역행렬들을 어떤 순서로 곱해야 단위 행렬이 나올까?

(즉, $AB??=I$)

 

이를 위해서는 아래와 같이 "Reverse order"로 곱해줘야 한다.

$$\begin{equation} A\underbrace{BB^{-1}}_{I}A^{-1} = AA^{-1} = I \end{equation} \tag{1}$$

 

행렬의 전치 (Transpose)

행렬의 전치는 row축과 column축을 뒤바꾸는 것을 말하며 다음과 같이 대각선을 중심으로 뒤집힌 모양을 말한다.

$$ \underbrace{\begin{bmatrix} a_{11} & a_{12}\\ a_{21} & a_{22} \end{bmatrix}}_{A} \xrightarrow{\text{transpose}} \underbrace{\begin{bmatrix} a_{11} & a_{21}\\ a_{12} & a_{22} \end{bmatrix}^T}_{A^T} \tag{2}$$

 

이를 행렬 곱셈에 적용하면 아래와 같이 된다.

$$\begin{equation} AA^{-1}=I \xrightarrow{\text{transpose}} (AA^{-1})^T = I^T \xrightarrow{\text{reverse order}} \underbrace{(A^{-1})^T}_{(A^T)^{-1}}(A)^T=I \end{equation} \tag{3}$$

여기서 전치가 row축과 column축을 뒤바꾸는 것이기 때문에 행렬 곱셈의 순서가 바뀐다.

또한 $A$의 역행렬의 전치 부분은 $A$의 전치행렬의 역행렬이 된다. (항등행렬이 나오려면)

 

2. LU 분해

$A=LU$ 분해는 행렬의 분해방법 중 가장 간단한 형태로 어떤 행렬 $A$가 있을 때, 이를 하삼각 행렬(Lower triangular matrix)와 상삼각 행렬(Upper triangular matrix)의 곱으로 분해하여 나타내는 것을 말한다.

(우선 분해과정에서 행교환이 필요하지 않은 행렬만 고려한다)

2.1. 2x2 case

어떤 non-singular 행렬 $A$가 있을때, 지난 포스팅 [2. 행렬의 소거법 참고]에서 배웠던 소거 행렬을 사용하여 상삼각 행렬을 다음과 같이 만들 수 있다.

$$\underbrace{\begin{bmatrix} 1 & 0 \\ -4 & 1 \end{bmatrix}}_{E_{21}} \underbrace{\begin{bmatrix} 2 & 1 \\ 8 & 7 \end{bmatrix}}_{A} = \underbrace{\begin{bmatrix} 2 & 1 \\ 0 & 3 \end{bmatrix}}_{U} \tag{4}$$

 

$A=LU$와 같은 형태를 얻기 위해서는 다음과 같이 양변에 $E_{21}$의 역행렬을 곱해주면 된다.

$$(E_{21})^{-1} E_{21} A  = (E_{21})^{-1}U \tag{5}$$

여기서 $(E_{21})^{-1}$는 $E_{21}$과 곱했을때 항등행렬이 나오게끔 만들면 되므로 -4만 4로 바꿔주면 되며 (하삼각 행렬이 만들어짐), 결국 $A$는 다음과 같이 $LU$의 형태로 분해될 수 있다.

$$\underbrace{\begin{bmatrix} 2 & 1 \\ 8 & 7 \end{bmatrix}}_{A} =\underbrace{\begin{bmatrix} 1 & 0 \\ 4 & 1 \end{bmatrix}}_{L} \underbrace{\begin{bmatrix} 2 & 1 \\ 0 & 3 \end{bmatrix}}_{U} \tag{6}$$

 

2.2. 3x3 case

이번에는 왜 $EA=U$의 형태에서 굳이 역행렬을 구하여 $A=LU$의 형태로 만드는 것일까에 대해 생각해보자

이를 위해 다음과 같은 3x3 행렬 $A$를 고려해보자.

$$ A= \begin{bmatrix} 2 & 1 & 7 \\ 4 & -1 & 16 \\ 0 & -15 & 19 \end{bmatrix} \tag{7}$$

이러한 3x3 행렬을 상삼각 행렬로 만들기 위해서는 $a_{21}, a_{31}, a_{32}$를 순차적으로 제거해야 하므로 $E_{32}E_{31}E_{21}A=U$와 같은 형태가 만들어지며 $E$만 따로 계산해서 나타내면 다음과 같다.

$$ \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -5 & 1 \end{bmatrix}}_{E_{32}} \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}}_{E_{31}=I} \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}}_{E_{21}} = \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ \color{red}{10} & -5 & 1 \end{bmatrix}}_{E} \text{ in } \color{blue}{E}A=U   \tag{8}$$

여기서 $L$을 구하려면 $E$행렬들의 역행렬을 reverse order에서 곱해주면 된다.

$$ \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}}_{(E_{21})^{-1}} \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}}_{(E_{31})^{-1}=I} \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 5 & 1 \end{bmatrix}}_{(E_{32})^{-1}} = \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ \color{red}{2} & 1 & 0 \\ 0 & \color{red}{5} & 1 \end{bmatrix}}_{L} \text{ in } A=\color{blue}{L}U   \tag{9}$$

여기서 $\pm 2$와 $\pm 5$는 소거 과정에서 pivot row에 곱해지는 multiplier이다. 

 

Eq. (8-9)을 보면 $E$에 10이라는 숫자가 생겼고, $L$에는 multiplier들만 그대로 들어간다.

이러한 추가적인 숫자는 골칫거리가 되는경우가 많다.

예를 들어, 아주 큰 행렬 $A$에 대해 $U$를 만들어낼 수 있는 $E$를 딥러닝에서 사용되는 gradient descent를 통해 최적화문제로 푼다고 해보면, 위의 10과 같이 뭔가 학습해야할 파라미터 수가 증가하고 (search space 증가) 문제를 더 어렵게 만들 수 있다.

따라서 $A=LU$의 형태가 더 좋은 표현이다.

 

2.3. 치환 행렬 (Permutation matrix)

지금까지 행 교환을 요구하지 않는 행렬 $A$에 대하여 살펴보았다.

Eq. (9)와 같이 빨간색으로 표시된 multipliers가 $L$에 그대로 들어가는 특성을 유지하기 위해 행교환은 치환행렬 $P$를 사용하여 따로 처리해보자

$P_{23}$를 2번째 row와 3번째 row를 바꿔주는 행렬이라고 하자.

$n$개의 rows가 있을때, 행교환의 가능한 조합의 수는 $n!$가 된다.

$n=3$일 때 다음과 같이 $n!=6$개의 치환행렬이 존재한다.

$$ \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}}_{I} \underbrace{\begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}}_{P_{12}} \underbrace{\begin{bmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{bmatrix}}_{P_{13}} \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix}}_{P_{23}} \underbrace{\begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix}}_{P_{13}P_{23}} \underbrace{\begin{bmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix}}_{P_{12}P_{23}}  \tag{10}$$

 

이를 통해 행교환이 필요할 경우 $P$를 사용하여 아래와 같이 LU 분해를 표현할 수 있다.

$$ PA=LU \tag{11}$$

 

이러한 $P$의 전치 행렬은 행교환했던것을 다시 원래대로 되돌려놓게 된다. (헷갈리면 계산해보면 알 수 있다)

즉 $P^T$는 $P$의 역행렬이다.

$$ P^T=P^{-1} \tag{12}$$

 

Reference

1. MIT Lecture by Gilbert Strang [Link]