3-4. 고급 선형대수: SVD(1)

Quick Review
(1) Diagonalization
Eigenvectors가 역행렬이 존재할 때(=선형독립일 때) $A=V\Lambda V^{-1}$과 같이 분해할 수 있다.

(2) 대칭행렬의 대각화
1.  실수 대칭행렬  A의 고유값은 실수다.
2.  고유값이 서로 다른 고유벡터는 직교한다.(항상 대각화 가능하다)
3.  대칭행렬  A가 양의 (준)정부호이면 고유값은 모두 양수이거나 0이다.

(3) 분산행렬
임의의 실수행렬 $X$에 대해 $A=X^TX$ 혹은 $A=XX^T$를 만족하는 $A$를 분산행렬이라고 한다.
1.  대칭행렬이다.
2.  양의 준정부호이다.
3.  $X$가 풀랭크이면,  $A$의 역행렬이 존재한다.

(4) $A=V\Lambda V^T$

$\begin{cases}
v_i^Tv_j=0(i \ne j) \\
v_i^Tv_i=1
\end{cases}$

위 성질에 따라 대칭 행렬 $A$의 고유벡터가 정규직교한다면 $V^{-1}=V^T$가 되기 때문에($\because VV^T=E$) 대각화 연산이 훨씬 쉬워진다. 즉, $A=V\Lambda V^T$와 같이 표현할 수 있게 된다. 이렇게 되면 행렬 $A$의 고유값과 고유벡터만 찾으면 대각화가 가능해진다.

본론

정방행렬이며 고유벡터가 선형독립일 때 고유분해를 할 수 있었다. 하지만 이에 해당하는 행렬은 극히 일부이며, 많은 행렬은 고유분해가 불가능하다. 그렇기 때문에 고유분해 대신 특잇값분해(Singular Value Decomposition)를 할 수 있다.

특잇값분해는 임의의 실수행렬 $A$를 $A=U\Sigma V^T$로 분해하는 것으로 정의할 수 있다.($A \in \mathbb{m \times n}$) 이 때 $U$를 Left Singular Vector, $V$를 Right Singular Vector라고 한다.각각의 요소에 대해 알아보자.

(1) $U$
$AA^T=(U\Sigma V^T)(V\Sigma U^T)=U\Sigma^2U^T\quad(U\in \mathbb{R}^{m \times m})$

즉, $\Sigma^2$는 $AA^T$의 고유값이며, $U$는 $AA^T$의 고유벡터다.

(2) $V$
$A^TA=(V\Sigma U^T)(U\Sigma V^T)=V\Sigma^2V^T\quad(V\in \mathbb{R}^{n \times n})$

즉, $\Sigma^2$는 $A^TA$의 고유값이며, $V$는 $A^TA$의 고유벡터다.

정리해보자면 행렬 $A$의 Left Singular Vector는 $AA^T$의 고유벡터이며, Right Singular Vector는 $A^TA$의 고유벡터이다. $AA^T$와 $A^TA$는 같은 고유값을 가지며, 각각의 고유값에 루트를 씌워 $\Sigma$를 구할 수 있다.

단, $\Sigma$에 고유값을 넣을 때는 가장 큰 고유값이 $\sigma_{11}$에 위치하게, 가장 작은 고유값이 끝에 위치하도록 해야 한다. 즉, 내림차순으로 정렬해야 한다. 또한, $U$와 $V$의 사이즈가 다르기 때문에 행렬의 곱셈을 가능하게 하기 위해 $\Sigma$에 zero-padding해서 $m \times n$행렬로 만든다.

특잇값분해를 그림으로 나타내면 다음과 같다.

Matrix Approximation

$A$는 특이값분해 해서 아래와 같이 나타낼 수 있다.

$A=U\Sigma V^T=\sigma_1u_1v_1^T+\sigma_2u_2v_2^T+...+\sigma_ru_rv_r^T\quad (r=min(m,n))$

특이값은 내림차순으로 정렬했으므로 $\sigma_1 \ge \sigma_2 \ge ... \ge \sigma_r$를 만족한다.

랭크-k 근사(rank-k approximation)는 위 식에서 k개의 항을 선택하여 행렬 $A$를 표현하는 것이다. k개의 항을 어떻게 조합할 것인가에 따라 $A$를 근사할 수 있는 정도가 다를 것이다. 이 때 여러 조합 중 $A$를 가장 잘 근사하도록 조합해야 한다. ($1\le k \le r$)

정답을 먼저 알려드리자면, 첫 번째 항부터 k번째 항까지를 선택하면 $A$를 가장 잘 근사하게 된다.

 

왜 그렇게 될 것인가에 대한 자세한 설명에 들어가기 전에 예시로 진짜 그렇게 되는지 확인해보자.

 

(주피터 노트북 코드를 직접 올리려고 했는데 아무리 해도 안돼서 구글 코랩에 올렸다.)

 

아래는 행렬 근사의 다양한 형태를 그림으로 나타낸 것이다.

 

아래와 같이 행렬 A를 SVD로 분해하는 것을 full SVD라고 부른다. 단, 이 경우는 $m>n$

 

 

하지만 실제로 full SVD를 하는 경우는 드물며, 아래와 같이 reduced SVD를 하는 것이 일반적이다.

 

아래는 $\Sigma$에서 대각파트가 아닌 0으로 구성된 부분을 없애고 $U$에서 이에 대응되는 열벡터들을 제거한 형태이며, thin SVD라고 부른다.

 

 

아래는 비대각 원소들 뿐만 아니라 0인 Singular values까지 모두 제거한 형태이며, compact SVD라고 부른다.

 

 

지금까지의 행렬은 계산을 하면 $A$가 그대로 나왔지만, 이번에 볼 truncated SVD는 원래의 $A$를 보존하지 않고 $A$에 대한 근사행렬 $A'$가 나온다.

 

 

출처

김도형의 데이터사이언스 스쿨 수학편

[선형대수학 #4] 특이값 분해(Singular Value Decomposition, SVD)의 활용

특이값 분해

Lecture: The Singular Value Decomposition (SVD)