공부하는 단계에서 정리한 내용입니다.
잘못된 내용이 있다면 말씀해주시면 감사하겠습니다.
https://mml-book.github.io/book/mml-book.pdf
4.5.2 Construction of the SVD
이번 section에서는 왜 SVD가 항상 존재하는지, 그리고 SVD를 어떻게 계산하는지에 대해서 알아볼 것이다.
SVD는 정사각행렬의 eigendecomposition과 비슷한 면이 있다.
Remark.
SPD(symmetric positive definite) 행렬 $S$의
eigendecomposition은 $S = S^{\top} = PDP^{\top}$이고
SVD는 $S = U \Sigma V^{\top}$ 이다.
만약 $U = P = V$이고 $D = \Sigma$ 일 때 eigendecomposition과 SVD가 같아진다.
이제 본격적으로 SVD를 어떻게 계산하는지 알아볼 것이다.
$m \times n$ 행렬 $A$를 계산하는 것은 두 orthonormal bases $U = (u_1, \cdots, u_m)$과 $V = (v_1, \cdots, v_n)$을 구하는 것과 같다. 이렇게 계산된 bases들로 행렬 $U$와 $V$를 만들 것이다.
총 4단계로 구성된다.
1. 먼저 right-singular vector의 orthonormal set $v_1, \cdots, v_n$ 부터 만든다.
-> $\mathbb R^m$의 벡터들을 새로운 basis로 정렬해야 하는데, 이 중에서 가장 깔끔한 축을 찾아야 하기 때문
Spectral theorem에서 대칭행렬의 eigenvector들은 ONB, 즉 diagonalize 할 수 있음을 알 수 있다.
그리고 Theorem 4.14에서 $m \times n$ 행렬 $A$에 대해서 항상 symmetric, positive semidefinite한 $n \times n$ 행렬 $A^{\top}A$를 만들 수 있음을 알 수 있다.
그러므로 $A^{\top}A$를 항상 diagonalize 시킬 수 있고, $A^{\top}A = PDP^{\top} = P \begin{bmatrix} \lambda_1 & \cdots & 0 \\ \vdots & \ddots & \vdots \\ 0 & \cdots & \lambda_n \end{bmatrix} P^{\top}$ 가 된다.
여기서 $\lambda_i \geq 0$은 $A$의 eigenvalue 들이다.
$A$의 SVD가 존재한다고 가정하고, $A^{\top}A$에 $A = U \Sigma V^{\top}$ 을 넣어보자. 그러면 아래와 같이 전개된다.
$$A^{\top}A = (U \Sigma V^{\top})^{\top} (U \Sigma V^{\top}) = V \Sigma^{\top} U^{\top}U \Sigma V^{\top} = V \Sigma^{\top} \Sigma V^{\top} = V \begin{bmatrix} {\lambda_1}^2 & 0 & 0 \\ 0 & \ddots & 0 \\ 0 & 0 & {\lambda_n}^2 \end{bmatrix} V^{\top}$$
위의 두 식을 비교해보면 $V^{\top} = P^{\top}$이고 $\sigma_i^2 = \lambda_i$임을 알 수 있다.
- 행렬 $P$($A^{\top}A$의 eigenvector들)가 $A$의 right-singular vector임
- $A^{\top}A$의 eigenvalue들은 $\Sigma$의 singular value들의 제곱임
2. 그다음에 left-singular vector의 orthonormal set $u_1, \cdots, u_m$ 을 만든다.
-> $V^{\top}$와 $\Sigma$를 거치면서 크기가 조정되었고, 마지막으로 $\mathbb R^n$에 맞춰서 새로운 방향으로 정렬해야 함
Left-singular vector $U$를 구할 때도 비슷한 과정을 거친다.
먼저 $AA^{\top}$의 SVD를 구한다.
$$AA^{\top} = (U \Sigma V^{\top})(U \Sigma V^{\top})^{\top} = U \Sigma V^{\top} V {\Sigma}^{\top} U^{\top} = U \begin{bmatrix} \sigma_1^2 & 0 & 0 \\ 0 & \ddots & 0 \\ 0 & 0 & \sigma_m^2 \end{bmatrix} U^{\top}$$
$AA^{\top}$은 대칭행렬이므로 spectral theorem에 의해서 diagonalize 할 수 있으므로 $AA^{\top} = SDS^{\top}$이다.
이때 얻어지는 eigenvector $S$가 SVD의 left-singular vector가 된다.
이제 $\Sigma$만 구하면 된다. $AA^{\top}$과 $A^{\top}A$가 동일한 nonzero eigenvalue를 가지므로, SVD에서의 nonzero entry들도 동일해야 한다.
3. 이렇게 구한 두 집합을 연결해서 $A$가 적용되었을 때 $v_i$들의 orthogonality가 유지되도록 한다.
두 집합 $U$와 $V$를 연결하기 위해서 $A$에 의해서 변환된 $v_i$들도 orthogonal 해야 한다는 사실을 이용할 것이다.
Section 3.4에서 $i \neq j$ 일 때, $A_{v_i}$와 $A_{v_j}$의 내적이 0이 되어야 한다. 즉, $A$가 변환한 벡터들이 서로 직교해야 함을 배웠다.
즉, 서로 다른 $v_i$와 $v_j$가 orthogonal eigenvector라면 아래 식이 성립한다.
$$(A_{v_i})^{\top}(A_{v_j}) = {v_i}^{\top}A^{\top}Av_j = {v_i}^{\top}(\lambda_i v_j) = {\lambda_i v_i}^{\top}v_j = 0$$
$m \geq r$ 일 때, $Av_1, \cdots, Av_r$이 $\mathbb R^m$의 $r$차원 부분공간의 baiss가 된다.
4. 그리고 이렇게 변환된 벡터들을 스칼라 인자들로 정규화해서 singular vector($U$하고 $V$에 속해있는 벡터)를 구한다.
SVD를 완성하기 위해서 우리는 orthonormal한 left-singular vector($u_i$)들이 필요하다.
아래와 같이 right-singular vector의 $A_{v_i}$들을 정규화하면 $u_i$들을 얻을 수 있다.
$$u_i := \frac{A_{v_i}}{\| A_{v_i} \|} = \frac{1}{\sqrt{\lambda_i}}A_{v_i} = \frac{1}{\sigma_i}A_{v_i}$$
(+ 중간에 왜 $\| A_{v_i} \| = \sqrt{\lambda_i}$인지 전개해봤다.)
따라서 $v_i$와 $u_i$가 $\Sigma$를 통해서 연결된다.
위에서 온 $u_i = \frac{1}{\sigma_i}A_{v_i}$를 아래와 같이 다시 쓸 수 있다.
$$Av_i = \sigma_i u_i (i = 1, \cdots, r(=rank))$$
보면 eigenvalue 방정식하고 비슷하지만, 좌변과 우변의 벡터가 다르다.
즉, SVD에서는 변환 후에 벡터의 방향이 바뀜을 알 수 있다!
$n \leq m$ 일 때, 모든 $i \leqslant n$에 대해서 성립하지만 $i > n$인 $u_i$이 존재하긴 한다. 그냥 남아있는 basis 라고 생각하면 된다.
$m \leq n$일 때도 마찬가지이다.
즉, SVD가 $A$의 null space($Ax = 0$)도 찾을 수 있다는 뜻이다!
$Av_i = \sigma_i u_i $에서 $v_i$를 모아서 행렬 $V$로, $u_i$를 모아서 행렬 $U$로 만들면 아래와 같아진다.
$$AV = U \Sigma$$
여기서 양변에 $V^{\top}$을 곱하면 아래와 같이 $A$의 SVD가 나온다.
$$A = U \Sigma V^{\top}$$
Ex 4.13 (Computing the SVD)
행렬 $A = \begin{bmatrix} 1 & 0 & 1 \\ -2 & 1 & 0 \end{bmatrix}$의 SVD를 구해보자.
그러려면 right-singular vector들 $v_i$, singular value들 $\sigma_k$, left-singular vector들 $u_i$를 구해야 한다.
아래와 같이 3단계에 걸쳐서 구하면 된다.
보통 singular value는 $\sigma_1 \geqslant \sigma_2 \geqslant \cdots \sigma_r \geqslant 0$ 순으로 정렬된다.
(앞 포스팅에서 포스팅했던 Theorem 4.22 아래쪽에 나와있음..)
(틀린 풀이)
이거 까먹고 처음에 그냥 아래처럼 오름차순으로 계산했는데 어딘가 이상했음. 검산을 했는데 A가 $\begin{bmatrix} 1 & 0 & 1 \\ -2 & 1 & 0 \end{bmatrix}$가 안 나옴
(수정해서 맞은 풀이)
Sigular value가 $\sigma_1 \geqslant \sigma_2 \geqslant \cdots \sigma_r \geqslant 0$ 순으로 정렬되어야 하기 때문에 eigenvalue부터 내림차순으로 정렬해줬다.
끝!!!
이것도 오래 걸렸다.
점점 감을 잡아가는 것 같기도 하다.
근데 이게 어디에 쓰이는지는 아직 잘 모르겠다.