SVD(Singaluar Vector Decomposition) 특이값 분해

참고자료
참고자료2

1. SVD(Singular Vector Decomposition)

특이값 분해(SVD : Singular Vector Decomposition)은 $m\times n$크기의 행렬 A를 다음과 같이 분해하는 것을 말한다.

m x n 크기의 행렬 A는 m x m 크기의 행렬 $U$와 m x n 크기의 $\Sigma$ 그리고 n x n 크기의 $V^T$로 나뉩니다. (위 식에서 행렬 $V$의 전치 행렬(Transpose)은 편의상 $V^T$라 표기한다.)
행렬 $U$와 $V$에 속한 벡터를 특이 벡터(Singular Vector)라 한다. 모든 특이 벡터는 서로 직교하는 성질을 가진다.(나중에 증명) $\Sigma$는 직사각 대각 행렬(diagonal matrix)이며, 행렬의 대각에 위치한 값만 0이 아니고 나머지 위치의 값은 모두 0이다. m < n인 경우 첫번째 그림과 같이 분해되며, m > n인 경우 두번째 그림과 같이 분해된다. $\Sigma$의 0이 아닌 대각 원소값을 특이값(Singular Value)라고 한다.

2. 특이값 분해의 특징

$A=U\Sigma V^T$에서 행렬 $A,U,V$의 특징은 다음과 같다.

$U$는 $AA^T$를 고유값 분해해서 얻은 직교 행렬이며, $V$는 $A^TA$를 고유값 분해해서 얻은 직교 행렬이다. 그리고 $\Sigma$는 m x n의 직사각 대각 행렬이며 대각 행렬의 대각 성분은 $AA^T$ 혹은 $A^TA$의 고유값들에 루트를 씌워준 값으로 구성되어 있다.
(증명)
$U,V,\Sigma$가 $AA^T$ 또는 $A^TA$의 고유값 분해(eigen decomposition)의 결과라고 했는데 그것에 대한 증명을 보이겠다.
먼저 대칭 행렬은 모두 고유값 분해가 가능하며, 더군다나 직교 행렬로 분해할 수 있다.(증명은 여기를 참고하라.)
$AA^T$ 또는 $A^TA$는 모두 대칭행렬이므로(직접 곱해보면 자명하다) 둘다 고유값 분해가 가능하며 고유벡터들이 모두 서로 직교한다.
$A=U\Sigma V^T$
$\begin{aligned} AA^T&=U\Sigma V^T(U\Sigma V^T)^T \\ &=U\Sigma V^TV\Sigma^TU^T \\ &=U(\Sigma\Sigma^T)U^T \quad (\because\;V\;is\;orthonormal\;matrix)\\ &=U(\Sigma\Sigma^T)U^{-1} \quad (\because\;U\;is\;orthonormal\;matrix) \end{aligned}$
따라서 $AA^T$를 고유값 분해(eigen decomposition)하면 U가 고유벡터들의 행렬이고 $\Sigma\Sigma^T$가 고유값(고유값을 대각성분으로 하는 대각행렬)이 된다.
$A^TA$도 같은 방식으로 증명이 된다.
정리하면, SVD는 특이값 분해라고 하며, 행렬 U와 V에 속한 벡터를 특이 벡터(Singular Vector)라 한다. 모든 특이 벡터는 서로 직교하는 성질을 가진다. 특히 U에 속한 벡터를 Left Singular Vector, V에 속한 벡터를 Right Singular Vector라고 한다. $\Sigma$는 대각행렬이며 대각 원소 값이 바로 행렬 A의 특이값(Singular Value)입니다.이 특이값은 $AA^T$ 혹은 $A^TA$의 고유값의 루트(Square Root) 값과 같다. $AA^T$ 혹은 $A^TA$의 고유값은 같은데 이에 대한 증명은 다음과 같다.
($AA^T$, $A^TA$의 고유값이 같은 이유 증명)
1) $AA^T$, $A^TA$의 고유값이 0 이상이다.
$A^TA$의 고유값을 $\lambda$, 고유벡터를 $\mathbf{v}$라 했을 때,
$A^TA\mathbf{v}=\lambda \mathbf{v}$
양변에 $\mathbf{v^T}$를 곱한다.
$\mathbf{v^T}A^TA\mathbf{v}=\mathbf{v^T}\lambda \mathbf{v}=\lambda\mathbf{v^Tv} \\ (A\mathbf{v})^TA\mathbf{v}=\lambda\mathbf{v^Tv} \\ \left\| A\mathbf{v} \right\|^2=\lambda\left\| \mathbf{v} \right\|^2 \\ \therefore \lambda \geq 0$

2) $AA^T$, $A^TA$의 고유값이 같다.

• $A^TA$의 고유값을 $\lambda$, 고유벡터를 $\mathbf{v (v\neq 0)}$라 했을 때,
  $A^TA\mathbf{v}=\lambda \mathbf{v} \qquad\cdots (1)$
  양변에 $A$를 곱한다.
  $AA^TA\mathbf{v}=A\lambda \mathbf{v}=\lambda A\mathbf{v} \\ (AA^T)A\mathbf{v}=\lambda A\mathbf{v} \quad\cdots (2)$
  만일 $A\mathbf{v}=0$이라면 (1)에서 $\lambda=0$이므로($\mathbf{v\neq 0})$ 고유값이 0이상이라는 조건에 위배되어 $A\mathbf{v}\neq0$ 이다. $A\mathbf{v}\neq0$이므로 (2)에서 $\lambda$는 $AA^T$의 고유값이다.
• 다음 $(A^TA)$에 대해서도 동일하게 전개해 보면,
  (2)에서 $AA^T$ 의 고유값은 $\lambda$이므로,
  $AA^T\mathbf{v}=\lambda\mathbf{v} \qquad\cdots (3)$
  양변에 $A^T$를 곱하면,
  $A^TAA^T\mathbf{v}=\lambda A^T\mathbf{v}\\ (A^TA)A^T\mathbf{v}=\lambda A^T\mathbf{v} \;\cdots (4)$
  $A^T\mathbf{v}$가 0이라면 (3)에서 $\lambda=0$이므로($\mathbf{v\neq 0})$ 고유값이 0이상이라는 조건에 위배되어 $A^T\mathbf{v}\neq0$ 이다. $A^T\mathbf{v}\neq0$이므로 (4)에서 $\lambda$는 $A^TA$의 고유값이다.

$\therefore\;\lambda$는 $AA^T, A^TA$의 고유값이다.

3. 특이값 분해(SVD)의 기하학적인 의미

행렬을 $x' = Ax$와 같이 좌표공간에서의 선형변환으로 봤을 때 직교행렬(orthogonal matrix)의 기하학적 의미는 회전변환(rotation transformation) 또는 반전된(reflected) 회전변환, 대각행렬(diagonal maxtrix)의 기하학적 의미는 각 좌표성분으로의 스케일변환(scale transformation)이다.
$A=U\Sigma V^T$에서 행렬 A의 선형 변환을 해보자. U, V는 직교행렬, $\Sigma$는 대각행렬이므로, 먼저 $V^T$로 회전 변환(Rotate)을 하고 $\Sigma$로 스케일 변환(Stretch)를 한 뒤 다시 $U$로 회전 변환(Rotate)을 하는 걸 볼 수 있다. 기하학적으로 표현하자면 아래와 같다.

고유값분해(eigendecomposition)에서 나오는 고유값(eigenvalue)과 비교해 보면 고유값은 변환에 의해 불변인 방향벡터(-> 고유벡터)에 대한 스케일 factor이고, 행렬의 특이값(singular value)은 변환 자체의 스케일 factor로 볼 수 있다.
SVD의 기하학적인 의미는 나중에 PCA(Principal Component Analysis)에서 중요하게 쓰이므로 잘 이해하도록 하자.

4. Full SVD와 Truncated SVD

행렬 A를 m x m 크기인 $U$, m x n 크기인 $\Sigma$, n x n 크기인 $V^T$ 로 특이값 분해(SVD)하는 것을 Full SVD라고 한다.(m>n)
즉 행렬 $U, V$의 행과 열 전체를 모두 다 사용한다.

($m\times n=(m\times m)\cdot (m\times n)\cdot (n\times n)$)
그런데, 실제로 이와같이 full SVD를 하는 경우는 드물며 아래 그림들과 같이 reduced SVD를 하는게 일반적이다.

($m\times n=(m\times s)\cdot (s\times n)\cdot (n\times n)$)($s<n$)
그림은 $\Sigma$에서 대각파트가 아닌 0으로 구성된 부분을 없애고 U에서는 이에 대응되는 열벡터들를 제거한 형태이고(thin SVD라 부른다)

($m\times n=(m\times r)\cdot (r\times r)\cdot (r\times n)$)($r<s$)
이 그림은 비대각 원소들뿐만 아니라 0인 singular value들까지 모두 제거한 형태이다(compact SVD). 0인 sungular value만을 제거했기 때문에 여기서 계산된 A'는 A와 동일한 행렬이 나온다.

($m\times n=(m\times t)\cdot (t\times t)\cdot (t\times n)$)($t<r$)
이 그림의 경우는 0이 아닌 singular value까지 제거한 형태로서(truncated SVD) 이 경우에는 원래의 A가 보존되지 않고 A에 대한 근사행렬 A'이 나온다. 즉 여기서 계산된 A'는 A로 완벽히 복원되지 않고 행렬 A와 유사한 행렬이 나온다.
그런데, 이렇게 truncated SVD로 근사한 행렬 A'은 matrix norm $\left\|A-A' \right\|$을 최소화시키는 rank t 행렬로서 데이터압축, 노이즈제거 등에 활용될 수 있다.(A의 유사행렬 A'가 A와의 차이가 최소화되는 A'가 만들어 진다는 말이다.)