[Linear Algebra] 14. Eigen Decomposition & SVD

이번 글에서는 고윳값 분해(eigen decomposition)와 SVD(singular value decomposition)에 대해 알아볼 것이다.

 

1. 고윳값 분해

2-D to 2-D linear transformation $A$에 independent한 eigenvector $\mathbf{\vec{v_1}}$,  $\mathbf{\vec{v_2}}$와 eigenvalue $\lambda_1$, $\lambda_2$가 있다고 가정할 때, 다음과 같이 식을 전개할 수 있다.

참고로, $\mathbf{\vec{v_1}}$,  $\mathbf{\vec{v_2}}$는 서로 independent한 eigenvector이기 때문에 eigenbasis로 볼 수 있다.

 

$$ V = \begin{bmatrix} \mathbf{\vec{v_1}} & \mathbf{\vec{v_2}} \end{bmatrix} ; \Lambda = \begin{bmatrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{bmatrix} $$

$$ A\mathbf{\vec{v_1}} = \lambda_1 \mathbf{\vec{v_1}}, \quad A\mathbf{\vec{v_2}} = \lambda_1 \mathbf{\vec{v_2}} $$

$$ A \begin{bmatrix} \mathbf{\vec{v_1}} & \mathbf{\vec{v_2}} \end{bmatrix} = \begin{bmatrix} \lambda_1 \mathbf{\vec{v_1}} & \lambda_2 \mathbf{\vec{v_2}} \end{bmatrix} $$

$$ A \begin{bmatrix} \mathbf{\vec{v_1}} & \mathbf{\vec{v_2}} \end{bmatrix} = \begin{bmatrix} \mathbf{\vec{v_1}} & \mathbf{\vec{v_2}} \end{bmatrix} \begin{bmatrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{bmatrix} $$

$$ AV = V \Lambda \rightarrow A = V\Lambda V^{-1}$$

 

$A = V\Lambda V^{-1}$을 고윳값 분해라고 한다.

이때, 고윳값 분해가 되는 모든 행렬을 "diagonalizable"한 행렬이라고 한다. 

참고로, "행렬 A에 eigenbasis가 존재한다"와 "행렬 A는 diagonalizable하다"는 동치이다.

---

1.1. 고윳값 분해의 속성?

1. $A^k =V\Lambda^KV^{-1}$

2. $A^{-1} = (V\Lambda V^{-1})^{-1} = V\Lambda V^{-1}$

3. $\det (A) = \det (V) \det(\Lambda) \det (V^{-1}) = \det(\Lambda) = \prod_{i=1}^N \lambda_i$

4. $\det (A) = 0 \leftrightarrow$ 0인 eigenvalue가 하나 이상 존재한다.

---

5. $A$가 orthogonal matrix이면, 모든 $\lambda_i = \pm1$이다.

$A \mathbf{\vec{v_i}} = \lambda_i \mathbf{\vec{v_i}} \rightarrow (A\mathbf{\vec{v_i}})^\top A\mathbf{\vec{v_i}} = \mathbf{\vec{v_i}}^\top A^\top A \mathbf{\vec{v_i}} = \lVert \mathbf{\vec{v_i}} \rVert^2 = \lambda_i^2 \lVert \mathbf{\vec{v_i}} \rVert^2 \rightarrow \lambda_i = \pm1$

 

6. Diagonalizable matrix $A$의 non-zero eigenvalue의 수는 rank($A$)와 같다.

 

- 6번째 명제에 대한 직관적인 설명 -

$A$가 diagonalizable하다는 것은 "서로 independent한 eigenvector가 n개 있다 $\leftrightarrow$ eigenbasis가 있다"는 의미다.

rank$(A) \ge n$이고, 모든 eigenvector는 $A$의 column space에 속해있기 때문에,

$A$의 column space를 eigenvector 기준으로 분해할 수 있다.

결론, $A$의 column space를 N개의 rank-1 space로 쪼갠 후, 해당 space의 eigenvalue가 0인 경우, squeeze된다.

그렇기 때문에, $A$의 zero eigenvalue의 수 만큼 column space가 squeeze된다.

 

---

1.2. 대칭행렬(=symmetric matrix)은 diagonalizable하며, $A = Q\Lambda Q^\top$이 된다.

이때, $Q$는 orthogonal matrix다.

 

$$A^\top = A \rightarrow A = Q\Lambda Q^{-1}, A^\top = Q^{-\top}\Lambda Q^\top \rightarrow Q^{-1} = Q^\top \rightarrow Q \text{ is orthogonal matrix}$$

$$\text{So if } A^\top = A, \text{then } A = Q\Lambda Q^\top \\ (Q \text{ is orthogonal matrix})$$

 

2. SVD

고윳값 분해는 특정 행렬(square and sysmmatrix matrix)에만 적용이 가능했다. 

그에 반해, SVD는 모든 행렬에 적용이 가능하다. 즉, 임의의 $n \times m$ 행렬 $A$를 다음과 같이 분해할 수 있다.

 

$$A = U\Sigma V^\top$$

($\underset{n \times n}U$ and $\underset{m \times m}V$ are both orthogonal matrix, $\underset{n \times m}\Sigma$ is diagonal matrix)

 

 

2.1. $A$의 non-zero singular value의 수는 rank($A$)와 같다.

 

- 직관적인 설명 -

$A = U\Sigma V^\top \rightarrow A\mathbf{\vec{v_1}} = \lambda_1 \mathbf{\vec{u_1}}, \ A\mathbf{\vec{v_2}} = \lambda_2 \mathbf{\vec{u_2}}, \ \cdots$ 이기 때문에,

모든 $\mathbf{\vec{u_i}}$는 $A$의 column space에 속해있다.

그러므로, $A$의 column space를 $\mathbf{\vec{u_i}}$기준으로 분해할 수 있다.

결론, $A$의 column space를 N개의 rank-1 matrix $\mathbf{\vec{u_i}}$로 쪼갠 후, 해당 matrix의 $\lambda_i$가 0인 경우, squeeze된다.

그렇기 때문에, $A$의 zero singluar value의 수 만큼 column space가 squeeze된다.