Linear Algebra - UNIT III - 08 Singular Value Decomposition and PCA

Learn Differential Equations: SVD

Linear Algebra: Lec. 29

SVD summary pdf

SVD Film

다크프로그래머 블로그

---

Singular Value Decomposition

강의에서 다루는 마지막이자 최고의 factorization이다!

What is Singular Value Decomposition?

$$A= U \Sigma V^T$$

우변은 각각 Orthogonal, Diagonal, Orthogonal Matrix로 구성된다.

Orthogonal과 Diagonal 둘다 정말 좋은 특성을 지니고 있다.

Orthogonal은 역행렬이 쉽게 구해진다. Diagonal은 제곱계산에 대해 간단하다. (+Symmetric한 행렬은 eigenvector가 orthogonal하다.)

A는 어떤 행렬이어도 상관없다. 어떠한 A라도 SVD를 가지고 있다.

새로운 점은 우리가 서로 다른 두개의 orthogonal matrices가 필요하다는 것이다.

이 분해는 이 코스의 모든 것을 함축한다.

쉽게 말하면 Eigendecomposition의 일반화라고 볼 수 있을 것 같다.

Symmetric Positive Definitive

먼저 불러올 것은 PD이다.

$$A=Q \Lambda Q^T$$ $$A=S \Lambda S^{-1}$$

Symmetric한 행렬은 Eigenvector가 Orthogonal하다. 위에서 일반적인 행렬인 S가 Q가 된 것을 볼 수 있다.

그리고 PD에서 일반적인 $\Lambda$가 Positive $\Lambda$가 된 것이다.

$$A=Q \Lambda Q^T$$

행렬이 Symmetric Positive Definite일 경우 위 식은 Singular Value Decomposition을 한 것과 같다.
Symmetric Positive Definite에서는 U나 V가 필요가 없다. 그냥 하나의 Orthogonal matrix면 충분하다.

그러나 다음에는 해당하지 않는다.

$$A=S \Lambda S^{-1}$$

일반적으로 S 행렬은 orthogonal하지 않다. 그래서 이는 신경쓰지 않겠다.

Orthogonal x Diagonal x Orthogonal

인 경우를 생각하는것이 편하다.

이게 어떤 의미를 가지는지, 어디서 온것인지 알아보자.

How it works

우린 행렬 A를 row space $R^n$의 벡터 $v_1$을 column space $R^m$의 벡터

$$u_1 = A v_1$$

으로 보내는 것으로 생각할 수 있다.

SVD는 row space에 대한 orthogonal basis를 column space에 대한 orthogonal basis로 변환하는 것에서 출발한다.
$u$를 단위벡터로 만들어 orthonormal하게 표현하기 위해 다음처럼 $\sigma$를 추가하여 스케일링 해준다.

$$Av_i = \sigma_i u_i$$

Row space에 대한 orthonormal basis를 찾는 것은 어렵지 않은 일이다 - Gram Schmidt process를 이용한다면.
그러나 그 orthogonal basis를 또 다른 공간의 orthogonal basis를 보낸다고 그것이 orthogonal이라는 보장이 없다.
그렇기 때문에 특별한 setup이 필요하다.

$A,A^T$의 Nullspace상에 있는 벡터들에 대해 걱정할지도 모르지만 상관없다.
$\Sigma$의 대각성분 $\sigma_{r+1},\sigma_{r+2},...\sigma_{n}$는 0으로 나타날 것이기 때문이다.
그러므로 표시하지 않아도 된다.

Matrix language

이를 행렬식으로 표현해보자.

앞으로 $\Lambda$대신에 $\Sigma$라고 부를것이다.

$$A \begin{bmatrix} v_1 & v_2 & \cdots & v_r \end{bmatrix} = \begin{bmatrix} \sigma_1 u_1 & \sigma_2u_2 & \cdots & \sigma_ru_r \end{bmatrix} \\\\ = \begin{bmatrix} u_1 & u_2 & \cdots & u_r \end{bmatrix} \begin{bmatrix} \sigma_1 & & & \\ & \sigma_2 & & \\ & & \ddots & \\ & & & \sigma_r \\ \end{bmatrix}$$

$\sigma$는 단위벡터 $u$를 스케일링하기 위한 것이다.

문제의 핵심은 행렬 A에 대해 column space상의 orthonormal basis $u_1,u_2,...u_r$로 변환 되는 row space상의 orthonormal basis $v_1,v_2,...v_r$를 찾는 것이다.

Null space까지 포함해서 이를 다시 정리하면

$$AV=U \Sigma$$

가 된다.

Orthonormal basis $V$ in row space, orthonormal basis $U$ in column space. 이 둘을 이용하여 행렬을 대각화하였다.
행렬 A가 대각화된 행렬로 표현된 것이다.

일반적으로는 U와 V는 서로 다른 행렬이다.
그러나 Positive definite의 경우는

$$AQ=Q \Sigma$$

인 경우다.
V와 U가 똑같이 Q인 것이다.
즉, 같은 basis를 row 와 column space에 사용할 수 있다.

Calculation

$$A = \begin{bmatrix} 4 & 4 \\ -3 & 3 \end{bmatrix}$$

이는 invertible하고 rank 2를 가진다.
그러나 symmetric하지 않아서 eigenvector가 orthogonal하지 않아 그대로 이용할 수 없다.

row space $R^2$에서 $v_1,v_2$를 찾고, column space $R^2$에서 $u_1,u_2$를 찾아보자.
그리고 $\sigma_1 \gt 0,\sigma_2 \gt 0$를 찾아 $v_i,u_i$을 orthonormal하게 만들자.

다음에 대한 Orthonormal 행렬 V,U, Diagonal 행렬 $\Sigma$를 찾아보자.

$$AV=U \Sigma$$

$V$가 orthogonal하므로 $V^{-1}=V^T$ 로 양변에 곱한다.

$$A=U \Sigma V^T$$

$U,V$와 $\Sigma$ 를 동시에 풀기보단, 양변에 $A^T=V \Sigma^T U^T$를 곱하여 U를 없애자:

$$A^TA = V \Sigma U^{-1} U \Sigma V^T \\\\ =V \Sigma^2 V^T \\\\ = V \begin{bmatrix} \sigma_1^2 & & & \\ & \sigma_2^2 & & \\ & & \ddots & \\ & & & \sigma_n^2 \\ \end{bmatrix} V^T$$

$A^TA$는 Symmetric하며, positive definite 혹은 semidefinite이다.

이것은 $Q \Lambda Q^T$형태라는 것을 알 수 있다.
그러므로 행렬 $A^TA$를 대각화함으로써 V를 찾을 수 있다.
$V$의 column들은 $A^TA$의 eigenvector들이고, positive definite이기 때문에 $\sigma_i^2$는 양수인 eigenvalue들이다.($\sigma_i$는 양수인 $\lambda_i$의 제곱근을 선택하면 된다.)

$U$를 얻기 위해서 우리는 $AA^T$에 대해 같은 것을 하면된다.

SVD example

$$A= \begin{bmatrix} 4 & 4 \\ -3 & 3 \end{bmatrix}$$

다시 돌아와서 계산해보자.

$$A^TA = \begin{bmatrix} 25 & 7 \\ 7 & 25 \end{bmatrix}$$

Eigenvector는 $v_i$가 될것이고, eigenvalue는 $\sigma_i$가 될것이다.

$$v_1= \begin{bmatrix} 1/\sqrt{2}\\ 1/\sqrt{2} \end{bmatrix} , v_2= \begin{bmatrix} 1/\sqrt{2}\\ -1/\sqrt{2} \end{bmatrix}$$ $$\sigma_1^2=32,\sigma_2^2=18$$ $$A=U \Sigma V^T$$ $$\begin{bmatrix} 4 & 4\\ -3 & 3 \end{bmatrix} = \begin{bmatrix} \\ \end{bmatrix} \begin{bmatrix} 4 \sqrt{2} & 0\\ 0 & 3 \sqrt{2} \end{bmatrix} \begin{bmatrix} 1/\sqrt{2} & 1/\sqrt{2}\\ 1/\sqrt{2} & -1/\sqrt{2} \end{bmatrix}$$

이를 통해 U를 풀 수 있으나, 연습을 위해 $AA^T$로도 해보면 좋다.

$A^TA$의 eigenvalue와 $AA^T$의 eigenvalue는 같다.

Example with a nullspace

$$A= \begin{bmatrix} 4 & 3 \\ 8 & 6 \end{bmatrix}$$

---

Principle Component Analysis

Symmetric한 A에 대해 Eigendecomposition을 하면,

$$A=S \Lambda S^T$$

S는 orthonormal하다.

개인적인 해석은 이는 otrhonormal eigenvector인 S의 basis로 변환하고, $\Lambda$의 eigenvalue만큼 스케일링 해준뒤, 다시 원래대로 S의 역변환을 해주는 느낌인것 같다. 물론 곱해지는 순서는 그 반대긴하지만.

eigenvalue가 제일 작은 성분을 0으로 만들어버리면, 원래의 벡터와 오차가 크지 않다.

eigenvalue만큼 변형을 하게 되는데, 그 변형의 정도가 제일 작은 것을 0으로 만들어도 그럭저럭 원래와 비슷하게 재구성할 수 있다는 것이다.

이러한 특징을 이용하면 Rank가 더 낮은 Low Dimensional Representation을 얻을 수 있다.

낮은 차원의 hyperplane으로 투영되는 것이다.

Covariance, Covariance Matrix

$$cov(X,Y)=\sigma_{X,Y}^2 = E(XY)- \mu_X \mu_Y$$ $$=E((X-\mu_X)(Y-\mu_Y))=\frac{1}{n-1}\sum_{i=1}^{n} (x_i - \mu_X)(y_i - \mu_Y)$$

n개의 데이터에 대해 전부 평균.

Cov는 Symmetric하다. 이는 그 정의에 의해 증명된다.

원형이라면 대각행령의 대각 원소가 모두 같다.

대각 행렬의 대각 성분이 서로 다르다면 한쪽으로 늘어져있다. 타원체(ellipsoid) 모양일듯?

대각 행렬이 아니고 일반적인 행렬이라면 회전한 타원체 모양.

평균과 분산을 정규분포로 모델링 했을 때 위처럼 보이게 되는듯. 물론 수가 늘어나면 CLT에 의해 마찬가지가 되겠지만.

k차원인 n개의 데이터에 대해 각각의 1부터 k까지의 축의 데이터의 평균을 0이라고 할 때, (Normalize 하였을 때?) 이 공분산 행렬을 구하는 것은 쉬워진다.

평균이 0이라 쉽게 연산할 수 있다.

이제 이 공분산 행렬을 차원 축소시켜 투영할 것이다.

평행이동 하는 것은 간단한 일이다.

그러나 회전이 어렵다. 얼마나 회전시켜야할까?

공분산 행렬이 대각화될 때 까지 회전하는 것이다.

(길버트 교수님이 Spectral Theorem 설명할 때 어떤 각도에서 보면 ‘순수한 성분’이 보인다는 뜻이 이것이다.)

이를 수식화하면, 회전 전 행렬을 X, 회전 후 행렬을 Y라고 했을 때

$$Y=PX$$

인 회전행렬 $P$를 얻겠다는 것이다.

$P=S^T$ 로 두면 $\Lambda$만 쏙 빠지고 나머지가 없어진다.

$X^TX$이 공분산 행렬이라는 것은 매우 좋다. Symmetric해서 eigenvector가 전부 직교하기 때문이다. 그런데 공분산이라는 의미까지 가진다..

eigenvalue가 작은 것을 삭제하면 차원축소가 된다.