[선형대수] 4.5.2 Construction of the SVD

공부하는 단계에서 정리한 내용입니다.

잘못된 내용이 있다면 말씀해주시면 감사하겠습니다.

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부터 내림차순으로 정렬해줬다.

 

 

끝!!!

이것도 오래 걸렸다.

점점 감을 잡아가는 것 같기도 하다.

근데 이게 어디에 쓰이는지는 아직 잘 모르겠다.