M4AI) Singular Value Decomposition

안녕 오랜만이야.. 널 또 공부하게 될 줄은 몰랐는데 말이야..

 

본격적으로 SVD를 복습하기에 앞서, 지난 시간에 훑어본 eigen-decomposition의 한계를 먼저 살펴보도록 합시다. 

• $n\times n$ 행렬밖에 안 됨
• symmetric한 애들한테 써먹을때 주로 유용함

SVD는 임의의 $m\times n$ 행렬에 대해 적용할 수 있다는 장점이 있어요. Let's take a look into this step-by-step!

 

*이건 영상 레퍼런스인데 너무 도움 많이 돼서 가져옴! https://www.youtube.com/watch?v=vSczTbgc8Rc

 

본격적으로 SVD를 살펴보기 전에 먼저 두 가지 사실을 짚고 넘어가봅시다.

• 행렬에 대해서는, 그냥 아무 숫자나 막 갖다 쓴 네모네모가 아닌 그 자체로 선형변환을 나타낸다는 생각을 견지하는 게 좋겠습니다! $m\times n$ 행렬은 rank가 꼭 $\max(m, n)$이 아니라는 데 주목해야겠습니다. 이것이 의미하는 바는, 이 행렬로 선형변환을 하면 차원이 늘어나거나 축소된다는 것이지요! 
• Diagonal matrix는 eigenvector가 서로 orthogonal하다는 특징을 최대한 이용하기 위해, $\mathbf{A}\mathbf{A}^\top$과 $\mathbf{A}^\top\mathbf{A}$이 symmetric matrices라는 점에 주목해볼 겁니다.

자 그러면 대망의 SVD는 어떻게 나타내느냐!

\begin{equation}\label{*}\tag{*} \mathbf{A} = \mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^\top\end{equation}

헐랭 별거 없죠..? 각각이 뭐냐면,

\begin{align}
\mathbf{U} &:\quad m\times m \text{ matrix of left singular vectors}\\
\boldsymbol{\Sigma} &: \quad m\times n \text{ rectangular diagonal matrix containing singular values} \\
\mathbf{V} &:\quad n\times n\text{ matrix of right singular vectors}
\end{align}

흠 오키 근데 대체

singular가 뭐야...? 가 나의 첫 번째 의문이었음

 

일단 $\boldsymbol{\Sigma}$가 제일 특이해 보이니 이것부터 설명하고 넘어가지요. Eigendecomposition에서 $\boldsymbol{\Lambda}$는 eigenvalue로 구성된 diagnoal matrix였잖아요? 그거의 $m\times n$ 버전이라고 생각하믄 됨!

이쯤에서 positive semidefinite의 개념을 소개해야 할 것 같은데요, 어떤 행렬 $\mathbf{M}$이 임의의 벡터 $\mathbf{x}\in\mathbb{R}^n$에 대해 $\mathbf{x}^\top\mathbf{M}\mathbf{x}\le0$을 만족하면, $\mathbf{M}$이 PSD라고 말합니다. 이런 행렬의 eigenvalue는 반드시 $\lambda\ge0$이라는 특징이 있어요.

다시 돌아가서ㅋㅋ  $\mathbf{A}\mathbf{A}^\top$과 $\mathbf{A}^\top\mathbf{A}$의 eigenvector로 구성된 행렬이 각각 $\mathbf{U}$와 $\mathbf{V}$라고 했자네? 이 아이들 각각의 eigenvalue를 내림차순으로 정리했을 때, 각각의 $\lambda_1,\: \cdots,\: \lambda_{\min(m,n)}$는 서로 동일하고 겹치지 않는 나머지 $\lambda_{\min(m,n)+1},\:\cdots,\:\lambda_{\max(m,n)}$는 모두 0이래요. 말이 좀 어려웠는데 그냥 non-zero eigenvalue의 개수가 $\text{rank}(\mathbf{A})$임! 증명은 제게 묻지 말기.. 암튼 이때 $\lambda_1,\: \cdots,\: \lambda_{\min(m,n)}$의 양의 제곱근을 바로 singular values라고 합니다! 얘네들로 구성된 행렬이 바로 $\boldsymbol{\Sigma}$인 것이고..

 

좋다 각각의 component가 무엇인지는 알아봤으니.. SVD가 의미하는 바가 무엇인지를 이제 알아봐야 하지 않겠음? 다시 식 $\ref{*}$로 돌아가서, 우리는 이제.. 오른쪽에서 왼쪽으로 식을 읽어나갈 겁니다ㅋㅋ

1. 일단 $\mathbf{V}$의 열들은 전부 orthogonal한 벡터잖아요? 여기에 전치를 취하면, orthogonal matrix의 특성으로 인해 $\mathbf{V}^{-1}$이 되고 이는 곧 standard basis, 즉 우리가 알고 있는 xy축으로의 회전(rotation)을 의미합니다. 있어보이게 말한거지 그냥 xy 축으로 align 시켜준단 뜻임! 원래의 공간을 휘릭 돌려준 상태임.
2. $\boldsymbol{\Sigma}$는 준-대각행렬?ㅋㅋ이라서 $\sigma_{ii}$ 항을 제외하고는 전부 0입니다. 이는 곧 차원의 축소 또는 확장을 의미하구요. 그러고 차원을 축소/확장해줍니다. 3차원=>2차원으로 가는 경우면 공간을 찌그러뜨린 셈이네요.
3. 마지막 $\mathbf{U}$도 eigenvector로 구성돼있고 orthogonal matrix니까 얘 또한 회전을 의미하겠죠? 그럼 회전 =>축소/확장=>회전 일케 되겠네요!

자세한 시각화는 영상 참고..

결국 SVD는 선형변환을 단계적으로 decompose했다~ 라고 이해해도 되겠구만!

 

Application

식을 이렇게 많이 쓰더라구요

\begin{align}\label{eq1}\tag{1}\mathbf{A} & = \mathbf{U}\boldsymbol{\Lambda}\mathbf{V}^\top \\
& = \sigma_1\mathbf{u}_1\mathbf{v}_1^\top + \sigma_2\mathbf{u}_2\mathbf{v}_2^\top + \cdots\end{align}

행렬을 singular value를 이용해 decompose한다고도 말할 수 있을 것 같은데, 제일 만만한 예시가 이미지 해상도 조절(?)인 듯합니다.

출처: 영상 캡쳐

hmmm~~ 아 그나저나 장발 예쁘다 두상이 예쁘니까 저게 되는 거겠지

이짓을 왜하나요~ 싶은데, 저렇게 $k$를 계속 올리다보면 데이터를 많이 압축한 상태긴 한데도 원본 이미지만큼이나 준수한 해상도를 가지는 경우가 있습니다. 그래서 데이터를 압축하는 데에 유용하게 활용된다고 하네용

 

 오늘은 여까지~