LG Aimers | Matrix Decomposition (행렬 분해)

 

1) Determinants & Trace

2) Eigenvalues & Eigenvectors

3) Cholesky Decomposition

4) Eigendecomposition & Diagonalization

5) Sigular Value Decomposition

 

 

📌 Derterminant (행렬식) : Motivation (1)

 

• 2*2 Matrix

 $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}$

 

2*2 Matrix & 역행렬

 

$a_{11}a_{22}-a_{12}a_{21}$ = determinant 

▶ 해당 항이 0인지 아닌지에 따라 determinant 값이 존재하는지 아닌지가 정해짐

 

• 3*3 Matrix

Gaussian elimination 도구 등을 이용하면 Determinant 공식 구할 수 있음 

 

 

 

 

3*3 Matrix Determinant 패턴 발견 

 

 

▶ 2*2 Determinant의 Recursive formular 형태로 정의 (e.g. $A_{1,1}$)

 

🔎 $A_{1,1}$ 이란?
3*3 Matrix의 첫 번째 Entry 1,1 (첫 번째 Column & 첫 번째 Row) 제외한 Matrix

e.g.
$\begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{bmatrix}$ 
中
$\begin{pmatrix} a_{22} & a_{23} \\ a_{32} & a_{33} \end{pmatrix}$ 부분

 

$A_{1,1}$ Entry(=$a_{11}$)가 앞에 들어가고 $(-1)^{1+1}$, $determinant(A_{1,1})$ +

$A_{1,2} =(a_{12})$ 곱해지고 $(-1)^{1+2}$ 여기는 {1,2}이기 때문에 1+2가 되는 것 $determinat(A_{1,2})$ (=첫 번째 열과 두 번째 행을 제외한 Matrix를 의미) +

....

 

이런 식으로 2*2 Determinant를 사용해 계산한 식과 Original 3*3 Determinat entry가 서로 동치

 

∴ 3*3 Matrix를 2*2 Matrix로 재정의할 수 있다

 

▶Laplace expansion 

 

이 형태를 이용해서 Determinant 정의

 

 

Determinant : Formal Definition

 

column과 row에 entry Determinant를 따로 정의할 수 있으며, 결국은 같은 개념 

Determinant 정의 시, Sub-matrix Determinant의 Recursive Formula 정의 가능 

 

 

명제.

$det(A)\ne0 \Longleftrightarrow rk(A) = n \Longleftrightarrow A$

Determinat가 0인지 아닌지에 따라 Matrix A의 역행렬이 존재하는지 아닌지 구분

 

 

Determinant의 성질

• det(AB) = det(A) det(B) 

▶ det 연산과 행렬의 곱셈 연산은 분리될 수 있음 

 

• det(A) = det($A^T$)

▶ det(A)는 det(A)의 transpose와 같음 

 

• det($A^{-1}$) = 1/det(A)

▶ det의 inversion의 det는 1/det 와 같음

 

• traingular $matrix^1 T, det(T) = \prod_{i=1}^n T_{ii}$

▶ 트라이앵글 매트릭스는 $T_{ii}$ (Diagonal Entry)를 곱하면 계산할 수 있음 

 

🔎 traingular matrix 란?
 대부분의 오른쪽 위 삼각형 entry가 0, 반대쪽 entry만 살아있는 형태 

 

 

📌 Trace

 

Matrix의 Diagonal Entry를 다 더한 형태 

 

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

 

 

• determinant가 곱셈에 대해 분리되었다면 trace는 덧셈에 대해 분리

 

📌 Eigenvalue & Eigenvector

matrix A가 주어졌을 때, $Ax= \lambda x$ 이면

Scala value인 $\lambda$와 x Vector를 Eigenvalue & Eigenvector로 부름

 

 

➕ det(A-$\lambda I_n$)=0 조건과 일치 

 

 

e.g.

 

2*2 matrix가 있을 때, Dignal Entry에 $\lambda$를 빼고 determinat를 구하면 

$(4- \lambda)(3 -\lambda) - 2·1$ = $\lambda^2 -7\lambda +10$ = 0

 

▶$\lambda=2 or \lambda=5$  => Matrix Eigenvalue

 

 

Eigenvector $E_5 \lambda=5$ 일 때, $E_5 = span[{2 \choose 1}]$ ${2 \choose 1} 에 어떤 c를 곱한 어떤 Vector도 다 Eigenvetor가 됨 

 

$E_2 = span[{1 \choose -1}]$

 

▶ Eigenvector가 unique하지 않음 

 

 

🔎 Eigenvalue/Eigenvector 와 Trace/Determinant 사이의 연관관계

Determinant. Eigenvalue 들의 곱셈
det(A) = $\prod^n_{i=1} \lambda_i$

Trace. Eigenvalue 들의 덧셈 
tr(A) = $\sum^n_{i=1} \lambda_i$

 

 

📌 Matrix Decomposition : Cholesky Decomposition

주어진 행렬을 어떤 작은 행렬 두 개의 곱셈으로 나타낼 수 없을까 (=분해, Decompostition)

 

Theorem 명제.

Matrix A가 symmetric(대칭)이고 positive definite (모든 Eigenvalue 값 > 0)일 때, 

$A=LL^T$

 

L ▶ Lower-triangular Matrix

→ 대부분의 Upper Entry가 0 , 밑에 Entry만 살아있는 형태 & Positive Diagonal 

→ L은 unique하며 A의 Cholesky factor라고 부름 

 

Decomposition 이유 

 

분해할 경우, Determinant 계산이 쉬워짐  

▶ Determinant는 곱셈에 대해 분리가 가능, $det(A)=det(L)det(L^T)$  

▶$det(L^T)= det(L) 이므로, det(L)^2$

▶det(L)은 Lower-Triangular Matrix 이므로, $\prod_i l_{ii}$ (=diagonal entry 곱셈)

 

∴ det(A) = $\prod_i L^2_{ii}$

 

 

📌 Eigendecomposition & Diagonalization

 

🔎 Diagonal Matrix and Diagonalization

 

Diagonal Matrix

Matrix 인데 Diagonal Entry 만 살아있고 나머지 Entry는 0인 형태 

▶ 다양한 연산들이 쉽게 되는 여러가지 성질들을 가지고 있음

 

$D\begin{pmatrix} d_1 &\cdots & 0 \\ \vdots & &\vdots \\ 0 & \cdots & d_n \end{pmatrix}$

 

• Diagonal Matrix의 지수승, 즉 $D^k$ 가 쉽게 표현됨 ( =Diagonal Entry만 k번 곱하면 됨)

 

 $D^k=\begin{pmatrix} d_1^k &\cdots & 0 \\ \vdots & &\vdots \\ 0 & \cdots & d_n^k \end{pmatrix}$

 

• Diagonal Matrix 역행렬도 Diagonal Entry 역수만 구하면 됨

$D^{-1}=\begin{pmatrix} 1/d_1 &\cdots & 0 \\ \vdots & &\vdots \\ 0 & \cdots & 1/d_n \end{pmatrix}$

 

• Determinant도 Diagonal Matrix에 곱셈하면됨

det(D) = $d_1d_2\cdots d_n$

 

 

Q. 일반적인 Matrix를 Diagonal Matrix와 유사한 형태로 표현할 수 없을까?

A. Matrix A가 diagonalizable

 

D는 Diagonal matrix, P는 일반적인 Invertible Matrix

$D=P^{-1}AP.$

 

e.g.

$D^2=(P^{-1}AP)^2=P^{-1}APP^{-1}AP=P^{-1}A^2P$

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

 

A. A가 diagonalizable 하면서 P가 orthogonal Matirx인 경우 ($=P^{-1}=P^T$)

$D = P^{-1}AP = P^TAP$

 

 

일반적인 Matrix도 Diagonal Matrix 성질 이용해서 쉬운 계산 가능

• $A^k=PD^kP^{-1}$
• det(A) = det(P)det(D)det(P^{-1})=det(D)=\prod_i d_{ii}$

 

 

Q. 그렇다면 어떤 Matrix를 $PDP^T$ 형태로 Diagonal하게 표현할 수 있을까?

A. A가 symmetric Matrix 인 경우, 항상 Orthogonally diagonalizable

 

▶ P는 Eigenvector를 모아놓은 Matrix, D는 Eigenvalue들을 모아놓은 Diagonal Matrix

 

A가 Symmetric 한 경우, Spectral theorem(스펙트럼 정리)에 의해

1) 모든 eigenvalue 가 실수(Real number)

2) eigenvector 들은 서로 수직하게 됨  ▶ $P^T = P^{-1}$

 

Eigenvalue & Eigenvector 정의 활용 시, $AP = PD$ 성질 확인 가능

 

 

 

Q. A가 Symmetric 하지않고, Square Matrix도 아닌 경우 Matrix Decomposition이 가능한가?

A. Singular Value Decomposition

 

Eigne Value Decomposition 은 Symmetric Matrix에만 적용 가능

Singular Value Decomposition 은 일반적인 Matrix에 다 적용 가능

 

 

e.g.

$A \in \mathbb{R}^{m\times n}$ 

▶ Matrix A가 Symmeric, square 가 아님

 

$S := A^TA$, S는 항상 Symmetric 하고, Positive Semidefinite (정치 행렬, 정부호 행렬)

 

🔎 Positive Semidefinite
모든 Eigenvalue들이 0보다 큰 것 

https://sine-qua-none.tistory.com/69

행렬이 양수다? positive semidefinite

 

 

 

S에 대한 Eigendecomposition을 Original Matrix인 A에 대한 Decomposition 으로 활용할 방법 

 

 

📌 Singular Value Decomposition 

어떤 Matrix A가 있을 때,

$A = U \sum V^T$

 

U와 V는 항상 Orthogonal Matrix, $UU^T= I, VV^T=I$

$\sum$는 Diagonal Matrix (Diagonal entry만 남아있고 나머지는 0이 되는 형태)

 

 

 ✅  Eigendecomposition : $A = PDP^T$

▶ P는 eigne vector, D는 Diagonal Matrix, 앞과 뒤가 거의 유사한 형태

 ✅  Singular Value Decomposition : $A = U \sum V^T$

▶U와 V가 서로 다른 형태

• Sigma의 Diagonal entry를 singular value라고 부름 
• U를 구성하는 Vector들을 Singular Vector, V를 구성하는 Vector는 Right Singular Vector

 

 

Q. 어떤 Matrix든 간에 U, $\sum$, V를 어떻게 구할 수 있는가?

 

A. 핵심은 Eigendecomposition

 

어떤 Matrix A라도 $A^TA$를 하면 항상 Symmetric & Positive definite 

▶ $A^TA = VDV^T$ Eigendecomposition 적용 가능 

V는 $A^TA$의 Eigenvector들, D는 Eigenvalue 모아놓은 것 

 

$A^TA$가 Positive definite이기 때문에 D를 이루는 Entry들은 항상 0보다 크다 

▶ $\lambda_1 \ge \cdots \ge \lambda_r \ge \lambda_{r+1} = \cdots \lambda_n = 0$

 

 

U의 vector들은

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

 

$U\sum = AV$

 

 

🔔 EVD(Eigen Value Decomposition) vs. SVD (Singular Value Decomposition)

Eigen Value Decomposition

$A= PDP^{-1}$

• Symmetric Matrix 나 Squrare Matrix에 한해서만 존재 

 

Singular Value Decomposition

EVD의 확장형, $U\sum V^T$ 

• 항상 존재, Data 다룰 때 SVD가 더 유용하게 쓰이는 경우가 많음 
• SVD가 EVD에서 왔기 때문에 항상 기억해야 함 
• Matrix A $AA^T$의 Eigenvalue Decomposition 과 동치 
• 만약 A가 Symmetric 하면 EVD=SVD