SVD(Singular Value Decomposition)

 

🩴 저번 선형대수학 포스팅에서는 고유벡터 분해 eigendecomposition에 대해 배웠다.

eigendecomposition

 

🩴 이번에는 유사한 분해 '특잇값 분해(Singular Values Decomposition)'에 대해서 알아보려 한다.

SVD 정의

"모든 mxn matrix는 $A = U \Sigma V^T$ 형태로 분해된다."

 

※ eigendecomposition은 nxn matrix에서만 가능했지만, singular value decomposition은 모든 mxn matrix에 대해 분해 가능

 

① $U$는 mxm orthogonal matrix

② $\Sigma$는 mxn diagonal matrix (non-negative $\lambda$의 decreasing order로 구성)

③ $V^T$도 nxn orthogonal matrix 

→ $U$ - $\Sigma$ - $V^T$, 즉 rotate - stretch - rotate 순

 

→ $U$는 $AA^T$ 행렬의 고유벡터를 열로 갖는 행렬 (left singular vectors)

→ $V$는 $A^TA$ 행렬의 고유벡터를 열로 갖는 행렬 (right singular vectors)

→ $\Sigma$는 대각행렬로, 대각원소($\sigma$)는 $A^TA$(또는$AA^T$)의 eigenvalues($\lambda_i$)에 root를 씌운 값 ($\sqrt{\lambda_i}$) (A의 singular values)

---

자세히 풀면..

$$A = \begin{bmatrix}
u_1 & u_2 \\
\end{bmatrix}\begin{bmatrix}
\sigma_1 & 0 \\
0 & \sigma_2 \\
\end{bmatrix}\begin{bmatrix}
v_1^T \\ v_2^T
\end{bmatrix}$$

정의가 나온 이유를 직접 계산해 보면..

$$A = U \Sigma V^T$$

---

① $A^TA$에 관해 계산하면..

$$A^TA = (V\Sigma^TU^T)U\Sigma V^T = V\Sigma^T \Sigma V^T$$

(U는 orthogonal matrix이므로 $U^TU$는 identity matrix가 된다)

 

→ 식을 자세히 보면, $A^TA$의 eigendecomposition 식임을 캐치할 수 있다.

→ $A^TA$는 symmetric한 square matrix

→ V는 orthogonal matrix(eigenvector의 모임)

→ $\Sigma^T \Sigma$는 $A^TA$의 $\lambda$이자 $A$의 $\sigma^2$

 

② 이제 $AA^T$에 관해 계산하면..

$$AA^T = U\Sigma V^T V \Sigma^T U^T = U\Sigma \Sigma^T U^T$$

 

→ 역시 $AA^T$의 eigendecomposition 식

→ 따라서, $AA^T$와 $A^TA$의 eigenvalue가 서로 동일

SVD examples & real-world application

* examples

$$A = \begin{bmatrix}
2 &  2\\
1 &  1\\
\end{bmatrix} = \frac{1}{\sqrt{5}}\begin{bmatrix}
2 & 1\\
-1 & 2\\
\end{bmatrix}\begin{bmatrix}
\sqrt{10} & 0 \\
0 &  0\\
\end{bmatrix}\frac{1}{\sqrt{2}}\begin{bmatrix}
1 & 1 \\
1 & -1 \\
\end{bmatrix}$$

 

→ A는 det(A)=0인 singular matrix로, singular values는 $\sqrt{10}$과 0이 있다

* applications

→ 실제에서는 A의 SVD 분해 결과 가장 많은 정보를 갖고 있는 $u_1 \sigma_1 v_1^T$를 원하는 경우가 많으며($\Sigma$의 $\lambda$가 감소하는 방향으로 구성), 다양한 기법에 많이 사용된다. 식으로 자세히 살펴보자.

 

→ 각각의 여러 vector와 $\lambda$로 자세히 나타내면

$$X = \begin{bmatrix}
x_1 & x_2 & x_3 & ... & x_n \\
\end{bmatrix}=U \Sigma V^T$$ 

$$= \begin{bmatrix}
u_1 & u_2 & u_3 & ... & u_n \\
\end{bmatrix}\begin{bmatrix}
\sigma_1 &  &  &  \\
 & \sigma_2 &  &  \\
 &  & \sigma_3 &  \\
 &  &  & \sigma_m \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
\end{bmatrix}\begin{bmatrix}
v_1 & v_2 & v_3 & ... & v_m \\
\end{bmatrix}^T$$

$$= \begin{bmatrix}
u_1 & u_2 & u_3 & ... & u_n \\
\end{bmatrix}\begin{bmatrix}
\sigma_1 &  &  &  \\
 & \sigma_2 &  &  \\
 &  & \sigma_3 &  \\
 &  &  & \sigma_m \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
\end{bmatrix}\begin{bmatrix}
v_1^T \\
v_2^t \\
... \\
v_m^T \\
\end{bmatrix}$$

 

① $U$에서의 여러 $u_1, u_2, ... u_n$은 각각 $x_1, x_2, ... x_n$ 개체의 eigen 고유 특성을 hierarchically organized한 모음

② $\Sigma$에서의 여러 $\lambda$값은 각 개체의 전체 X를 기여하는데의 각각의 기여도를 decreasing order - 즉 중요도 순서로 나열

③ $V$에서의 여러 $v_1, v_2, ... v_n$은 예를 들어 $v_1$의 경우 $x_1$을 만들기 위한 모든 $u_1, u_2, ... u_n$ eigen mixture

 

→ 즉 각각 중요도 순서대로 항으로 나누어 분해하면

$$= \sigma_1u_1v_1^T + \sigma_2u_2v_2^T + ... + \sigma_mu_mv_m^T + 0$$

 

→ 여기서 $x_1 .. x_m$ 총 m개만 존재하므로 n>m이라면 나머지 요소는 모두 0

→ 따라서 전체 n개를 고를 필요 없고, 중요 정보 m개만 선택.

→ 이보다도 더 적은 수의 개수만 골라 중요 정보만 고를 수 있다. (추후 PCA 포스팅 참조)

python

🩴np.linalg.svd() 사용

→ 3x2 X의 SVD → 3x3의 U와 2개의 singular values, 그리고 2x2의 $V^T$

→ 결과적으로 $\sigma_1u_1v_1^T + \sigma_2u_2v_2^T$로 분해

import numpy as np
np.set_printoptions(suppress=True)

X = np.array([[7, 2],
             [3, 4],
             [5, 3]])

U,sing_values,VT=np.linalg.svd(X)

U
'''
array([[-0.69366543,  0.59343205, -0.40824829],
       [-0.4427092 , -0.79833696, -0.40824829],
       [-0.56818732, -0.10245245,  0.81649658]])
'''

sing_values #array([10.25142677,  2.62835484])

VT
'''
array([[-0.88033817, -0.47434662],
       [ 0.47434662, -0.88033817]])
'''

 

🩴실제로 $XX^T$의 eigendecomposition에서 $XX^T$의 eigenvector matrix가 U임을 확인하였다. 그리고 fill_diagonal()을 사용해 영행렬에 singular values를 넣으면 원래 식대로 $U\Sigma V^T$의 결과가 올바르게 나옴을 확인할 수 있다.

np.linalg.eig(np.dot(X,X.T))[1]
'''
array([[-0.69366543, -0.59343205, -0.40824829],
       [-0.4427092 ,  0.79833696, -0.40824829],
       [-0.56818732,  0.10245245,  0.81649658]])
'''

U
'''
array([[-0.69366543,  0.59343205, -0.40824829],
       [-0.4427092 , -0.79833696, -0.40824829],
       [-0.56818732, -0.10245245,  0.81649658]])
'''

D = np.zeros((3, 2))
np.fill_diagonal(D, sing_values)

D
'''
array([[10.25142677,  0.        ],
       [ 0.        ,  2.62835484],
       [ 0.        ,  0.        ]])
'''

np.dot(np.dot(U,D),VT)
'''
array([[7., 2.],
       [3., 4.],
       [5., 3.]])
'''

 

🩴축소형 - 예시의 경우 3x3의 U에서 3x2의 X를 표현하기 위해 단순히 3x2의 U의 정보만으로 충분히 표현할 수 있음을 알 수 있다.

($\Sigma$의 맨 마지막 행이 모두 0으로 이루어져 있으므로). numpy svd()의 인자 full_matrices를 False로 설정하면 U의 차원이 축소되고, 축소된 U를 기존의 singular_values, $V^T$와 곱해도 결과는 동일하게 나옴을 확인할 수 있다.

U1,sing_values1,VT1=np.linalg.svd(X, full_matrices=False)

U1 #U 3x3
'''
array([[-0.69366543,  0.59343205],
       [-0.4427092 , -0.79833696],
       [-0.56818732, -0.10245245]])
'''

sing_values1 #array([10.25142677,  2.62835484])

VT1
'''
array([[-0.88033817, -0.47434662],
       [ 0.47434662, -0.88033817]])
'''

D1 = np.zeros((2, 2))
np.fill_diagonal(D1, sing_values1)

np.dot(np.dot(U1,D1),VT1)

'''
array([[7., 2.],
       [3., 4.],
       [5., 3.]])
'''

---

* 출처1) SVD by Gilbert Strang (MIT) https://youtu.be/mBcLRGuAFUk

* 출처2) SVD (mathematical overview) by Steve Brunton https://youtu.be/nbBvuuNVfco