특이값 분해 (Singular Value Decomposition)

특이값 분해

벌써 고윳값 분해의 확장판인 특이값 분해를 정리할 때가 왔다. 으하하

선형 대수를 다시 공부해야지 마음을 먹었을 때 특이값 분해에 대해서 대충만 알고 제대로 배워본 적이 없어서 특이값 분해는 대체 어떻게 정 사각 행렬이 아닌 행렬에 대해서 분해를 하는 것일까 궁금했었는데 드디어 그 비밀을 파헤쳐 볼 때가 되었다.

이번 장에서는 다음 내용들을 다룬다.

1. 특이값 분해란?
2. 특이값 분해

 

특이값 분해(SVD: Singular Value Decomposition)란?

특이값 분해라는 이름을 딱 들으면 바로 이전에 배운 고윳값 분해가 생각이 난다. 고윳값 분해와 마찬가지로 특이값 분해 또한 행렬을 대각화 할 수 있는 방법이다.

고윳값 분해의 가장 큰 문제점인 $n \times n$ 정방 행렬이어야만 한다는 것과 Symmetric이어야만 대각화 및 고유 벡터들이 orthogonal 함을 보장한다는 것을 해결한 것이 바로 특이값 분해이다.

특이값 분해는 $m \times n$ 행렬에 대해서도 분해가 가능하며, Symmetric이 아니어도 분해된 결과가 직교 행렬을 이루게 된다.

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

위와 같이 분해하는 것이 특이값 분해이다.

 

특이값 분해

이제 특이값 분해에 대해서 자세히 살펴보자.

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

위 식의 행렬의 shape를 나타낸 그림

위와 같이 $m \times n$ 행렬 $A$를 $U, \Sigma, V^T$ 세가지 행렬로 분해하는 것을 SVD. 특이값 분해라고 부른다.

이때 $U$는 $m \times m$ 정방 행렬, $\Sigma$는 $m \times n$ 주 대각선을 제외한 모든 요소가 0인 행렬, $V^T$는 $n\times n$ 정방 행렬이며, $U, V^T$는 각각 왼쪽 특이 벡터, 오른쪽 특이 벡터들을 열벡터로 하는 직교 행렬이다. (즉, $U^TU = I, V^TV = I$)

 

그렇다면 이러한 특이값 분해의 결과 $U, \Sigma, V^T$는 어떻게 구할까?

그 전에 자기 자신과 행렬 곱 한 결과가 Symmetric이라는 행렬의 특성을 먼저 짚고 넘어가야 이해에 도움된다.

• $A^TA, AA^T$는 Symmetric이다.즉, Symmetric 하다는 것을 알 수 있음. 그렇다면 $A^TA, AA^T$는 고윳값 분해 시 Symmetric Matrix의 이점을 활용 가능 (Diagonalizable & Eigen vector들이 수직)
• $(A^TA)^T = AA^T$에 각각 Transpose를 다시 취한 것이므로 $= A^TA$

 

그렇다면 행렬 $A$를 자기 자신과 행렬 곱한 결과를 살펴보자.

$$
\begin{matrix}
A = U\Sigma V^T \\
\begin{align}
AA^T &= U\Sigma V^T \cdot V\Sigma^T U^T \\
&= U\Sigma\Sigma^TU^T \\
&= Q\Lambda Q^T
\end{align}
\end{matrix}
$$

즉, $AA^T$를 Eigen Decomposition 시 $Q$가 바로 우리가 찾던 $U$이다.

이번엔 반대로 $A^TA$의 결과를 살펴보자.

$$
\begin{align}
A^TA &= V\Sigma^T U^T \cdot U\Sigma V^T \\
&= V\Sigma^T\Sigma V^T \\
&= Q\Lambda Q^T
\end{align}
$$

마찬가지로 $A^TA$를 Eigen Decomposition 시 $Q$가 바로 우리가 찾던 $V$가 된다.

이제 마지막으로 행렬 $\Sigma$만 찾으면 된다. $\Sigma\Sigma^T$의 경우 $\Lambda$가 되는데 이때 $\Sigma$는 아래와 같다.

$$
\Sigma = \begin{bmatrix}
\sigma_1 & 0 & \cdots & 0 & \cdots &0 \\
0 & \sigma_2 & \cdots & 0 & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots & \cdots & \vdots\\
0 & 0 & \cdots & \sigma_m & \cdots & 0
\end{bmatrix}, (m < n)
$$

그러므로 $\Sigma\Sigma^T$의 결과는 정방 행렬에 주 대각선 요소가 $\sigma_i$의 제곱이 되며 이 요소들의 값은 $\sqrt{\lambda_i}$가 될 것이다.

이때 $m > n$인 경우 $\Sigma^T\Sigma$의 결과 $n\times n$의 행렬로 구해야 편하게 구할 수 있고, $m < n$인 경우 $\Sigma\Sigma^T$의 결과 $m \times m$ 행렬로 구해야 편하게 구할 수 있다.

 

결국 정리해보면 $\Sigma$에는 eigen vector들의 양의 제곱근으로 주 대각선이 구성되었고 나머지는 0인 행렬이며, $U$는 $AA^T$의 eigen vector들을 열 벡터로 하는 행렬로 이러한 eigen vector들을 $A$의 left singular vector라 부르며 $U$를 left singular matrix라 부른다.

마지막으로 $V$는 $A^TA$의 eigen vector들을 열 벡터로 하는 행렬로 이런 eigen vector들을 $A$의 right singular vector라 부르며, $V$를 right singular matrix라 부른다.

 

Non-Zero Singular Value의 수

이때 알아두면 좋은게 있는데 0이 아닌 Singular Value의 수는 Rank(A)와 같다는 것이다.

0이 아닌 Singular Value의 수는 사실상 $AA^T, A^TA$의 0이 아닌 eigen value의 수와 동일하다.

이때 $A^TA, AA^T$는 어차피 행렬 $A$로 만든 것이기 때문에 rank(A)와 동일하며 rank($AA^T$)는 0이 아닌 eigen value의 수이므로 0이 아닌 Singular Value의 수는 Rank(A)와 같다!

Singular Value Decomposition을 기하학적으로 잘 설명한 유튜브가 있어 밑 동영상을 보면 더 좋다.

그렇다면 한 가지 궁금한 점이 생긴다. 정방 행렬에 특이값 분해를 적용 시 결과는 고윳값 분해의 결과와 동일할까?

 

 

고윳값 분해와 특이값 분해의 결과의 동일성

먼저 답부터 말하자면 “그런 경우가 존재하지만 그 외의 경우는 아니다.” 이다.

대신 특정 조건이 만족하는 경우 고윳값 분해와 특이값 분해의 결과가 동일한 경우가 존재한다.

그 조건은 아래와 같다.

• 행렬 $A$가 Symmetric 이어야 한다.
• 행렬 $A$의 고유값이 전부 양수(positive definite)이어야 한다. (positive definite 참고)

 

$A$가 대칭 행렬인 경우 $A$의 고윳값 분해는 $A = Q\Lambda Q^T$가 되며, 특이값 분해는 그냥 $A = U\Sigma V^T$라는 것을 알고 있다.

이때 우리는 $U$와 $V$를 구하기 위해서 $AA^T, A^TA$의 고유 벡터들을 구해야 한다.

이때 $A$가 Symmetric인 경우 $A^TA = AA^T$이므로 $U = V$가 되며, $U$는 직교 행렬이므로 $A$의 특이값 분해 또한 $A = Q'\Sigma {Q'}^T$가 된다.

 

이제 $Q = Q'$임을 보이면 되는데 이는 고유 벡터가 특이 벡터와 같다는 것을 의미한다.

$A$의 고유 벡터 $x$가 있을때 $Ax = \lambda x$가 된다. 그렇다면 특이 벡터 $x'$의 경우 $A^TAx' = \lambda'x'$이 되는데 이 두 정보를 사용해 아래와 같은 결과를 얻을 수 있다.

$$
\begin{align}
A^TAx &= A^T \lambda x \\
&= A\lambda x \\
&= \lambda^2x \\
&= \lambda' x'
\end{align}
$$

이를 통해서 2가지 정보를 얻을 수 있다.

• $x = x'$
• $\lambda' = \lambda^2$

즉, 특이 벡터는 고유 벡터와 동일하며, $A^TA$의 고유값은 $A$의 고유값의 제곱이며, $A$의 특이값은 $A^TA$의 고윳값의 양의 제곱근이기에 positive definite인 $A$의 고윳값과 동일하다.

 

결국 Symmetric인 고유값이 모두 양수인 행렬 $A$는 특이 벡터와 고유벡터가 동일하며, 고유값과 특이값도 동일하기에 $A$의 특이값 분해와 고윳값 분해는 동일하다라는 결론에 이른다.

 

 

실제 SVD 계산시 알아두면 좋은점

Full SVD

위 그림은 SVD의 식을 나타낸 그림이다. $U, V^T$는 각각 $m \times m, n \times n$ 정방 행렬이다.

Thin SVD

하지만 위와 같은 Full SVD 보다는 일반적으로는 위와 같이 $\Sigma$의 0인 부분을 제거하고 그에 해당하는 $U$의 열 벡터를 제거한 Thin SVD 버전을 사용하여 불필요한 계산을 줄인다.

Compact SVD(좌)와 Truncated SVD(우)

그 외에도 위와 같이 대각 요소 중 0이 아닌 부분도 제거한 Compact SVD를 사용해 더 불 필요한 계산을 줄이거나, 큰 상위 특이값 $n$개 만을 남기는 Truncate SVD를 사용해 데이터 압축, 노이즈 제거의 효과를 보기도 한다.

드디어 엄청나게 궁금했던 특이값 분해까지 마쳤다. 크하하하

 

Reference

• Deeplearning Ch.2 Linear Algebra
• 유튜브 혁펜하임
• 데이터 사이언스 스쿨 - 특잇값 분해
• 행렬의 분해(고윳값 분해, 스펙트럼 분해, 특잇값 분해)
• 위키백과 정부호 행렬