[Mathmatics for ML] 1. Matrix Decompositions(행렬분해)

 

 

 

주요 키워드 : Singular Value Decomposition

• 행렬들이 어떻게 더해지는지 : determinants, eigenvalues
• 행렬들이 어떻게 분해되는지 : Cholesky decomposition, diagonalization, singular value decomposition

1. Determinant and Trace

determinant : 행렬식

trace : 대각합

A,A의 역행렬

A의 역행렬이 정의되려면, $a_{11}a_{22} - a_{12}a_{21} != 0$

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

 

Laplace expansion : 3x3 det를 2x2 det로 재정의하는 방법

3x3의 det(A) = $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_{21}a_{12}a_{33}$

=

 

For a matrix $\mathbf{A} \in \mathbb{R}^{n \times n}, \text{ for all } j=1,...n,$

Expansion along column j : det(A) = $\sum_{k=1}^{n} (-1)^{k+j} a_{kj}det(A_{k,j})$

Expansion along row j : det(A) = $\sum_{k=1}^{n} (-1)^{k+j} a_{jk}det(A_{j,k})$

 

정리 : det(A) ≠0 일 때 A의 역행렬 존재

 

행렬식의 주요속성

$det(AB) = det(A) det(B)$

1. $det(A) = det(A^T)$
2. $det(A^{-1}) = 1/det(A)$
3. T가 triangular matrix라면, $det(T) = \prod_{i=1}^{n} T_{ii}$

Trace

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

 

대각합의 주요 속성

1. $tr(A+B) = tr(A) + tr(B)$
2. $tr(\alpha A) = \alpha tr(A)$
3. $tr(I_n) = n$

2. Eigenvalues and Eigenvectors

Eigenvalue : 고윳값

EigenVector : 고유벡터

$I_n$ : 단위행렬

Def

A의 Eigenvalue : $\lambda$

A의 Eigenvector : $x$

 

$\text{matrix } \mathbf{A} \in \mathbb{R}^{n \times n}, Ax = \lambda x$ , A를 선형변환으로 봤을 때 자기 자신의 상수 배가 되는 0이 아닌 벡터 : eigenvector, 상수배 값 : eigenvalue

$det(A-\lambda I_n) = 0$ → eigenvalue를 구하고 싶을 때 $A-\lambda I_n=0$이 되는 방정식을 풀면 됨.

 

ex)

⇒ $\lambda$ = 2 or 5

$\lambda$ = 5 라면

$\left( {-1\atop 1} {2\atop -2} \right)$$\left( {x_1\atop x_2}\right)$ = 0 ⇒ $span[\left( {2\atop 1}\right)]$

$\lambda$ = 2 라면

$\left( {2\atop 2} {1\atop 1} \right)$$\left( {x_1\atop x_2}\right)$ = 0 ⇒ $span[\left( {1\atop -1}\right)]$

⇒ eigenvector는 unique하지 않을 수 있음

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

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

⇒ det(A), tr(A)를 구하려면 eigenvalue를 구해보는 것도 방법

 

Matrix Decomposition - 행렬들이 어떻게 분해되는지

• Decomposition : 주어진 행렬을 작은 행렬들의 곱으로 나타내는 것. 알면 determinant 계산이 매우 쉬워짐
• Diagonal matrix : 대각행렬. 주대각성분이 아닌 모든 성분의 값이 0인 행렬

 

3. Cholesky Decomposition

A : 대칭(symmetric), positive matrix

$A = LL^T$

L : lower-triangular matrix, 대각 값이 모두 0보다 큰 행렬 → Cholesky factor

$det(A) = det(L)det(L^T) = det(L)^2$

$det(A) = \prod_{i=1}I^2_{ii}$

⇒ Det 계산이 매우 쉬워짐

 

4. Eigen Decomposition( = EigenValue Decomposition, EVD) and Diagonalization

• EVD : $A = PDP^T$

→ square matrix일 때, basis of eigenvectors가 존재할 때

• Symmetric matrix는 항상 EigenDecomposition이 가능함.

P : orthogonal하지 않아도 ㄱㅊ

 

EigenValue Decomposition(EVD) :

$\mathbf{A} \in \mathbb{R}^{n \times n} \text{is orthogonally diagonalizable} <=> \text{A is symmetric}$

⇒ Eigenvalue & Eigenvector를 구할 수 있으면 A를 orthogonally Diagonalization 할 수 있음

Diagonal Matrix 특징

A가 diagonal matrix와 유사하면, diagonalizable.

$D = P^{-1}AP => A = PDP^{-1}$ 이면, diagonalizable

⇒ D : A의 eigenvalue, P : A의 eigenvector

ex)

A = symmetric vector

각 벡터를 normalize해서 orthonormal vector로 표현하기

⇒ P : A의 Eigenvector로 이루어진 행렬, D : A의 eigenvalue로 이루어진 행렬

 

이를 활용하면, $A^2, A^3$,, 등을 구하기 쉬움

$D^2 = P^{-1}AP*P^{-1}AP = P^{-1}A^2P => A^2 = PD^2P^{-1}$

 

$PP^T = I$인, orthogonal한 행렬 P이므로

$PP^T = PP^{-1}$

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

 

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

 

5. Singular Value Decomposition (SVD)

• Singular value(특잇값) : 고윳값(Eigen Value)의 제곱근
• → $Av = σu$, $σ_i = \sqrt{\lambda_i}​$
• SVD를 어떻게 계산하는지
• Eigen decomposition과의 관계

SVD : 일반적인 value decomposition에 다 적용가능 (A ≠ symmetric 할 때에도 가능)

• $A = U\sum V^T$로 A를 분해하는 것
• U,V : orthogonal
• $\mathbf{U} \in \mathbb{R}^{m \times n}$, $\mathbf{\sum} \in \mathbb{R}^{m \times n}$,$\mathbf{V} \in \mathbb{R}^{n \times n}$
• U : $AA^T$를 EigenDecomposition 해서 얻어진 orthogonal matrix. U의 열벡터 : A의 left singular vector
• 어떤 matrix의 SVD = matrix $AA^T$의 EVD
• A가 symmetric ⇒ EVD = SVD

[Extensions]

1. diagonalization for non-symmetric, but still square matrices $\mathbf{A} \in \mathbb{R}^{n \times n}$
2. diagonalization for non-symmetric, and non-square matrices $\mathbf{A} \in \mathbb{R}^{m \times n}$

[Background]

$\mathbf{A} \in \mathbb{R}^{m \times n}$, matrix S : $A^TA\in \mathbb{R}^{n \times n}$ 는 항상 symmetric, positive semidefinite

(모든 eigenvalue > 0) ⇒ S는 eigen decomposition이 가능함.

• Symmetric ⇒ $S^T = (A^TA)^T = A^TA = S$
• $x^TSx = x^TA^TAx = (Ax)^T(Ax)$ ≥ 0
• U,V : orthogonal matrics, $UU^T = I, VV^T=I$
• U : $AA^T$를 EigenDecomposition해서 얻은 orthogonal matrix
• V : $A^TA$를 EigenDecomposition해서 얻은 orthogonal matrix
• $u_i, v_j$ : left / right singular vector
• $\sum$ : diagonal matrix, A의 singular value.

• Eigen Decomposition으로 모든 matrix의 $U, \sum, V$를 구할 수 있음

<어떻게 $U, \sum, V$를 구하는가?>

어떠한 matrxix A라도 ($\mathbf{A} \in \mathbb{R}^{n \times n}$), $A^TA$ : symmetric, positive definite. ⇒ EigenDecomposition 적용 가능

$AA^T = VDV^T$

• D : $A^TA$의 Eigenvalue
• V : $A^TA$의 Eigenvector

$\mathbf{u}_i = \frac{\mathbf{A}\mathbf{v}_i}{\sqrt{\lambda_i}}, \quad 1 \leq i \leq r.$

⇒ $U\sum = AV$

⇒ $A = U\sum V^T$