Singular Value Decomposition (SVD, 특이값 분해)

행렬을 세 개의 행렬로 분해하여 원본 행렬의 중요한 구조적 정보를 추출하는 기법으로, 차원 축소나 노이즈 제거 등에 활용

Singular Value Decomposition

---

---

• Dimension reduction 보다는, data compression 하는 방법
• Eigen decomposition (고유값 분해) 처럼, diagonalization of matrix(행렬의 대각화) 하는 방법으로, 모든 크기의 $m \times n$ matrix A 에 대해 적용 가능하다.
• ${A=U\sum V^T}$
• $U$ 와 $V$ 는 각각 $m \times m, n \times n$ 크기의 orthogonal matrix 이며, $\sum$ 는 $m \times n$ 행렬이다.
• Orthogonal Matrix (직교 행렬) 이란, Transposed matrix (전치 행렬) 이 Inverse matrix (역행렬) 가 되는 matrix

• SVD’s geometric meaning (기하학적 의미) 는 아래와 같다.
  • 2x2 size 의 orthogonal matrix 는 다음의 shape 와 equivalent 하다.

• $\epsilon=1$ 일 때에는 Rotation matrix (회전 변환 행렬) 과 같은 shape 이며, $\epsilon = -1$ 일 때에는 inverse 된 Reflection rotation matrix 를 의미한다.
• Diagonal matrix (대각 행렬) 는 each axle 로의 scale transformation 을 의미한다.
• Matrix A 의 linear transformation 을 rotation transformation 과 scale transformation 으로 divide 하는 것이 SVD 이다.
• SVD, ${(A=U\sum V^T)}$

• U 는 ${AA^T}$ 의 eigenvector 를 column vector 로 가지고 있는 matrix 로, 이 때의 ‘column vectors 를 left singular vector of A’ 라고 부른다.
  • $U=[u_1 \ u_2 \ … u_m], \ (AA^T)u_i=\lambda_iu_i$
• V 는 ${A^TA}$ 의 eigenvector 를 column vector 로 가지고 있는 matrix 로, 이 때의 ‘column vectors 를 right singular vector of A’ 라고 부른다.
  • $V=[v_1 \ v_2 \ … v_n], \ (A^TA)v_i=\lambda_iv_i$
• $\sum$ 는 ${AA^T}$ 또는 ${A^TA}$ 의 eigenvalue 들의 root value ($\sigma$) 를 diagonal element 로 하는 $m \times n$ rectangle diagonal matrix 이다.(직 사각 대각 행렬)
• 이 때의 elements 가 Singular value (특이값) 이다.

Property in SVD

---

---

• ${AA^T}$ 와 ${A^TA}$ 는 모두 square matrix 이므로 eigen decomposition 가능하다.
• 이 때의 eigenvalue 는 모두 over the 0
• $A^TAv=\lambda v\Rightarrow v^TA^TAv=\lambda v^Tv\Rightarrow(Av)^TAv=\lambda v^Tv\Rightarrow$ ${||Av||^2=\lambda||v||^2}$
• 0 이 아닌 eigenvalue 는 서로 같으며, 하나의 matrix $\sum$ 으로 표현.

$A^TAv =\lambda v \Rightarrow A(A^TA)v=\lambda Av \Rightarrow AA^T(Av)=\lambda(Av). \ \textrm{if} \ Av\neq0$ ($Av=0$ 이면, $Av=\lambda v$ 이므로 eigenvalue 는 0이 되기 때문에, assumption.)

• For reference, there is exist-able when eigenvalue is 0
• $Au=\lambda u=0$
• Due to eigenvector cant be exist 0-vector, A is only singular matrix without inverse matrix.
• 
  • m > n 일 때에는 $u_{n+1},…,u_m$ eigenvector’s eigenvalue is 0.
    • $AA^T$ matrix 가 singular matrix 이다.
  • $\sigma_1,…,\sigma_n \ge 0$ 이므로, 0 값인 singular value 가 possible to exist
    • $A^TA$ matrix 가 singular matrix 이다.
  • $\sigma_n=0$ 이라면, $u_n,u_{n+1},…,u_m$ eigenvector 의 sequence 는 random 으로 바뀌어도 irrelevant 하다.

Data Compression using SVD

---

---

Case: Decompose an $m\times n$ matrix using SVD

• Full SVD

  

• Thin SVD (Output : 동일한 matrix A)

  

• Compact SVD (Output : 동일한 matrix A. 0의 singular value 를 제외하는 method)

  

• Truncated SVD (Output : Approximate matrix $A’$. 작은 singular value 까지 제외하는 method)