SVD

SVD

SVD는 차원축소 뿐만 아니라, Matrix completion, Matrix Factorization(행렬 분해) 등에 사용한다.

• Rank

  랭크란 intrinsic dimensionality이다

  rank가 1이라는 것은 열벡터(행벡터)끼리 어떤 하나의 벡터의 곱으로 나타낼 수 있어 자유도는 0이라는 것이다. rank 가 mxn 행렬에서 min(m,n)이면 full rank 라고 한다.

• SVD

  모든 mxn 행렬 A에 대하여 A행렬의 rank가 r인 경우 다음과 같이 분해가능하다

  • cf. SVD 구하기
    • $V^T$: $A^{T}A$의 고유벡터로 구성됨 (v1, v2)
    • $U$: $A$의 고유값의 제곱근인 $\sigma$, A, v(위에서 구한) 것, 그리고 $A^{T}$의 left null space의 벡터를 그 크기로 나눈 것으로 구성된다.

    

    ref. https://www.youtube.com/watch?v=Ls2TgGFfZnU&t=129s

  

  

  또한 동일하게, D행렬(시그마 행렬)의 대각 원소를 통해 다음과 같이 표현할 수 있다. ui는 U행렬의 열벡터, vi 는 $V^{T}$ 행렬의 행벡터이다. 이것은 r개의 rank가 1인 행렬들을 더한 것으로 볼 수 있다.

  ($u1v1^T$는 rank가 1인 행렬)

  $A = \sum_{i=1}^{r} d_{i}u_{i}v_{i}^{T}$

  고유값 분해와 다른 점은 대각행렬(D, 시그마)의 원소는 항상 양수인 것이다. singular value는 항상 양수이다. eigen value는 복소수나 음수일 수 있다.

  $A = \sum_{i=1}^{r} d_{i}u_{i}v_{i}^{T} = \sum_{i=1}^{n} d_{i}u_{i}v_{i}^{T}$

  그리고 1부터 n까지로 나타내고, $d_{r+1} , \cdots d_{n} = 0$ 으로 표현이 가능해, 여러 표현이 가능하며, 헷갈릴 수 있음.

  

• SVD와 관련된 행렬의 Norm

  l1, l2 - 벡터의 길이를 측정, infinity norm - 벡터의 박스(?)를 포착하듯이,

  이 3가지 노름은 행렬의 힘, 에너지, 크기 등을 측정한다고 볼 수 있으며 SVD와 관계가 있다.

  • Frobenius Norm(Hilbert Schmidt norm)

    

    벡터에서의 l2 norm처럼 프로비니우스 노름을 사용한다. 4번째 항은 SVD를 사용해 표현한 것이고, 5번째 항은 norm(a,b) = norm(b,a)인 노름의 성질을 이용한 것이다.

    따라서, A행렬의 SVD의 대각행렬의 제곱합이 프로비니우스 노름이며, dot product에서 유도된 것이다.

  • Operator Norm or Spectral Norm

    

    행렬 A의 singular value 중 가장 큰 값이 A의 operator norm이다. 또한 동일하게 $A^T A$나 $AA^T$의 가장 큰 고유값의 제곱근은 operator norm은 같다. PCA의 기본적인 아이디어가 operator norm을 사용한 것이다.

  • Nuclear Norm or Trace Norm

    

    A행렬의 singular value들의 합은 Nuclear Norm이다.

• Matrix Approximation

  SVD가 어떤 것을 하는지 이해하기 위해 Matrix Approximation을 아는 것은 중요하다.

  SVD는 best approximation을 제공한다.

  $\argmin_{B \ rank1} ||A-B||_{op} = d_{1}u_{1}v_{1}^{T}$

  A를 근사하는 가장 좋은 rank가 1인 행렬 B는 $d_{1}u_{1}v_{1}^{T}$ 이다. 그리고 op 노름(가장 큰 singular value)가장 큰 으로 계산한 에러는 d2(두번째로 큰 singular value)이다. 즉, 가장 큰 singular value와 singular vector가 가장 큰 에너지를 차지한다.

  유사하게 A에 근사하는 rank가 2이면서, 손실이 가장 작은 행렬 B는 $d_{1}u_{1}v_{1}^{T} + d_{2}u_{2}v_{2}^{T}$일 것이다.

  오차를 프로비니어스 노름으로 계산하면 다음과 같을 것이다. $||A-d_{1}u_{1}v_{1}^{T}||_{F} = \sqrt{\sum_{i=2}^{r}d_{i}^{2}}$

  → 결론적으로 rank k의 행렬과 프로비니어스 노름과 operator 노름으로 계산했을 때 가장 오차가 작은 행렬 B는 $\Sigma_{i=1}^{k} d_{i}u_{i}v_{i}^{T}$ 이다.

  rank가 줄기 때문에 굉장히 차원축소를 많이 할 수 있는 것이다.

  $u1v1^T$행렬과 $u2v2^T$의 행렬은 서로 직교하기 때문에 0 이다. 또한, $uivi^T$는 행렬 A의 기저이며, 어떤 기저가 가장 중요한지 SVD 찾게 해준다.

• references

  https://www.youtube.com/watch?v=2HQ5Z1y0bEg&list=PLRCdqbn4-qwqqC-ksijw-PCQbt92pugvV