728x90
Matrix Decomposition (행렬분해)
1. Determinant
det A : 정사각행렬 A를 하나의 수로서 대응시키는 특별한 함수
- only 정사각행렬
- vector는 정의 X
- M_ij : Minor(소행렬식) = i행, j열을 모두 지운 후 남은 element끼리 determinant처리
- C_ij : Cofactor (여인수) = M_ij * (-1)^(i+j) : (0,0)에서 시작해서 1칸씩 건너갈 때마다 (-1)을 곱한다고 생각
- 기본행 연산 (A->B)
- 두 행을 swap : -|A| = |B|
- 한 행을 상수배 : c|A| = |B| (행렬식 전체가 c로 묶임)
- 한 행을 상수배하고 다른 행에 + : |A| = |B| (same)
- Determinant 구하기
- 기준을 잡은 행 or 열에 '0'을 최대한 많이 만들기
- 기준 행 or 열을 잡고 '부호' & 'Minor' 계산
- just addition (기준 element * 부호 * Minor을 더하기)
- Triangle Matrix의 Determinant = 각 entry 들끼리 곱하기
- Properties
- |A| * |B| = |AB|
- |A| = |A^T|
- |A^-1| = |A|^-1 = 1 / |A| : inverse determinant = reciprocal of A
2. Trace
tr(A) : 정사각행렬 A의 주대각선 성분을 전부 더한 것
3. Eigenvalue and Eigenvector
방정식 Ax = λx : Eigenvalue Problem
< -> (A-λI)x = 0 <-> det(A-λI) = 0
- A: square matrix
- λ: Eigenvalue of A
- X_n : Eigenvector corresponding to λ_n (Non-zero Vector)
- D(λ) = det(A-λI) : characteristic determinant (characteristic polynomial, A의 특성다항식)
- D(λ) = det(A-λI) = 0 : characteristic equation of A (A의 특성방정식)
- A-λI : characteristic matrix (A의 특성행렬)
- Eigenvectors are not unique (서로 상수배하면 표현가능해지므로)
- STEPS
- D(λ) = det(A-λI) = 0: λ Eigenvalues 구하기
- λ들을 (A-λI)x = 0 식에 대입하기
- x Eigenvectors 구하기
- Tip : x_1 = 0 or 1 or ... 등의 값을 대입하기 (all x = 0인 case만 제거)
- 각 Eigenvalue λ 마다 각 Eigenvector x 존재
- if λ가 중근 : Eigenvector x를 서로 linear independent하게 조정가능
4. Cholesky Decomposition
주어진 행렬을 어떤 작은 2개의 행렬의 곱으로 나타내는 방법
- Determinant를 구하기 매우 쉽다 : Matrix L의 주대각선 성분들을 전부 곱한 후 제곱처리
- $det(A) = det(L)^2 = \prod_{i}l_{ii}^{2}$
- Square matrix H와 n차원 vector y 에 대하여 :
- PD : $y^{T}Hy >0$ for all $y\neq 0$
- PSD : $y^{T}Hy\geq 0$ for all $y$
- ND : $y^{T}Hy <0$ for all $y\neq 0$
- NSD : $y^{T}Hy\leq 0$ for all $y$
- Leading Principal Minor : $D_{k}$
- 처음 $k \times k$ matrix만 남긴 후 determinant 구하기
- Principal Minor : $\Delta _{k}$
- 주대각선의 일부 성분을 기준으로 row, column 제거 후 $k \times k$ matrix만 남긴 후 determinant 구하기
- Leading Principal Minor 또한 포함
- H가 symmetric matrix라면 :
- PD : $D_{k} >0$ for all $D_{k}$
- PSD : $\Delta _{k}\geq 0$ for all $\Delta _{k}$
- ND : $(-1)^{k}D_{k} > 0$ for all $D_{k}$
- PSD : $(-1)^{k}\Delta _{k}\geq 0$ for all $\Delta _{k}$
5. Eigendecomposition: only for symmetric matrices ($A = PDP^{-1}$)
- Diagonal Matrix : 다양한 연산들이 매우 쉽게 되는 좋은 성질 존재
- Main diagonal을 제외한 나머지 entry가 모두 0인 matrix
- Matrix D를 k번 곱한 Matrix는 diagonal entry만 k번 곱하면 (지수승) 된다
- D의 역행렬(inverse matrix) 또한 각 diagonal entry를 -1승 처리하면 된다
- Determinant는 각 diagonal entry를 전부 곱하면 된다
- 일반적인 Matrix A를 Diagonal Matrix와 유사한 형태로 표현할 수 있지 않을까?
- $D = P^{-1}AP$ : A is diagonalizable
- P가 invertible matrix
- D가 diagonal matrix
- $D^{k} = P^{-1}A^{k}P$
- $D = P^{-1}AP = P^{T}AP$ : A is orthogonally diagonalizable
- P가 orthogonal matrix ($P^{-1} = P^{T}$)
- D가 diagonal matrix
- A가 symmetric <-> A is orthogonally diagonalizable
- always $A = PDP^{T}$로 표현되는 P,D가 존재
- Eigenvector들을 모아놓은 Matrix P
- Eigenvalue들을 모아놓은 Matrix D
6. Singular Value Decomposition: general matrices ( $A = U\sum V^{T}$ )
- General Matrix A $m \times n$
- $S = A^{T}A$ 는 항상 symmetric하고 PSD이다 (모든 eigenvalue들이 0보다 크다)
- S에 대해서는 Eigendecomposition이 가능한데, 이를 original matrix A에 적용할 수 없을까
- Singular Value Decomposition
- $AA^{T} = I$의 Eigendecomposition과 동치
- $A = U\sum V^{T}$ 형태로 분해하는 것
- U, V : Orthogonal matrix ($UU^{T} = I, VV^{T} = I$)
- $sum$ : diagonal entry만 남아있고 나머지는 0이 되는 matrix
- $sum$의 diagonal entries : singular values 라고 부름
- U,V 를 구성하는 vectors : 각각 left, right singular vectors
728x90
