[Linear Algebra] SVD 간단하게 알아보기

지난 글에서 Eigen Value, Eigen Vector를 구하고 이를 통한 Matrix의 Eigen Decomposition에 대해서 알아보았다.

 

이번 포스팅에서는 일반적인 직사각형의 matrix에 대한 Decompostion이 가능한 SVD(Singular Value Decomposition)

 

에 대해서 작성해보려고 한다.

 

 

SVD는 Singular Value Decomposition의 약자로 m by n matrix를 여러개의 간단한 형태로 Decomposition 하는 것을 의미한다. Eigen Decomposition과 비슷하지만 어떤 matrix 더라도 Decomposition이 가능하다는 것이 큰 특징이다. SVD와 Eigen Vectors는 큰 연관성을 갖는다.

어떤 matrix $A$에 대해서 $AA^T, A^TA$ 모두 square matrix가 된다는 것은 알 것이다. 이를 전제로 해서 다음과 같이 정의를 할 수 있다.

 

a. Left singular vectors (unit eigenvectors of $AA^T$) = $u's$

b. Right singular vectors (unit eigenvectors of $A^TA$) = $v's$

c. singular values = $\sigma$ (참고로 $AA^T, A^TA$의 eigenvalues 의 square root 값과 모두 같다.)

그래서 다음 조건을 만족한다.

$$ AA^Tu_i = \sigma_i^2u_i, A^TAv_i = \sigma_i^2v_i, Av_i = \sigma_iu_i $$

 

우리가 m by n의 matrix A를 가정할 때 matrix의 rank를 r이라 하자. Eigen Decomposition $D = X^{-1}AX $ 처럼 대각화를 할 수 있을까?? 답은 될 수도 있고 안될 수도 있다. $ Ax = \lambda x $ 를 만족하는 eigen vector는 square matrix가 전제되어야 한다. 이러한 문제들을 해결해주는 것이 바로 SVD이다. singular vector는 어떤 matrix에 대해서도 decomposition, 대각화가 가능하도록 해준다.

SVD?

$ u's, v's $ : singular vectors, U : m by m matrix, V : n by n matrix 라 하자.

그리고 A를 rank r의 m by n matrix라 할 때, SVD는 다음과 같이 나타낼 수 있다.

$$ A = U\Sigma V^T = u_1\sigma_1v_1^T + \cdots + u_r \sigma_r v_r^T $$

 

예시를 통해 확인해보자

 

$ A = \begin{bmatrix} 3 && 0 \\ 4 && 5 \end{bmatrix} $에 대해서 U, $\Sigma$, V matrix를 구해보자. 이때 $A$의 rank = 2 이다. A가 rank 2 이므로 singular values도 positive 값 2개를 갖는다.

 

$$ A^TA = \begin{bmatrix} 25 && 20 \\ 20 && 25\end{bmatrix}, AA^T = \begin{bmatrix} 9 && 12 \\ 12 && 41 \end{bmatrix} $$

$$ \sigma_1^2 = 45, \sigma_2^2 = 5 (AA^T, A^TA \ eigenvalues)$$

$$ \sigma_1 = \sqrt{45}, \sigma_2 = \sqrt{5}, \sigma_1\sigma_2 = 15 = \det A $$

$$ \begin{bmatrix} 25 && 20 \\ 20 && 25 \end{bmatrix} \begin{bmatrix} 1 \\ 1 \end{bmatrix} = 45 \begin{bmatrix} 1 \\ 1 \end{bmatrix}, \begin{bmatrix} 25 && 20 \\ 20 && 25 \end{bmatrix} \begin{bmatrix} -1 \\ 1 \end{bmatrix} = 5 \begin{bmatrix} -1 \\ 1 \end{bmatrix} $$

Right Singular vectors : $ v_1 = \frac{1}{\sqrt{2}}\begin{bmatrix} 1 \\ 1 \end{bmatrix}, v_2 = \frac{1}{\sqrt{2}}\begin{bmatrix} -1 \\ 1 \end{bmatrix}$

Left Singular vectors  : $ u_i = \frac{1}{\sigma_i}Av_i $

$$ Av_1 = \begin{bmatrix} 3 && 0 \\ 4 && 5 \end{bmatrix} \frac{1}{\sqrt{2}}\begin{bmatrix} 1 \\ 1 \end{bmatrix} = \frac{3}{\sqrt{2}}\begin{bmatrix} 1 \\ 3 \end{bmatrix} = \frac{\sqrt{45}}{\sqrt{10}}\begin{bmatrix} 1 \\ 3 \end{bmatrix} = \sigma_1u_1 $$

$$ A_v2 = \begin{bmatrix} 3 && 0 \\ 4 && 5 \end{bmatrix} \frac{1}{\sqrt{2}}\begin{bmatrix} -1 \\ 1 \end{bmatrix} = \frac{\sqrt{5}}{\sqrt{10}}\begin{bmatrix} -3 \\ 1 \end{bmatrix} = \sigma_2u_2 $$

$$ U = \frac{1}{\sqrt{10}}\begin{bmatrix} 1 && -3 \\ 3 && 1 \end{bmatrix}, \Sigma = \begin{bmatrix} \sqrt{45} && 0 \\ 0 && \sqrt{5} \end{bmatrix}, V = \frac{1}{\sqrt{2}}\begin{bmatrix} 1 && -1 \\ 1 && 1 \end{bmatrix} $$

$$ \sigma_1u_1v_1^T + \sigma_2u_2v_2^T = \begin{bmatrix} 3 && 0 \\ 4 && 5 \end{bmatrix} = A $$