일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
31 |
- 코드포스
- 재배치
- matrix
- c++
- column space
- vector
- 대상파일
- CS정리
- 구문트리
- 정처기 실기 공부법
- 정처기 공부법
- 행렬
- 다익스트라
- 컴퓨터밑바닥의비밀
- 링커
- 선형대수학
- 컴파일러
- unity
- 알고리즘
- linear algebra
- rust 스터디
- Rust
- eigenvalue
- 정보처리기사 2025 1회 실기 벼락치기
- 스레드전용저장소
- 정처기 실기 벼락치기
- 다이나믹 프로그래밍
- 정보처리기사 실기 벼락치기
- 백준
- 벡터
- Today
- Total
개발_기록용
[선형대수학 정리] 20. 특이값 분해 (SVD, Singular value Decomposition) 본문
1. 배경
그래픽스 공부에 들어가기 전, 근본 중에서도 근본인 선형대수학을 먼저 파야겠다고 생각했다!
Chris Ohk 님의 Game Developer Roadmap 2022를 보고 내가 부족한 부분을 채워나가기로 결심했기 때문이다.
https://github.com/utilForever/game-developer-roadmap
GitHub - utilForever/game-developer-roadmap: Roadmap to becoming a game developer in 2022
Roadmap to becoming a game developer in 2022. Contribute to utilForever/game-developer-roadmap development by creating an account on GitHub.
github.com
.
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하다.
고윳값 분해 내용을 통해 어떤 행렬이 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 이미지에 대해서도
데이터 압축이 가능해지는 것을 의미한다.
'선형대수학' 카테고리의 다른 글
[선형대수학 정리] 22. LU 분해, PLU 분해, LDU 분해 (2) | 2024.07.29 |
---|---|
[선형대수학 정리] 21. 의사역행렬 (pseudo inverse) 짤막 정리 (0) | 2024.07.29 |
[선형대수학 정리] 19. 주성분 분석 (PCA : Pricipal Component Analysis) (8) | 2024.07.24 |
[선형대수학 정리] 18. 고윳값 분해 (eigen decomposition) (7) | 2024.07.24 |
[선형대수학 정리] 17. 고윳값과 고유벡터(eigen value & eigen vector) (3) | 2024.07.24 |