Matrix Decomposition

Matrix Decomposition

TODO: svd를 제외한 나머지
https://en.wikipedia.org/wiki/Matrix_decomposition

Decompositions based on eigenvalues and related concepts

1. Singular Value Decomposition(SVD)

m x n matrix $M$에 대해 SVD는 다음과 같이 정의된다.

$$
M = U\Sigma V^{T}
$$

$U$: m x m unitary matrix ($AA^{T}=U(\Sigma\Sigma^{T})U^{T}$)

$\Sigma$: m x n rectangular diagonal matrix with non-negative real numbers on diagonal

$V$: n x n unitary matrix ($A^{T}A=V(\Sigma^{T}\Sigma)V^{T}$)

만약 $M$이 real 이라면 $U, V^{T}$는 orthgonal matrix며 SVD는 singular values $\Sigma$ii가 descending order이기만 하면 되므로 not unique이다.

SVD는 pseudo inverse를 계산하는데에 유용하고 data fitting을 위한 least square에도 유용하게 쓰인다.

SVD의 기하학적 의미를 잘 나타낸 그림은 아래와 같다(출처: wikipedia)

결국 $U$와 $V^{T}$는 basis의 rotation을 의미하고 $\Sigma$는 original coordinate를 기준으로 scaling을 하는 역할을 한다고 생각하면 되겠다.

SVD의 대표적인 적용 예시는 앞서 말했듯 pseudo inverse이다. 이 pseudo inverse를 이용해 least square problem $||Ax - b||$ 를 최소화 하는 해를 $x = A^{+}b$ 와 같이 구할 수 있다.

$$
\mathbf{M}^+ = \mathbf{V} \boldsymbol{\Sigma}^+ \mathbf{U}^T
$$