Matrix Decomposition, 행렬 분해란 무엇인가?

Image generated from DALL E

 

AI, ML, DL의 많은 데이터가 행렬 형태로 표현되므로 AI 연구자, 엔지니어라면 그와 관련된 개념을 꼭 이해해야 한다,

 

그 중 가장 중요한 개념들인

Determinants (행렬식), Trace (대각합), Eigenvalues (고유값), Eigenvector (고유벡터)

그리고 그를 이용한 Cholesky Decomposition, Diagonalization, Single Value Decomposition 을 알아보자.

 

---

 

1. Determinant (행렬식) 란 무엇인가?

행렬 A가 2*2인 정방행렬 (행의 개수 = 열의 개수인 행렬) 일 때, 행렬 A와 그 역행렬은 다음과 같다.

(역행렬의 계산은 컴퓨터에 맡기고 넘어가자.)

 

$$ A =
 \begin{pmatrix}
a_{11} & a_{12} \\
a_{21} & a_{22} \\
\end{pmatrix} $$  

$$ A^{-1} = 
 \frac{1}{a_{11}a_{22}-a_{12}a_{21}} 
\begin{pmatrix}
a_{22} & -a_{12} \\
-a_{21} & a_{11} \\
\end{pmatrix} $$

 

이 때, 행렬 A의 행렬식 인 det(A)는 다음과 같다.

 

$$ det(A) = {a_{11}a_{22}-a_{12}a_{21}} $$

 

그리고 어떤 행렬의 $ det(A) =  0 $ 일 때 그 행렬은 역행렬을 갖지 않고, $ det(A) \neq 0 $ 이면 그 행렬은 역행렬을 갖는다.

 

즉 determinant는 어떤 행렬의 역행렬의 존재 여부를 판별하는 역할을 갖는다.

따라서 determinant의 값이 행렬의 특성을 "결정"한다.

(그 외 3*3, 4*4 행렬에 대해서도 Gaussian elimination 등의 도구를 이용해 행렬식에 대한 공식을 구할 수 있다.)

 

이런 식으로 역행렬이라는 개념을 정의하기 위해 행렬식이라는 개념을 정의한다.

 

그러던 중 한 가지 패턴이 발견된다.

 

3*3 행렬의 행렬식은 아래와 같이 표현할 수 있는데,

 

$$ a_{11}a_{22}a_{33} + a_{21}a_{32}a_{13} + a_{31}a_{12}a_{23} - a_{31}a_{22}a_{13} - a_{11}a_{32}a_{23} - a_{21}a_{12}a_{33} $$

 

이것이 2*2 행렬의 행렬식을 이용한 recursive formula (점화식)로 정의될 수 있다는 사실이다.

즉 아래와 같은 동치가 성립하게 된다.

 

$$ a_{11}a_{22}a_{33} + a_{21}a_{32}a_{13} + a_{31}a_{12}a_{23} - a_{31}a_{22}a_{13} - a_{11}a_{32}a_{23} - a_{21}a_{12}a_{33} \\ \\ = \\ \\ a_{11}(-1)^{1+1}det(A_{1, 1}) + a_{12}(-1)^{1+2}det(A_{1, 2}) + a_{13}(-1)^{1+3}det(A_{1, 3}) $$

 

( $(A_{k, j})$ 는 행렬 A의 row k, column j를 제외한 submatrix 이다.)

 

이 발견으로 인해 3*3 행렬의 행렬식을 2*2 행렬의 행렬식으로 다시 정의할 수 있다.

 

이 전개를 Laplace expansion 이라 한다. 그리고 이런 형태를 일반화하여 수학자들이 행렬식을 정의하게 된다.

(정의는 생략.)

 

---

 

2. Determinant (행렬식) 의 중요한 성질들

$$ (1) \, det(AB) = det(A)det(B) $$ 

가장 중요한 성질 중 하나, 행렬식 연산과 행렬의 연산은 분리될 수 있다.

 

$$ (2) \, det(A) = det(A^T) $$

 

$$ (3) \, For \, a \, regular \, A, det(A^{-1}) = 1 / det(A) $$

 

$$ (4) \, For \, a \, triangular \, matrix \, T, det(T) = \prod_{i=1}^{n}T_{ii} $$

삼각행렬의 행렬식은 대각원소들의 곱연산으로 계산할 수 있다.

 

그 외 많은 성질들이 있으니 알아보면 좋다.

 

---

 

3. Trace (대각합) 란 무엇인가?

대각합은 행렬식보다 정의하기 쉽다.

행렬 A의 대각합 정의는 다음과 같다. 행렬 A의 대각합은 행렬 A의 대각원소들의 합이다.

 

$$ tr(A) = \sum_{i=1}^{n}a_{ii} $$

 

---

 

4. Trace (대각합) 의 중요한 성질들

 

$$ (1) \, tr(A + B) = tr(A) + tr(B) $$ 

행렬식이 곱셈에 대해 분해되었듯, 대각합은 덧셈에 대해 분해된다.

 

$$ (2) \, tr(\alpha A) = \alpha * tr(A) $$ 

 

---

 

5. Eigenvalue, Eigenvector (고유값, 고유벡터) 란 무엇인가?

행렬 A가 있을 때, 아래 조건이 만족되면 $ \lambda $ 와 $ x $ 를 행렬 A의 고유값과 고유벡터라 한다.

 

$$ Ax = \lambda x $$

 

혹은

 

$$ det(A - \lambda I_{n}) = 0 $$

 

2*2 행렬 A에 대하여 예제를 들어보자.

 

$$ For \, 
A = \begin{pmatrix}
4 & 2 \\
1 & 3 \\
\end{pmatrix}, \,
pA(\lambda) = \begin{vmatrix}
4 - \lambda & 2 \\
1 & 3 - \lambda \\
\end{vmatrix} 
= (4 -\lambda)(3 - \lambda) - 2 * 1 = \lambda^2 - 7\lambda + 10 $$

 

$$ Eigenvalues\, \lambda = 2\, or \, 5 $$

 

그 후 고유값 2와 5 각각에 해당하는 고유벡터도 쉽게 구할 수 있다.

 

$$ \Rightarrow Eigenvector\,E_5 \, for\, \lambda = 5 \\
\begin{pmatrix}
4 - \lambda & 2 \\
1 & 3 - \lambda \\
\end{pmatrix} 
x = 0 \Rightarrow \begin{pmatrix}
-1 & 2 \\
1 & 2 \\
\end{pmatrix}
\begin{pmatrix}
x_1 \\ x_2
\end{pmatrix} = 0
 \Rightarrow E_5 = span[\begin{pmatrix}
2 \\ 1
\end{pmatrix}] $$

 

(span 이란 $\begin{pmatrix}
2 \\ 1
\end{pmatrix}$ 에 어떤 상수를 곱한 벡터도 모두 고유벡터가 된다는 의미.)

 

마찬가지로 고유값 2에 대해서도 대응하는 고유벡터를 구할 수 있다.

 

즉 고유벡터는 유니크하지 않다.

 

---

 

6. 정리

 

이렇듯 행렬식, 대각합, 고유값, 고유벡터는 밀접한 연관이 있다.

 

결론부터 말하자면, 행렬식은 고유값의 곱연산으로, 대각합은 고유값의 합연산으로 표현된다.

 

$$ det(A) = \prod_{i=1}^{n}\lambda_{i}\\
tr(A) = \sum_{i=1}^{n} \lambda_{i} $$

 

---

 

7. 행렬 분해 - Cholesky Decomposition (숄레스키 분해)

 

한 행렬을 작은 행렬 두 개의 곱으로 표현할 수 없을까?

 

행렬 A가 대칭이고, positive definite (모든 행렬값이 0보다 크다) 할 때 행렬 A는 다음과 같이 표현될 수 있다.

 

$$ A = LL^T $$

 

이 때, 행렬 L은 하삼각행렬이고 대각원소가 positive 하며 유니크하다.

이런 행렬 L을 행렬 A의 Cholesky factor 라고 한다.

 

그런데 왜 이런 분해를 하는 걸까?

 

가장 주된 이유는 행렬값 계산이 매우 쉬워지기 때문이다. 왜냐하면

 

$$ det(A) = det(L)det(L^T) = det(L^2), \, where \\
det(L) = \prod_{i}^{} l_{ii}. \, Thus,\, det(A) = \prod_{i}^{} l_{ii}^{2} $$

 

이고, 이 경우 $ det(L) $ 이 하삼각행렬이기 때문에 대각원소의 곱셈으로 표현될 수 있다.

따라서 $ det(A) = $ 대각원소 곱셈의 제곱 형태로 표현이 가능하기 때문이다.

 

---

 

8. 행렬 분해 - Eigen Decomposition, EVD (고유값 분해)

 

다음 행렬 분해 방법으로는 고유값 분해가 있다.

Diagonal matrix는 주대각원소 이외의 원소가 모두 0인 행렬로, 그 지수승을 아주 쉽게 표현할 수 있다.

대각행렬 D의 지수승은

 

$$ D^k = \begin{pmatrix}
d_{1}^{k} & 0 & 0 \\
0 & ... & 0 \\
0 & 0 & d_{n}^{k} \\
\end{pmatrix} $$

 

이고, D의 역행렬은

 

$$ D^{-1} = \begin{pmatrix}
1 / d_{1} & 0 & 0 \\
0 & ... & 0 \\
0 & 0 & 1 / d_{n} \\
\end{pmatrix} $$

 

으로 표현할 수 있다.

 

그리고 행렬식은 다음과 같다.

 

$$ det(D) = d_1d_2...d_n $$

 

즉 다양한 연산들을 매우 쉽게 표현할 수 있다.

 

그렇다면, 대각행렬이 아닌 행렬 A를 대각행렬과 유사하게 표현할 수 없을까?

가능하다.

 

대각행렬이 아닌 행렬 A에 대하여, $ D = P^{-1}AP. $ 일 때 행렬 A는 "diagonalizable" 하다. 즉 대각화 가능하다.

그렇다면, 대각행렬의 좋은 성질들을 이용하여 여러 연산을 쉽게 할 수 있다.

 

$ A^k = PD^kP^{-1} $

 

$ det(A) = det(P)det(D)det(P^{-1}) = det(D) = \prod_{i}^{}d_{ii} $

 

그렇다면 어떤 행렬이 diagonalizable 할까?

 

A가 대칭행렬이라면, 행렬 A는 항상 orthogonally diagonalizable 하다고 알려져있다.

 

다시 말해, 행렬 A가 대칭행렬이라면 $ A = PDP^T $ 를 성립하는 P와 D가 항상 존재한다는 이야기이다.

 

그리고 이는 고유값과 고유벡터에 밀접한 연관이 있다.

 

여기서 P를 고유벡터들을 모아놓은 행렬, D를 고유값을 모아놓은 대각행렬이라고 정하면, $ A = PDP^T $ 가 된다는 것을 쉽게 확인할 수 있다.

 

왜냐하면 A가 대칭인 스펙트럼 정리에 의해서

 

1. 모든 고유값이 실수이고,

2. 모든 고유벡터들이 서로 수직하고, 

3. 따라서 $ AP = PD $ 이고 $ P^T = P^{-1} $ 라는 사실과 $ A = PDP^T $ 라는 사실을 확인할 수 있다.

 

결론적으로 우리가 고유값과 고유벡터를 구할 수 있으면 이런 식으로 A를 orthogonally diagonalize 할 수 있다.

 

그렇다면, A가 대칭도 아니고, non-square (비정방행렬) 할 경우에는 diagonalize 할 수 있을까?

 

---

 

9. 행렬 분해 - Singular Value Decomposition, SVD (특이값 분해)

 

 

이 분해는 일반적인 행렬에도 적용할 수 있다.

기본적인 아이디어는 다음과 같다.

 

비정방, 비대칭한 행렬 A의 경우 $ S = A^TA $  하면, 행렬 S는 항상 대칭이고 모든 고유값이 0보다 큰 positive semidefinite 하다.

 

그렇다면 행렬 S에 대해서는 EVD가 가능하다. 그렇다면 S에 대해 EVD를 하고, 그것을 행렬 A의 분해에 활용할 수 없을까?

 

이것이 SVD의 원리이다.

 

다르게 말해서, SVD는 어떤 행렬 A가 주어졌을 때, $ A = U\sum V^T $ 로 분해하고,

여기서 U, V는 항상 직교행렬, 시그마는 대각행렬이 되는 것을 말한다.

 

이 때 시그마의 원소들을 singular values, U, V의 원소들을 singular vectors라고 부른다.

 

그렇다면 어떤 행렬이든간에 U, V, 시그마를 구할 수 있는가?

 

SVD 역시 원리의 핵심은 EVD에서 온다.

 

위에서 언급했듯, 어떤 행렬이던지 $ A^TA $ 는 항상 대칭이고 고유값이 0보다 크다.

 

따라서 $ A^TA $ 에 대해선 EVD가 가능하고 $ A^TA = VDV^T $ 로 표현할 수 있다.

 

이를 이용하여 U를 이루는 벡터들을 다음과 같이 정의할 수 있다.

 

$$ u_i = \frac{Av_i}{\sqrt{\lambda_i}},\,1\leq i\leq r. $$

 

그리고 V를 그대로 사용하면, $ U\sum = AV $ 꼴을 만족한다.

 

---

 

10. 정리

 

1. 결국 SVD는 EVD와 밀접한 연관이 있다. " EVD ($A = PDP^{-1}$) vs. SVD ($A = U\sum V^T$)

 

2. 따라서 SVD는 항상 존재한다.

 

3. EVD는 대칭행렬, 정방행렬에 한해서만 존재한다.

 

4. 따라서 보통은 데이터를 다룰 때 SVD가 더 유용하게 쓰인다.

 

 

모바일로 보면 수식이 모두 깨지는 오류가 발생하네요, 번거롭겠지만 PC모드로 보시길 바랍니다.