왜 Singular Value Decomposition?

• Eigenvalue Decomposition

  $S = Q\Lambda Q^T$

  • Square matrix에만 적용 가능, 즉 Rectangular matrix 적용 불가
  • Real Symmetric matrix만 real eigenvalue, orthogonal eigenvector 보장

  ⇒ Singular Value Decomposition으로 확장!

• Singular Value Decomposition

  $A = U\Sigma V^T$

  • $\small U, V$ - Left & Right Singular Vectors
  • $\small \Sigma$ - Singular Values (대각 행렬, 모든 요소 $\ge 0$)

어떤 행렬도 SVD가 될까?

Key facts

• $\small U,V -Orthogonal, \;\;\Lambda\ge0$

• 우리는 다음 수식을 만족하는 2 sets of $Singular\;Vectors$ 를 찾고 싶다!!

  $Av_1 = \sigma_1u_1$

  $\\cdot\\cdot\\cdot \\;\\;\\;\\;\\;\\;\\;\\small{(\\sigma_1 \\geq \\sigma_2 \\geq \\cdot\\cdot\\cdot \\geq \\sigma_r \\gt 0)}$
  

  $Av_r = \sigma_ru_r$

• $v$ (Orthogonal vectors) → Multiply $A$ → $u$ (Orthogonal vectors) 를 만족하는 $v, u$ 를 찾고 싶은 것!

• 풀어 이야기 하자면, v vector space 상에서 직교하는 vector들에 A를 곱하여도, u vector space 상에서 여전히 vector들이 직교하는, v vector space 상의 vector set, u vector space 상의 vector set을 찾는 것

• 결과적으로 SVD를 통해 A의 정보를 여러 matrix로 쪼갤 수 있게 된다.

• 위 식을 matrix form으로 나타내면 $AV = \Sigma U$

$A\begin{bmatrix} |& &|\\ v_1&\cdot\cdot\cdot&v_n\\ |& &|\\ \end{bmatrix}{n\times n} = \begin{bmatrix} |& &|\\ u_1&\cdot\cdot\cdot&u_m\\ |& &|\\ \end{bmatrix}{m\times m} \begin{bmatrix} \sigma_1& &&| &\\ &\cdot\cdot&&|&0\\ &&\sigma_r& |&\\ -&-&-&-&-\\ & 0 &&|&0\\ \end{bmatrix}_{m\times n} \;\;\;\; \small{\sigma_1 \ge...\ge\sigma_r}$

$A\begin{bmatrix} |& &|\\ v_1&\cdot\cdot\cdot&v_r\\ |& &|\\ \end{bmatrix}{n\times r} = \begin{bmatrix} |& &|\\ u_1&\cdot\cdot\cdot&u_r\\ |& &|\\ \end{bmatrix}{m\times r} \begin{bmatrix} \sigma_1& &\\ &\cdot\cdot\cdot&\\ & &\sigma_r\\ \end{bmatrix}_{r\times r} \space\;\;\; \small{\sigma_1 \ge...\ge\sigma_r}$

• 여기서 $v, u$의 basis는 각 the row, column space of A

• A의 rank= r, V, U의 rank = r

• 앞의 r까지만 유효

• 다음과 같이 정리하고, r개의 rank 1 pieces로 decompse가능하다

  $AV = U\Sigma \rightarrow A = U\Sigma V^T \;\;\; \small{(\because V^T = V^{-1})}$

  $A = U\Sigma V^T = \sigma_1u_1v_1^T + \cdot\cdot\cdot + \sigma_ru_rv_r^T$