Singulardecomposition

이번 장에서는 특잇값분해 singulardecomposition을 알아본다.

앞서 고윳값분해에서는 square matrix에서만 정의될 수 있었고, 항상 존재하진 않았다. 또한 주어진 n x n 의 고윳값들이 linear independent해야 정의가 됐었다. 하지만 특잇값분해는 어떠한 형태의 matrix도 정의가능하고 항상 존재한다. SVD도 linear mapping과 연관지은 설명과, 직관적으로 어떤작용을 하는지 알아보자.

 

 

 $A = U \Sigma V^{T}$ 행렬곱으로 표현이 된다. matrix $\Sigma$의 $\sigma_{i}$ 값들을 singular value라고 한다. $\Sigma$ 행렬이 직사각행렬이기 때문에 $ii$를 벗어난 값들(off diagonal term)은 전부 0이다. 

각각의 $U$, $\Sigma$, $V^{T}$의 shape을 잘 기억하자. 또한 $U, V$는 모두 $orthogonal matrix$임을 기억하자.

 $\Sigma$는 주어진 matrix$A$와 size가 일치한다. 이말은 (4.65), (4.66)을 보면 쉽게 이해할 수 있다.

m > n

n > m

 

SVD도 기하학적으로 살펴보자. 고윳값분해에서의 그림과 거의 유사한 것을 확인할 수 있다. 차이점은 고윳분해는 같은 vector space 상에서 transformation이 수행되는 것이고, SVD는 서로 다른 demension을 가지는 vector space사이의 transformation을 설명해준다. 

 아래의 그림을 토대로 $A$가 $A \in \mathbb{R}^{3 \times 2}$ 일 때, 맵핑함수 $\Phi : \mathbb{R}^{2} \rightarrow \mathbb{R}^{3}$ 이라 가정해보자. 우리는 $A$를  $A = U \Sigma V^{T}$로 decomposition 할 수 있다는거였다. shape으로 보면 (3x2) = (3x3)(3x2)(2x2) 처럼 된다. $V$는 $orthogonal$ matrix이니까 $V^{T}$는 $V^{-1}$와 같아진다. $V$는 (2x2)행렬이기 때문에 2dim 상에서 basis 를 바꿔주는 역할을 수행하게 된다. 그림 왼쪽 아래처럼 basis가 바뀌었다. 그다음 $\Sigma$를 곱해서 2dim에서 3dim으로 맵핑이 되는거고 여전히 이 벡터들은 2dim의 subspace에 존재하고 있음. $U$는 3dim space에서 basis를 바꿔주는 역할을 한다. $A$라는 맵핑을 돌아서 수행.

 

 

조금 더 이해를 돕기 위해 예제를 보도록 하자. $A$ 가 $U \Sigma V^{T}$로 아래와 같이 나타내질 수 있다고 하자.

 아래의 그림은 위의 그림을 떠올리면 basis가 바뀌고, 다른 dimension space에 매핑하고 다시 basis 를 바꾸는 모습을 직관적으로 파악할 수 있다.

 

 

SVD를 증명과정에서 대한 키포인트만 짚고 넘어가자.

먼저 SVD를 증명할 때, 고윳값분해 개념을 정확히 알고 있어야 한다. 그간의 여러 이론으로 증명이 된다. $A$라는 nxn 행렬이 있다고 가정한다면, 이 $A$를 $U \Sigma V^{T}$로 docomposition하고자 한다. SVD를 증명하기 위해 고윳값분해를 이용하는데, 고윳값분해는 특별한 경우에만 성립가능한데, 그 경우는 n x n 인 squre matrix가 n개의 eigenvetor를 가져야한다고 했다. 그리고 spectral theorem이라는 이론에서 symmetrix한 행렬은 항상 eigenvector로 구성되는 orthonomal basis를 항상 가진다고 했었고, 또 임의의 $A$같은 행렬을 $AA^{T}$하면 항상 symmetric하고 positive semidefinite하다고 했다. 이러한 사실을 조합하면 직사각행렬인 $A$같은 행렬을 전치한것과 곱하면 항상 symmetrix하게 만들 수 있다는 것이다. 이 symmetric한 행렬은 eigenvector들이 항상 orthonormal하다고 했었고 결과적으로 diagonalizing이 가능하다는 것이고 고윳값분해가 가능해진다는 것이다.

 $AA^{T}$를 보면 (n x n)행렬이 되고, $AA^{T} = PDP^{T}$로 decomposition이 된다는 것이다. 여기서 우리가 SVD를 한다고 하면은 $AA^{T}$ 자체는 $(U \Sigma V^{T})^{T}(U \Sigma V^{T})$와 같다고 할 수 있다. 이는 (4.72)와 같이 나타낼 수 있다. 그리고 SVD에서 $V$,$U$ 는 orthonormal하다고 했기 때문에 $U^{T}U$부분이 $I$ mairix가 되어 사라지게 된다.

고윳값분해에서는 $D$부분이 diagonal matrix가 되는데 $\Sigma^{T}\Sigma$는 마찬가지로 diagonal matrix가 될 것이고, 우리가 알 수 있는 건 (4.74), (4.75)와 같이 특잇값 제곱인 $\sigma_{i}^{2}$이 $\lambda_{i}$와 같은 것이 되겠고, 결국 SVD의 $V$는 $A{^T}A$의 고윳값을 구하면 된다라는 것을 알 수 있다.

지금까지 $A{T}A$에 대한 고윳값분해를 토대로 고윳값을 구하면 SVD 식과 비교하여 $V$ 구해봤는데, $AA^{T}$를 통해서 마찬가지로 수행하면 $U$도 똑같이 구할 수 있다.

 

 

이제 예제 4.13을 통해서 SVD를 구해보자.

 

먼저 오른쪽 특이벡터행렬을 구하자. $A^{T}A$의 고윳값을 구해서 $V$를 구한다.

아래와 같이 고윳값분해를 통해서 $P$가 곧 $V$니까 $V$를 쉽게 구할 수 있게 된다..

 

왼쪽 특이벡터행렬인 그리고 $U$는 $AA^{T}$의 고윳값을 구하면 아래와 같이 나오게 된다.

 

SVD의 가운데 특잇값행렬인 $Sigma$는 $A$ 행렬과 size가 같아야 한다. 즉, 증명과정에서 보았던 고윳값의 squreroot값을 가지고 적절히 만들어주면 아래와 같이 된다.

 

 

domain에서 basis를 바꾸고, 새롭게 바뀐 basis에 대해 독립적으로 scaling이 되고 codomain에서 basis를 바꾼다. => 고윳값분해와 특잇값분해의 공통점. 차이점은 domain과 codomain의 dimensionality가 같느냐.