[Linear Algebra] 14. Eigen Decomposition & SVD

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

 

1. 고윳값 분해

2-D to 2-D linear transformation $A$에 independent한 eigenvector $\overrightarrow{{\mathbf{v}}_{\mathbf{1}}}$,  $\overrightarrow{{\mathbf{v}}_{\mathbf{2}}}$와 eigenvalue ${\lambda }_1$, ${\lambda }_2$가 있다고 가정할 때, 다음과 같이 식을 전개할 수 있다.

참고로, $\overrightarrow{{\mathbf{v}}_{\mathbf{1}}}$,  $\overrightarrow{{\mathbf{v}}_{\mathbf{2}}}$는 서로 independent한 eigenvector이기 때문에 eigenbasis로 볼 수 있다.

 

$$V=\left[\begin{array}{cc}\overrightarrow{{\mathbf{v}}_{\mathbf{1}}}& \overrightarrow{{\mathbf{v}}_{\mathbf{2}}}\end{array}\right];\mathrm{\Lambda }=\left[\begin{array}{cc}{\lambda }_1& 0\\ 0& {\lambda }_2\end{array}\right]$$

$$A\overrightarrow{{\mathbf{v}}_{\mathbf{1}}}={\lambda }_1\overrightarrow{{\mathbf{v}}_{\mathbf{1}}},A\overrightarrow{{\mathbf{v}}_{\mathbf{2}}}={\lambda }_1\overrightarrow{{\mathbf{v}}_{\mathbf{2}}}$$

$$A\left[\begin{array}{cc}\overrightarrow{{\mathbf{v}}_{\mathbf{1}}}& \overrightarrow{{\mathbf{v}}_{\mathbf{2}}}\end{array}\right]=\left[\begin{array}{cc}{\lambda }_1\overrightarrow{{\mathbf{v}}_{\mathbf{1}}}& {\lambda }_2\overrightarrow{{\mathbf{v}}_{\mathbf{2}}}\end{array}\right]$$

$$A\left[\begin{array}{cc}\overrightarrow{{\mathbf{v}}_{\mathbf{1}}}& \overrightarrow{{\mathbf{v}}_{\mathbf{2}}}\end{array}\right]=\left[\begin{array}{cc}\overrightarrow{{\mathbf{v}}_{\mathbf{1}}}& \overrightarrow{{\mathbf{v}}_{\mathbf{2}}}\end{array}\right]\left[\begin{array}{cc}{\lambda }_1& 0\\ 0& {\lambda }_2\end{array}\right]$$

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

 

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

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

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

---

1.1. 고윳값 분해의 속성?

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

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

3. $det(A)=det(V)det(\mathrm{\Lambda })det(V^{-1})=det(\mathrm{\Lambda })=\prod _{i=1}^N{\lambda }_i$

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

---

5. $A$가 orthogonal matrix이면, 모든 ${\lambda }_i=\pm 1$이다.

$A\overrightarrow{{\mathbf{v}}_{\mathbf{i}}}={\lambda }_i\overrightarrow{{\mathbf{v}}_{\mathbf{i}}}\to (A\overrightarrow{{\mathbf{v}}_{\mathbf{i}}}{)}^{\mathrm{\top }}A\overrightarrow{{\mathbf{v}}_{\mathbf{i}}}={\overrightarrow{{\mathbf{v}}_{\mathbf{i}}}}^{\mathrm{\top }}{A}^{\mathrm{\top }}A\overrightarrow{{\mathbf{v}}_{\mathbf{i}}}=\Vert \overrightarrow{{\mathbf{v}}_{\mathbf{i}}}{\Vert }^2={\lambda }_i^2\Vert \overrightarrow{{\mathbf{v}}_{\mathbf{i}}}{\Vert }^2\to {\lambda }_i=\pm 1$

 

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\mathrm{\Lambda }{Q}^{\mathrm{\top }}$이 된다.

이때, $Q$는 orthogonal matrix다.

 

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

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

 

2. SVD

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

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

 

$$A=U\mathrm{\Sigma }{V}^{\mathrm{\top }}$$

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

 

 

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

 

- 직관적인 설명 -

$A=U\mathrm{\Sigma }{V}^{\mathrm{\top }}\to A\overrightarrow{{\mathbf{v}}_{\mathbf{1}}}={\lambda }_1\overrightarrow{{\mathbf{u}}_{\mathbf{1}}},A\overrightarrow{{\mathbf{v}}_{\mathbf{2}}}={\lambda }_2\overrightarrow{{\mathbf{u}}_{\mathbf{2}}},\cdots$ 이기 때문에,

모든 $\overrightarrow{{\mathbf{u}}_{\mathbf{i}}}$는 $A$의 column space에 속해있다.

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

결론, $A$의 column space를 N개의 rank-1 matrix $\overrightarrow{{\mathbf{u}}_{\mathbf{i}}}$로 쪼갠 후, 해당 matrix의 ${\lambda }_i$가 0인 경우, squeeze된다.

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