Singular value decomposition (SVD)

Singular value decomposition

Intuition

정방형(square) 매트릭스는 eigenvector 및 eigenvalues를 통해 다음과 같이 대각행렬로 분해가 가능합니다. 이를 eigen decomposition이라고 합니다.

이는 지난 포스트 링크를 참고 부탁드립니다.

https://velog.io/@kimgeonhee317/Eigenvectors-and-Eigenvalues

그렇다면 SVD는 무엇일까요?
이는 정방형 벡터가 아닌 어떠한 형태의 m * n형태의 매트릭스라도 유연하게 분해하기 위해서 고안되었습니다.

수식은 굉장히 비슷합니다.
m * n 의 매트릭스 $A$가 있다고 가정하면 다음과 같은 수식이 나옵니다.

차례대로 살펴봅시다.

1. $U$는 m * m 직교행렬(Orthogonal Matrix) 입니다.
   이는 $U$를 이루는 각각의 컬럼벡터 $\{u_1, u_2, ..., u_m\}$ 가 전부 상호 직교, 즉 내적이 0이 되는 것을 의미합니다.
   참고로 직교행렬은 트랜스포즈한 행렬과 곱해지면 항등행렬 $I$가 됩니다.
   그리고 트랜스포즈와 인버스의 결과가 같습니다.

   $UU^T = I\\ U^T = U^{-1}$

2. $\Sigma$ 는 m * n 대각행렬(Diagonal Matrix)입니다.
   각 대각행렬의 대각성분들은 $\{\sigma_1, \sigma_2, ...\}$로 표시됩니다.
   이를 성분들을 singler values라고 합니다.
   m과 n의 크기 대소에 따라 가능한 만큼 singler values를 채우는 형태입니다.

3. $V$역시 n * n 직교행렬(Orthogonal Matrix) 입니다.
   대신 transpose를 취했으므로 위에서 부터 $\{v_1, v_2, ..., v_n\}$ 이 쌓여있는 형태라고 보면 됩니다.

각 행렬의 느낌을 살펴보면, $U$는 회전(rotation) $\Lambda$은 확장(stretching) $V^T$은 다시 회전(rotation)입니다.

이제 수식의 직관적 의미를 파악해봅시다.
SVD가 말하고자 하는 바는 이렇습니다.

직교하는 여러 벡터들의 집합을 선형변환하여도 여전히 직교하는가?

먼저 $V$는 선형변환 전의 직교하는 여러 열벡터들의 집합으로 이해해 봅시다.
각 성분(열벡터)들($\{v_1, v_2, ..., v_n\}$)들은 동 매트릭스가 orthogonal하기 때문에 자명하게 서로 직교합니다.

이 열벡터들을 특정 매트릭스 $A$를 통해 선형변환 시켰다고 가정해봅시다.

이럴 경우, 스케일은 달라질지언정 그대로 서로 직교하는 열벡터들의 집합으로 남을 수 있을까요? 이런 경우는 반드시 unique하게 존재할 수 밖에 없습니다.
이런 새로운 직교 열벡터들의 매트릭스를 $U$라 합시다. $\{u_1, u_2, ..., u_m\}$의 형태라고 가정하겠습니다.
그리고 변환된 스케일만큼 각 $\{u_1, u_2, ..., u_m\}$에 곱해줄 즉 각 singular values $\{\sigma_1, \sigma_2, ...\}$은 대각행렬 $\Sigma$로 표기됩니다.
이를 수식으로 나타내면 다음과 같죠.

그리고 다음과 같이 바꿔줄 수 있습니다. ($V^{-1} = V^T$)

Illustration

위 수식을 바탕으로 $AA^T$를 계산해봅시다.
다음과 같이 표현될 수 있을 겁니다.

$V^T V = I$ 이므로 다음과 같이 계산됩니다.

계산된 $AA^T$는 m * m 정방형이므로 이렇게 바꾸고 보니 eigen decomposition(diagonalization)과 모양이 유사하네요?
그러면 $U$와 $U^T$는 $AA^T$의 eigen vector로 이루어진 매트릭스라고 할 수 있고 $\Sigma \Sigma^T$는 그 사이의 eigen values로 이루어진 대각행렬이 될겁니다. 대각행렬은 transpose 해도 같은 값이므로 $\Sigma \Sigma^T$은 $\Sigma^2$로 표현할 수 있습니다. 그리고 $U$는 orthogonal하므로 트랜스포즈한 결과와 인버스의 결과가 같습니다.
다음과 같이 살짝 바꿔 표현할 수 있겠네요

즉 이제 평범한 eigen decomposition 모든 값을 찾아낼 수 있습니다.
$U$ 는 $AA^T$의 eigenvector들의 집합이 될 것이고, eigenvalues들은 $\Sigma^2$에 매칭될 겁니다.

반대도 가능합니다.

계산하는 방식은 같죠.

Representation

표현 방법에 대해 조금 더 살펴봅시다.
먼저 알아야할 점은 SVD으로 분해된 매트릭스가 어떤 식으로 계산되는 지입니다.

매트릭스의 형태를 보면 $A$는 $m * n$, $U$는 $m * m$, $\Sigma$는 다시 $m * n$, $V^T$는 $n * n$입니다.
근데 생각을 해보면, 대각행렬은 $m * n$이기 때문에 $m$과 $n$의 크기의 차이로 $\Sigma$에서 어쩔수 없이 0으로 패딩되는 부분이 생기죠. 이 부분에 해당되는 $U$와 $V^T$는 있으나 마나합니다. 즉 $m$과 $n$중 작은 수만 고려해서 계산해도 됩니다.

$p = min(m, n)$ 을 가정해봅시다. 그리고 매트릭스를 풀어보면 다음과 같습니다.

보시면 식의 하나하나의 단위는 $U$이 $n$번째 column, $\Sigma$의 $n$번째 row(col), $V^T$의 n번째 row가 됩니다.

PCA

마지막으로 SVD가 어떻게 쓰이는지 알아봅시다. 가장 대표적으로 PCA(Principal Component Analysis)에 쓰입니다.

우선 표현 방법에 약간의 정교함을 더해봅시다.
통상 대각성분(singler values)들은 큰 수부터 내림차순으로 쓰곤 합니다. 그럼 그와 매칭되는 짝꿍들인 $u_i$ 와 $v_i$의 순서들도 전부 바뀌겠죠? 그래서 대각성분의 순서는 중요하지 않습니다.

그리고 매트릭스 $U$와 $V^T$는 orthogonal한데 각 크기 scale로 나누어 orthonomal 매트릭스로 보통 변환해놓습니다.

이렇게 해놓고 식을 다시 봅시다.

하나의 유닛 즉 성분은 다음과 같겠죠

이렇게 $A$는 여러 $p$개의 성분으로 나누어졌는데 singler value $\sigma$의 크기는 각 성분의 분산과 같게 됩니다. 근데 분산이 가장 큰 성분들을 추려내는 것이 PCA의 기본원리기 때문에 앞에서부터 주성분이 되게 됩니다.

Reference

[1] 공돌이의 수학정리노트, https://angeloyeo.github.io/2019/08/01/SVD.html
[2] MIT OpenCourseWare, https://www.youtube.com/watch?v=mBcLRGuAFUk