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}\Sigma\mathsf{V}^\mathsf{T}$$

 

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

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

$$ \Sigma = \mathsf{m} \times \mathsf{n} \qquad (\mathsf{rectangular\  diagonal \  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들 입니다.

 

$$ \Sigma = \begin{pmatrix} \sigma_{1} & 0 & 0 \\ 0 & \sigma_{2} & 0 \\ 0 & 0 & \sigma_{3} \\ 0 & 0 & 0\end{pmatrix}  \ (\mathsf{m} > \mathsf{n}) \qquad \Sigma = \begin{pmatrix} \sigma_{1} & 0 & 0 & 0 \\ 0 & \sigma_{2} & 0 & 0\\ 0 & 0 & \sigma_{3} & 0\end{pmatrix} \ (\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(A^TA)v = \lambda Av}$$

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

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

 

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

$$ \mathsf{ \sigma_1^2, \; \sigma_2^2, \;..., \; \sigma_s^2 \quad (s = \min(m,n) )}$$

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

$$ \mathsf{ Square root \; \rightarrow \; \sigma_i \ge 0, \; i = 1,2,3,...,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}\Sigma \mathsf{V}^\mathsf{T}$$

 

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

 

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

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

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

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

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

 

조금 더 생각을 해 봅시다.

$$ \mathsf{ A = U\Sigma V^T \quad \rightarrow \quad AV = U\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