특잇값 분해 - Singular Value Decomposition (SVD)

특잇값 - Singular value

행렬 $A$의 특잇값(singular value; $\sigma$)은 $A^T A$의 고윳값의 제곱근에 의해서 정의된다.

$\sigma_i(A)=\sqrt{\lambda_i}$
($\lambda_i$는 $A^TA$의 고윳값)

예시

2×3 행렬 $A$ :

$A=\begin{bmatrix}4&11&14\\8&7&-2\end{bmatrix}$

$A^TA=\begin{bmatrix}4&8\\11&7\\14&-2\end{bmatrix}\begin{bmatrix}4&11&14\\8&7&-2\end{bmatrix}=\begin{bmatrix}80&100&40\\100&170&140\\40&140&200\end{bmatrix}$

$\lambda = \{36,9,0\}$

$\therefore \sigma_1=6,\ \sigma_2=3,\ \sigma_3=0$

특잇값 분해 - Singular Value Decomposition (SVD)

특잇값 분해(Singular Value Decomposition ; SVD)는 어떤 실수 m×n 행렬을 다음과 같이 세 행렬로 분해하는 방법이다.

$A=U\sum V^T$

• $U$ : 정규 직교 벡터(왼쪽 특이 벡터;left singular vector)를 열로 가지는 m×m 직교 행렬
• $V$ : 정규 직교 벡터(오른쪽 특이 벡터;right singular vector)를 열로 가지는 n×n 직교 행렬
• $\sum$ : 특잇값을 주대각 성분으로 가지는 m×n 대각 행렬

  $\sum = \mathsf{diag}(\sigma_1, \sigma_2,...,\sigma_r,0,...)$

  $(\sigma_1\ge\sigma_2\ge\cdots\ge\sigma_r>0\ \mathsf{and}\ r=\mathsf{rank}(A))$

SVD는 정방 행렬이 아니더라도 항상 존재한다.

SVD 더 디테일한 개념

실수 행렬 $A\in\mathbb R^{m\times n}$는 다음과 같이 분해될 수 있다.

$A=U\sum V^T$

• $U\in \mathbb R^{m\times m}$ :
  $AA^T$의 고유벡터(left singular vector)를 열로 가지는 m×m 직교 행렬. 즉, $U^TU=I$

• $V\in \mathbb R^{n\times n}$ :
  $A^TA$의 고유벡터(right singular vector)를 열로 가지는 n×n 직교 행렬. 즉, $V^TV=I$

• $\sum \in \mathbb R^{m\times n}$ :
  다음과 같은 형태의 대각 행렬.

  $\sum = \begin{pmatrix}\sigma_1&&&\\&\sigma_2 &&\\&&\ddots&\\&&&\sigma_r\end{pmatrix}$

  $(\sigma_1\ge\sigma_2\ge\cdots\ge\sigma_r>0\ \mathsf{and}\ r=\mathsf{rank}(A))$

각 $\sigma_i$는 $A^TA$의 0이 아닌 고윳값의 제곱근이고, 이를 $A$의 특잇값(singular value)이라고 한다.

$U$의 열들은 $AA^T$의 고유벡터이고 $V$의 열들은 $A^TA$의 고유벡터이다.

$AA^T=(U\sum V^T)(U\sum V^T)^T=U\sum V^TV\sum^T U^T=U\sum^2U^T$

$A^TA=(U\sum V^T)^T(U\sum V^T)=V\sum^T U^TU\sum V^T=V\sum^2V^T$
이므로 $A^TA\ (or\ AA^T)$의 고윳값 $\lambda_i$는 다음을 만족한다.

$\lambda_i=\sigma_i^2$ ($\sigma_i$는 $A$의 $i$번째 특잇값)

이를 이용하여 $A^TA$의 고유벡터를 구하면 왼쪽 특이벡터(left singular vector) $\mathbf u_i$를 다음과 같이 계산할 수 있다.

$\mathbf u_i = \cfrac{A\mathbf v_i}{\sigma_i}$

반대로 다음을 이용해 오른쪽 특이 벡터(right singular vector)도 구할 수 있다.

$A\mathbf v_i=\sigma_i\mathbf u_i$

예제로 알아보기

예제 1 (2×2).

다음 행렬을 특잇값 분해 하여라.

$A=\begin{bmatrix}\sqrt3&2\\0&\sqrt3\end{bmatrix}$

단계별 풀이.

Step 1: $A^TA$ 구하기

$A^TA=\begin{bmatrix}\sqrt3&0\\2&\sqrt3\end{bmatrix}\begin{bmatrix}\sqrt3&2\\0&\sqrt3\end{bmatrix}=\begin{bmatrix}3&2\sqrt3\\2\sqrt3&7\end{bmatrix}$

Step 2: $A^TA$의 고윳값 구하기

$\det(A^TA-\lambda I)=\begin{vmatrix}3-\lambda&2\sqrt3\\2\sqrt3&7-\lambda\end{vmatrix}=\lambda^2-10\lambda+9=(\lambda-9)(\lambda-1)$

$\Rarr \lambda_1=9,\ \lambda_2=1 \Rarr \sigma_1=3,\ \sigma_2=1$

Step 3: $A^TA$의 고유벡터 구하기

$(A^TA-9I)\mathbf x=\begin{bmatrix}-6&2\sqrt3\\2\sqrt3&-2\end{bmatrix}\begin{bmatrix}x_1\\x_2\end{bmatrix}=\begin{bmatrix}0\\0\end{bmatrix}$

$\begin{cases}-6x_1+2\sqrt3x_2=0\\2\sqrt3 x_1-2x_2=0\end{cases}\Lrarr \sqrt 3x_1- x_2=0$

일반 해 : $t(1, \sqrt3)$

$\mathbf v_1=\begin{bmatrix}1\\\sqrt3\end{bmatrix}$

정규화 : $\mathbf v_1=\frac{\mathbf v_1}{||\mathbf v_1||}=\begin{bmatrix}\frac{1}{2}\\\frac{\sqrt 3}{2}\end{bmatrix}$

$(A^TA-I)\mathbf x=\begin{bmatrix}6&2\sqrt3\\2\sqrt3&2\end{bmatrix}\begin{bmatrix}x_1\\x_2\end{bmatrix}=\begin{bmatrix}0\\0\end{bmatrix}$

$\begin{cases}6x_1+2\sqrt3x_2=0\\2\sqrt3 x_1+2x_2=0\end{cases}\Lrarr x_1+\frac{1}{\sqrt3}x_2=0$

일반 해 : $t(-1, \frac{1}{\sqrt3})\Rarr t(-\sqrt3,1)$

$\mathbf v_2=\begin{bmatrix}-\sqrt{3}\\1\end{bmatrix}$

정규화 : $\mathbf v_2=\frac{\mathbf v_2}{||\mathbf v_2||}=\begin{bmatrix}-\frac{\sqrt3}{2}\\\frac{1}{2}\end{bmatrix}$

Step 4 : 왼쪽 특이벡터 $\mathbf u_i=\frac{1}{\sigma_i}A\mathbf v_i$ 계산

$\mathbf u_1=\frac{1}{\sigma_1}A\mathbf v_1=\cfrac{1}{3}\begin{bmatrix}\sqrt3&2\\0&\sqrt3\end{bmatrix}\begin{bmatrix}\frac{1}{2}\\\frac{\sqrt3}{2}\end{bmatrix}=\begin{bmatrix}\frac{\sqrt3}{2}\\\frac{1}{2}\end{bmatrix}$

$\mathbf u_2=\frac{1}{\sigma_2}A\mathbf v_2=1\begin{bmatrix}\sqrt3&2\\0&\sqrt3\end{bmatrix}\begin{bmatrix}-\frac{\sqrt3}{2}\\\frac{1}{2}\end{bmatrix}=\begin{bmatrix}-\frac{1}{2}\\\frac{\sqrt3}{2}\end{bmatrix}$

Step 5 : 결론

$U= [\mathbf u_1, \mathbf u_2]=\begin{bmatrix}\frac{\sqrt3}{2}&-\frac{1}{2}\\\frac{1}{2}&\frac{\sqrt3}{2}\end{bmatrix}$

$V=[\mathbf v_1, \mathbf v_2]=\begin{bmatrix}\frac{1}{2}&-\frac{\sqrt3}{2}\\\frac{\sqrt3}{2}&\frac{1}{2}\end{bmatrix}$

$\sum=\mathsf{diag}(\sigma_1, \sigma_2,...,\sigma_r,0,...)=\begin{bmatrix}3&0\\0&1\end{bmatrix}$

$\therefore A=U\sum V^T=\begin{bmatrix}\frac{\sqrt3}{2}&-\frac{1}{2}\\\frac{1}{2}&\frac{\sqrt3}{2}\end{bmatrix}\begin{bmatrix}3&0\\0&1\end{bmatrix}\begin{bmatrix}\frac{1}{2}&\frac{\sqrt3}{2}\\-\frac{\sqrt3}{2}&\frac{1}{2}\end{bmatrix}$

특잇값 분해의 기하적 해석

m×n 행렬$A$에 대해서 우리의 목표는 $A^T$와 $A$의 열 공간의 정규 직교 기저를 구하는 것이다.

이 행렬의 계수(rank)가 2라고 가정할 때, 벡터 $\mathbf v_1$, $\mathbf v_2$를 $A^T$의 열 공간의 정규직교벡터라고 하자.

$A$의 열 공간에 놓인 $A$의 상(image)은 $A\mathbf v_1$, $A\mathbf v_2$이고, 이를 정규화 하면 다음과 같다.

$\mathbf u_1=\cfrac{A\mathbf v_1}{||A\mathbf v_1||}=\cfrac{A\mathbf v_1}{\sigma_1}\ ,\quad$ $\mathbf u_2=\cfrac{A\mathbf v_2}{||A\mathbf v_2||}=\cfrac{A\mathbf v_2}{\sigma_2}$

그러므로 우리는 다음을 알 수 있다.

$A[\mathbf v_1, \mathbf v_2]=[\mathbf u_1, \mathbf u_2]\begin{bmatrix}\sigma_1&0\\0&\sigma_2\end{bmatrix}=[\sigma_1\mathbf u_1,\ \sigma_2\mathbf u_2]$

이를 기하적으로 해석해보자.
$A$는 정규직교벡터 $\mathbf v_1, \mathbf v_2$를 스칼라 배 된 정규직교벡터 $\mathbf u_1, \mathbf u_2$로 사상(map)한다.

쉽게 말해 선형 변환 $A$는 정규직교벡터 $\mathbf v_1, \mathbf v_2$를 각각 $\sigma_1\mathbf u_1,\ \sigma_2\mathbf u_2$로 늘리고, 회전시킨다. 이 때, 직교성을 보존한 채 크기만 변화한다.

즉, $V$는 입력 평면의 좌표축, $\sum$은 스케일링, $U$는 결과 벡터가 놓이는 출력 평면의 좌표축이고, 이를 통해 SVD는 행렬 $A$를 다음 세 가지로 분해한 것이다.

$A=U\sum V^T\Rarr$ 회전$(V^T)$ $\rarr$ 스케일링$(\sum)$ $\rarr$ 회전$(U)$

---

<참고자료>
Steve J. Leon, Linear Algebra with Application, 10th edition, 2021.