Singular Value Decomposition (SVD)

Source: Steve Brunton (Youtube)

https://www.youtube.com/watch?v=gXbThCXjZFM&list=RDCMUCm5mt-A4w61lknZ9lCsZtBw&index=5 

 

 

 

Singular Value Decomposition = 특이값 분해

 

- Data Reduction :  고차원 input data를 저차원으로 줄여주는 차원 축소 기법이다

- Data-driven generalization of Fourier transform : 푸리에 변환의 일반화 기법

 * 푸리에 변환이란? -> https://www.youtube.com/watch?v=Mc9PHZ3H36M 

- Facial Recognition, recommendation, 등에 사용됨

- 상업적 이용에 아주 중요한 개념임

- 왜 많이 사용되냐면, 가장 간단한 linear algebra 이기때문

- scalable

 

 

Mathematical Overview

---

 

m개의 이미지를 열벡터(tall skinny vector)로 reshape해서 행렬 X를 만들었다고 하자.

SVD는 이러한 행렬을 decompose 해서 3개의 다른 matrix로 분해하는 것이다.

U의 열벡터는 X의 열벡터와 같은 shape를 갖는다. 따라서 다시 eigen faces이미지로 reshape이 가능하다

u벡터들은 계층적으로 나열되어있다. (eigen faces)

 

U와 V는 unitary이다. 따라서 전치행렬의 성질을 만족한다.

Sigma 는 diagonal이다. non negative, hierarchical 이다. 따라서 sigma1은 sigma2보다 중요하다

따라서 원본 이미지를 표현하는 이 값들에서 첫번째 열벡터는 두번째 열벡터보다 중요하고, 다음 벡터또한 동일한 계층을 갖는다.

 

V transpose 는 mixtures of U. to make X 라고 생각하면 된다.

 

코드로 보면,

[U, sigma, V] = svd(X); 로 간단하게 표현할 수 있다.

 

 

정리)

U의 열벡턴는 X의 열벡터의 정보를 갖고 있고, 

V transpose는 X의 행벡터의 정보를 갖고 있으며,

sigma는 U와 V 벡터들의 중요도를 계층적으로 표현하기 위한 값들이다 (sigma1 > sigma2 > sigma3...)

 

 

 

 

Matrix Approximation

---

sigma x U의 열벡터 x V transpose의 행벡터 꼴로 나열한다.

원래 행렬의 곱은 행벡터 x 열벡터이지만,

여기서는 열벡터 x 행벡터 꼴로 만들고 각각의 절은 Rank 1이다.

 

* Rank 

- 행렬의 랭크는 행렬이 나타낼 수 있는 벡터 공간에서 기저의 개수를 의미

- 이 기저는 서로 독립인 행또는 열의 벡터의 개수에 의해서 결정

- 열과 행의 랭크는 서로 같은 값을 가지므로, 행렬의 랭크를 구할 때에는 한쪽의 랭크만 계산하면 됨

- 서로 선형 독립인 벡터가 몇 개가 되는지만 확인

 

X와 근사하는 가장 근사하는 값은 첫번째 절이라고 할 수 있고, 이후 2, 3, ..을 더하면서 X를 표현하게 된다.

 

 

Truncate at rank r

이그림에서 p를 r이라고 생각해보자

 

임의의 r번째 이후의 정보들을 버리는 방법이다.

대부분 중요한 정보들은 앞부분에 몰려있기때문에, r 번째 이후의 값들은 극히 작고, 더하나 마나 큰 차이가 없다.
따라서 이 정보들을 버려도 근사한 값을 갖게 된다.

 

Rank r버전의 X를 표현하는데 가장 적합한 방법이 R번째까지의 U, sigma, V transpose를 잘라내서 연결한 것이다.

만약 truancate 하면, U와 V는 더이상 정방행렬이 아니다.

이후에는 Ut x U = I이지만, U x U t는 I가 아니다 (중요!)

 

 

즉, U sigma V transpose로 분해한 후, 이들을 Rank 1의 절들의 합으로 변환할 수 있다.

이후에 특정 R 개수만큼만 truncate해서 기존 X과 근접한 행렬의 곱으로 표현할 수 있다.