[선형대수학 정리] 20. 특이값 분해 (SVD, Singular value Decomposition)

1. 배경

 

---

그래픽스 공부에 들어가기 전, 근본 중에서도 근본인 선형대수학을 먼저 파야겠다고 생각했다!
 
Chris Ohk 님의 Game Developer Roadmap 2022를 보고 내가 부족한 부분을 채워나가기로 결심했기 때문이다.
 

https://github.com/utilForever/game-developer-roadmap

.

2. 정리

---

고윳값 분해의 아쉬운 점

 

 

고윳값 분해의 아쉬운 점은 n x n 정사각행렬이고대칭행렬이어야만 적용 가능하다는 점이었다.

 

SVD는 이 두가지 아쉬운 점을 날려버릴 수 있다.

 

---

특이값 분해 (SVD)

 

 

m x n 행렬 A에 대해 특이값 분해를 하면

 

$$A=U\Sigma V^{T}$$

 

로 나타내 고윳값 분해와 같은 꼴로 decomposition할 수 있다.

 

• 행렬 Σ는 대각성분 외의 값은 모두 0인 m x n 대각행렬이다.
• 행렬 Σ의 대각성분들은 행렬 A의 singular value 들이다.
• 행렬 A의 singular value σ 는 A^{T}A 혹은 AA^{T}의 고윳값 λ 에 루트를 씌운 것이다.
• 행렬 V는 A^{T}A의 고유벡터 행렬이다.
• 행렬 V의 Column vector를 right singluar vector라 한다.
• 행렬 U는 AA^{T}의 고유벡터 행렬이다.
• 행렬 U의 Column vector를 left singular vector라 한다.

---

특이값 분해의 과정을 살펴보자.

A^{T}A와 AA^{T}는 무조건 정사각행렬에 symmetric하다.
→ 무조건 U와 V를 구할 수 있다.

 

 

그러면 AA^{T}를 전개하면 U를 구할 수 있고

A^{T}A를 전개하면 V를 구할 수 있게 된다.

---

 

행렬 A의 rank를 r이라 하자.

우선 A^{T}A는 n x n 행렬이니 고유벡터 v와 고윳값 λ는 n개이고 다음을 만족한다.

 

$$\lambda_{1}\geq\lambda_{2} \geq\cdots \geq \lambda_{n}$$

 

$$\lambda_{1}, \cdots ,\lambda_{r} \geq 0$$

 

$$\lambda_{r+1}, \cdots ,\lambda_{n}= 0$$

 

그리고 A^{T}A는 대칭행렬이니 diagonalizable하다.

---

[선형대수학 정리] 18. 고윳값 분해에서 발췌.

---

 

고윳값 분해 내용을 통해 어떤 행렬이 diagonalizable하면

이것의 0이 아닌 고윳값의 수는 이 행렬의 rank와 같다는 것을 알고 있다.

 

그러면 A^{T}A의 고윳값의 수는 rank(A^{T}A)와 같다.

 

그런데, A의 rank가 r이니

A^{T}A의 rank도 모두 r로 동일하다. (rank(AA^{T})도 r로 동일.)

 

따라서, non-zero singular value의 수는 rank(A)와 같다.

---

$$A=U\Sigma V^{T}$$

 

이 식에 대해 양변에 행렬 V를 곱하면

 

$$AV=U\Sigma$$

 

로 정리할 수 있고, 이때

우변은 UΣ = [ σ_{1}​u_{1}​​  σ_{2}​u_{2}  ⋯  σ_{r}​u_{r}  0 ​​ ⋯​  0 ] 의 형태이고,

좌변은 AV = [ Av_{1}  ​​Av_{2} ​​ ⋯  Av{r}  0  ​⋯  0 ] 의 형태이다.

 

그러면 곧 Av_{i} = σ_{i}u_{i} 이 성립한다.

 

---

 

그리고 행렬의 곱을 위와 같이 전개하면

고윳값이 singular value로 바뀐 것만 다르고

PCA와 동일한 식으로 표현할 수 있고, 이는 곧 m x n 이미지에 대해서도

데이터 압축이 가능해지는 것을 의미한다.