선형대수학 :: Singular Value Decomposition

Singular Value Decomposition

SVD : 특이값 분해

 

Digonalization : n*n A에 대하여

• n개의 independent eigenvectors
  
  

  $\begin{gather*}A=SΛS^{-1}\end{gather*}$

• A가 symmetric 이면 (A^T=A)
  
  

  $\begin{gather*}A=QΛQ^T\end{gather*}$

• n개의 independent eigenvectors X, A가 symmetric X, A가 n*n 이 아니면?
  ⇒ SVD

---

SVD Theorem

m*n real A
즉, 거의 모든 행렬들에 대하여 SVD가 존재한다.
A에 의하여 다음이 존재한다.

• U^TU=I 이므로 U^TU는 orthogonal matrix이다.

$\begin{gather*}m*m \ \ U, \ \ \ \ U^TU=I\end{gather*}$

 

$\begin{gather*}n*n \ \ V, \ \ \ \ V^TV=I\end{gather*}$

 

• Σ 는 diagonal matrix이다. (나머지 성분은 전부 0)
  σ 를 singular values라고 부르고, A가 symmetric 이면 eigenvalues이다.

 

$\begin{gather*}m*n \ \ \Sigma = \begin{bmatrix} \sigma_1 \\ & ... \\ & & \sigma_n \\ \\ \\ \end{bmatrix} or \begin{bmatrix} \sigma_1 \\ & ... \\ & & \sigma_n & & \end{bmatrix}\end{gather*}$

 

따라서 SVD는

 

$\begin{gather*}U^TAV=\Sigma\end{gather*}$

 

$\begin{gather*}A=U\Sigma V^T\end{gather*}$

 

---

증명

• n≤m이라 가정한다. (n > m이라면 A^T에 대하여 풀면 된다.)
• A^TA : n * n
  1. symmetric
  2. positive semi definite
  3. λ ≥ 0, n orthonormal eigenvectors.
• A^TA의 eigenvalues λ ≥ 0 (symmetric 이므로) 들에 루트를 씌운 뒤 내림차순 정렬하여
  
  

  $\begin{gather*}(σ_1, ...,σ_k \ge 0, \ \ \forall k)\end{gather*}$

  
  
  • 이때 σ > 0 인 개수가 r이라면
  • r = A^TA의 pivot > 0의 개수
    (symmetric 이므로 eigenvalue > 0의 개수 = pivot > 0 의 개수)
  • 즉, r = rank of A^TA & A
    (N(A^TA) = N(A) 이므로 dim(A^TA) = dim(A), 즉 free column의 개수가 동일.
    따라서 rank(A^TA) = rank(A) = n - freecolumn = r)

   

• A^TA의 orthonormal eigenvectors (symmetric 이므로)
  v1 … vn

 

$\begin{gather*}A^TAv_k=σ^2_kv_k\end{gather*}$

 

• 1 ≤ j ≤ r

$\begin{gather*}u_j = \frac{1}{σ_j}Av_j\end{gather*}$

 

$\begin{gather*}u^T_ju_k\\ =\frac{1}{σ_j}v^T_jA^T\frac{1}{σ_k}Av_k \\ =\frac{σ_k}{σ_j}v^T_jv_k\\ =\begin{cases} 1, \ \ \ \ j=k \\ 0, \ \ \ \ j\not=k \end{cases}\end{gather*}$

 

              * u1 … ur 은 orthonormal basis of C(A)
              * ur+1 … um 은 orthonromal basis of N(A^T)
                (C(A)와 N(A^T)는 orthogonal complement)

 

• k>r

 

$\begin{gather*}u^T_jAv_k=0\end{gather*}$

 

• k≤ r
  • j > r
    
    

    $\begin{gather*}u^T_jAv_k=0\end{gather*}$

  • j ≤ r
    
    

    $\begin{gather*}u^T_jAv_k=\begin{cases} \sigma_j, \ \ \ \ j=k \\ 0, \ \ \ \ j \not= k \end{cases}\end{gather*}$

 

---

---

 

풀이과정

m*n A의 SVD 구하기

 

$\begin{gather*}A=U\Sigma V^T\end{gather*}$

 

1. A^TA를 구한다.
2. |A^TA - λI| = 0을 풀어서 eigenvalue λ를 구하고 루트 씌워서
   σ 를 구한다. ⇒ Σ 구하기 가능. (단 내림차순)
3. (A^TA-λI)x = 0의 null space 즉, eigenvector v를 구한다. ⇒ n개 나온다.
   (주의 : σ 가 아니라 λ로 구해야 한다.)
   그리고 normalize eigenvector로 만든다.
4. u를 구한다. ⇒ m개 나온다.
   
   

   $\begin{gather*}u_j = \frac{1}{σ_j}Av_j\end{gather*}$

   
   이때 u는 m개 있는데 v로 만들 수 있는 u는 r개 밖에 만들지 못한다.
   (σ1…σr > 0, σr+1…= 0이라서 애초에 못 만듦)
   나머지 u는 v로 만들어진 u들과 orthogonal 하다.
   ⇒ A의 left nullspace를 구하고 normalize 한다. (= A^T의 null space)
5. Σ를 구한다.
6. 따라서 다음과 같이 분해할 수 있다.
   
   

   $\begin{gather*}A=U\Sigma V^T\end{gather*}$

---

SVD 압축

 

$\begin{gather*}A=U\Sigma V^T\end{gather*}$

 

곱해질 때

• U1 ~ Ur 까지는 σ 가 곱해져서 괜찮지만
  Ur+1부터는 0이 곱해지므로 필요 없다.
• V1^T ~ Vr^T 까지는 σ가 곱해져서 괜찮지만
  Vr+1^T부터는 0이 곱해지므로 필요 없다.

따라서 0이 되는 필요 없는 부분만 삭제하면 압축할 수 있다.

 

$\begin{gather*}A=σ_1u_1v_1^T+...+σ_ru_rv_r^T\end{gather*}$

 

• 이때 u는 m차원 벡터
• v는 n차원 벡터
• 따라서 만약 m = 1000, n = 1000, r = 20이라면
  원래 데이터의 크기는 1000000이지만 위 과정을 통해서
  100020(σu) + 100020(v) = 40000으로 압축할 수 있다.