Singular value decomposition(SVD, 특이값 분해)

저번 글로 초석을 다져놨으니 오늘 할 것은 SVD입니다. SVD의 개념과 계산 방법, 등위주로 알아보도록합시다.

(latex는 처음써보는데 모바일 버전에서는 안보이는것 같아요, 보신다면 데스크톱 버전으로 봐 주세요 ㅎㅎ)

 

Singular value decomposition

 

SVD역시 앞선 eigen decomposition과 같이 행렬을 대각화하는 방법중 하나입니다. 그럼 eigen decomposition과 무엇이 다르길래 이 방법을 쓰는 것일까요 . SVD를 쓰는 이유 n x n 행렬뿐만아니라 일반적인 m x n 행렬에 대해서도 대각화가 가능하기 때문입니다.

 

m x n 행렬 A에 대한 특이값분해는 다음과같이 정의되어집니다.

 

$$\mathsf{A}=\mathsf{U}\mathrm{\Sigma }{\mathsf{V}}^{\mathsf{T}}$$

 

$$\mathsf{U}=\mathsf{m}\times \mathsf{m}(\mathsf{orthogonal}\mathsf{matrix})$$

$$\mathsf{V}=\mathsf{n}\times \mathsf{n}(\mathsf{orthogonal}\mathsf{matrix})$$

$$\mathrm{\Sigma }=\mathsf{m}\times \mathsf{n}(\mathsf{rectangular}\mathsf{diagonal}\mathsf{matrix})$$

 

• 정확히는 Unitary matrix이지만 실수(R)에서만 다루기로 합시다. 따라서 orthogonal matrix로 취급하겠습니다. Orthogonal matrix(직교행렬)의 성질은 위키님이 설명해 줄 것입니다.

 

U의 열벡터(column vector)는 A의 left singular vector들 입니다.  left singular vector는 AA^T의 eigen vector로 정의되어집니다.

그렇다면 V의 열 벡터들도 생각해봅시다. 이것은 A의 right singular vector들인데, 이것은 A^TA의 eigen vector들로 정의되어있습니다.

Σ는 singular value들로 이루어진 직사각 대각행렬입니다. 이 singular value들은 AA^T 와 A^TA의 공통 eigen value들의 square root들 입니다.

 

$$\mathrm{\Sigma }=\left(\begin{array}{ccc}{\sigma }_1& 0& 0\\ 0& {\sigma }_2& 0\\ 0& 0& {\sigma }_3\\ 0& 0& 0\end{array}\right)(\mathsf{m}>\mathsf{n})\mathrm{\Sigma }=\left(\begin{array}{cccc}{\sigma }_1& 0& 0& 0\\ 0& {\sigma }_2& 0& 0\\ 0& 0& {\sigma }_3& 0\end{array}\right)(\mathsf{m}<\mathsf{n})$$

 

위의 왼쪽은 m>n 인경우이고 오른쪽은 m<n인 경우입니다. (latex를 처음 써 보아서 .. 간략하게 표현한 것입니다. )

 

여기서 A^TA와 AA^T는 모두 symemtric matrix입니다(transpose 해 보면 쉽게 알 수있습니다.). 따라서 모두 eigen decomposition이 가능하게되고 orthogonal matrix로 대각화가 가능합니다. (orthogonal인 증명은 여기에서 볼 수 있습니다.) 그에따라서 항상 특이값분해가 가능해지게 됩니다.

 

다음은 아래의 성질들을 보고 이야기 하겠습니다.

 

먼저 A^TA의 eigenvalue : λ, eigenvector : v 라고 합시다.

 

$${\mathsf{A}}^{\mathsf{T}}\mathsf{A}\mathsf{v}=\lambda \mathsf{v}$$

$${\mathsf{v}}^{\mathsf{T}}{\mathsf{A}}^{\mathsf{T}}\mathsf{A}\mathsf{v}=\lambda {\mathsf{v}}^{\mathsf{T}}\mathsf{v}$$

$$\parallel \mathsf{A}\mathsf{v}{\parallel }^2=\lambda \parallel \mathsf{v}{\parallel }^2-(1)$$

$$\therefore \lambda \ge 0$$

 

위의 (1)번 식은 일반적인 vector norm (유클리드 노름)의 정의에의해서 저렇게 표현되죠.

어찌됐든, A^TA의 eigenvalue는 항상 0이상의 실수를 가지게 됩니다. 따라서 위에서 singular value들은 A^TA와 AA^T의 공통 eigen value 들의 square root라고 한 부분을 만족시키게 됩니다. 0이상이므로 square root를 씌울 수 있죠!

 

다음으로는이제 A^TA와 AA^T가 공통 eigen value를 가지는가가 의문일것입니다. 그래서 그것을 보여주기위하여 다음을 보도록 합시다. 마찬가지로, A^TA의 0 아닌 eigen value: λ, eigen vector : v라고 합시다.

 

$$({\mathsf{A}}^{\mathsf{T}}\mathsf{A})\mathsf{v}=\lambda \mathsf{v}$$

$$\mathsf{A}\mathsf{(}{\mathsf{A}}^{\mathsf{TA}}\mathsf{)}\mathsf{v}\mathsf{=}\lambda \mathsf{Av}$$

$${\mathsf{AA}}^{\mathsf{T}}\mathsf{(}\mathsf{Av}\mathsf{)}\mathsf{=}\lambda \mathsf{(}\mathsf{Av}\mathsf{)}$$

$$\therefore \lambda \mathsf{is}\mathsf{eigen}\mathsf{value}\mathsf{of}{\mathsf{AA}}^{\mathsf{T}}$$

 

따라서 AA^T 와 A^TA는 공통의 eigen value를 갖는다는것을 알 수 있습니다. 그렇다면 공통의 eigen value를 아래와 같이 두겠습니다.

$${\sigma }_{\mathsf{1}}^{\mathsf{2}}\mathsf{,}{\sigma }_{\mathsf{2}}^{\mathsf{2}}\mathsf{,}\mathsf{.}\mathsf{.}\mathsf{.}\mathsf{,}{\sigma }_{\mathsf{s}}^{\mathsf{2}}\mathsf{(}\mathsf{s}\mathsf{=}min\mathsf{(}\mathsf{m}\mathsf{,}\mathsf{n}\mathsf{)}\mathsf{)}$$

그럼 여기다가 squre root를 씌우게 되면 정의에 의해서 A의  singular value들이 되는것 입니다.

$$\mathsf{Square}\mathsf{root}\to {\sigma }_{\mathsf{i}}\ge \mathsf{0}\mathsf{,}\mathsf{i}\mathsf{=}\mathsf{1}\mathsf{,}\mathsf{2}\mathsf{,}\mathsf{3}\mathsf{,}\mathsf{.}\mathsf{.}\mathsf{.}\mathsf{,}\mathsf{s}$$

 

위처럼 σi 들을 대각원소로하는 m x n 직사각 대각행렬이 Σ 가 됩니다.

 

이까지하면 SVD는 끝이 납니다. U와 V는 각각의 eigenvector들을 구해주면 되는것이니까요.

 

이제 이 SVD의 의미를 살펴볼까요 .

 

SVD의 기하학적 의미

 

먼저 행렬 A를 singular value decomposition하게 되면 orthogonal matrix와 직사각 대각행렬(diagonal matrix)로 분해가 됩니다.

이 두가지의 matrix의 특징을 간단하게 알아봅시다.

기본적으로  orthogonal matrix는 rotation과 reflection을 나타냅니다. 즉 isometry(등거리 변환, 다시말해서 scale 변화는 줄 수 없습니다.) 로써의 역할을 하는것입니다.

diagonal matrix는 반대로 scale변화에만 영향을 주게됩니다.

 

$$\mathsf{A}=\mathsf{U}\mathrm{\Sigma }{\mathsf{V}}^{\mathsf{T}}$$

 

다시 처음으로 돌아가서 위의 식을 살펴봅시다.

 

$$\mathsf{Ax}\mathsf{=}\mathsf{(}\mathsf{U}\mathsf{\Sigma }{\mathsf{V}}^{\mathsf{T}}\mathsf{)}\mathsf{x}$$

x에 대해서 다음과같은 변환이 이루어진다고할때 그 의미를 직관적으로 살펴보게되면,

1. x를 VT에 의해 회전시킵니다.
2. Σ를 통한 Scale 변환
3. U로 회전 변환을 시킵니다.

https://en.wikipedia.org/wiki/Singular_value_decomposition

위키에서 가져온 그림이라 기호가 약간 다르긴한데, M만 A로 바꿔주시면 됩니다. 위의 그림에서 보듯이 V는 회전 , Σ는 Scale변환, U는 다시 회전의 역할을 하는것을 볼 수 있습니다.

 

조금 더 생각을 해 봅시다.

$$\mathsf{A}\mathsf{=}\mathsf{U}\mathsf{\Sigma }{\mathsf{V}}^{\mathsf{T}}\to \mathsf{AV}\mathsf{=}\mathsf{U}\mathsf{\Sigma }$$

 

위의 오른쪽 식 처럼생각한다면, 'V의 orthogonal한 벡터들을 A라는 선형변환을 통해 변환하였을때, 크기는 Σ만큼 바뀌는 다시 orthogonal한 벡터들 U를 찾을 수 있다' 라는 말로 해석 할 수 있겠습니다.(어렵다..어려워 ..)

 

여담으로 eigen value와 singular value는 무엇이 다를까요?

 

eigen value는 변환에의해 방향이 변하지 않는 vector(eigen vector)에 대한 Scale factor이고,

singular value는 변환자체의 Scale factor로 볼 수 있습니다.

 

 

Reference

[1]https://darkpgmr.tistory.com/106?category=460967

[2]https://rfriend.tistory.com/185

[3]https://en.wikipedia.org/wiki/Singular_value_decomposition