특잇값 분해(Singular value decomposition, SVD) - 행렬식으로 만들기

특잇값 분해(Singular value decomposition, SVD) - 행렬식으로 만들기

 

0) 서론

이전까지 특이값 분해의 아주 기본적이지만, 핵심적인 내용을 모두 살펴보았습니다.

1. 방향이 바뀌지 않는 벡터를 고유값 분해로 찾을 수 있으니, 고유값 분해로 직교인 벡터도 찾을 수 있지 않을까?
2. 특수한 경우에만 가능하네? 왤까? 아, 이런저런 문제로 행렬 자체의 본질적인 축으로는 절대 불가능 하구나
3. 그럼 행렬 $A$가 선형 변환이니까, 변환 전과 변환 후로 나누어서 둘 다 동시에 직교성을 만족시키는 건 찾을 수 있나?
4. 찾을 수 있네! 그리고 직교성을 유지하는 그 변환은 '회전'과 '스케일링'으로 나눌 수 있구나!

까지 살펴보았는데요, 결국 이 개념이 바로 특이값 분해의 핵심 개념인거죠!

이번 포스팅에서는 벡터단위로 전개한 논지를 행렬식으로 합쳐보도록 하죠!

 

 

1) 행렬로 만들기

이전 포스팅에서 우리는 '입력축'이라고 불렀던 직교하는 벡터 $v_i$, '출력축 자체(혹은 '입력축이 변환된 출력축의 방향')'라고 불렀던 직교하는 벡터 $u_i$, '입력축이 변환된 출력축의 크기'라고 불렀던 스칼라 값 $\sigma_i$를 정의했습니다.

그리고 이것을 한번에 쓰면 벡터에 대해서 정의된 특이값 분해 식이 나옵니다.

$ Av_i = \sigma_i u_i $

즉, 직교하는 입력 벡터중 하나를 $A$라는 행렬로 선형변환하면 이 벡터는 $\sigma_i$라는 크기를 가지고 $u_i$라는 방향으로 변환된다. 입니다.

그리고 모든 $v_i$와 $u_i$는 정규직교한다고 말씀드렸었죠.(대칭행렬을 EVD한 결과 벡터들은 스펙트럼 정리에 의해서 서로 정규직교한다고 했었으니까요)

그럼 이 벡터들을 한번 '쌓아서' 행렬을 만들어 볼까요?

 

• 행렬 $V$: 고유벡터 $v_i$들을 열로 삼아서 모든 벡터를 쌓아 행렬 $V$를 만들 수 있겠죠?
  \begin{align}
  V &=
  \begin{bmatrix}
  | & | \\
  v_1 & v_2 & \cdots \\
  |& |
  \end{bmatrix}
  \end{align}
  
  
• 행렬 $\Sigma$: 그리고 $\sigma_i$는 고유값 $\lambda_i$들에 루트를 씌워($\sigma_i = \sqrt{\lambda_i}$) 대각 행렬 $\Sigma$를 만듭니다.
  (여기서 $\lambda$를 모은 행렬 $\Lambda$는 주 대각 성분에 고유값들을 가지는 대각 행렬인데, 왜 주 대각 성분에 고유값들을 가지는 지에 대한 더욱 자세한 내용은 피보나치 수열을 선형대수로 풀어보자 중 대각화 포스팅에서 살펴보실 수 있습니다.)
  (간단히 짚어보자면, 고유값 분해 식을 행렬식 $AV=V\Lambda$으로 썼을 때, 고유벡터 $v_i$들을 열로 삼아서 쌓았기 때문에 각 고유벡터 $v_i$에 $\lambda_i$를 곱해주려면 너무나도 당연하게 $\Lambda$행렬은 주 대각 성분에 $\lambda_i$를 가질 수 밖에 없습니다.)
  \begin{align}
  \Sigma &=
  \begin{bmatrix}
  \sigma_1 & 0 & \cdots \\
  0 & \sigma_2 & \cdots \\
  \vdots & \vdots & \ddots
  \end{bmatrix}
  \end{align}
  
  
• 행렬 $U$: $v_i$와 $\sigma_i$를 이용해, $u_i = \frac{1}{\sigma_i}Av_i$라는 공식으로 $u_i$들을 모두 계산하고, 이것들을 열로 삼아 행렬 $U$를 만듭니다.
  \begin{align}
  U &=
  \begin{bmatrix}
  | & | \\
  u_1 & u_2 & \cdots \\
  | & |
  \end{bmatrix}
  \end{align}

 

이렇게 행렬들을 전부 만들어보았습니다!

그런데... 이 행렬들을 어떤식으로 배치를 해야 우리가 생각한 대로 행렬식이 세워질까요?

 

 

2) 세 행렬을 어떻게 합치면 좋을까?

사실 원래 고민할 것도 없습니다.

원래 벡터 식이

$ Av_i = \sigma_i u_i $

였으니까, 행렬식으로 바꿔주면

$ AV = U\Sigma$

가 되겠죠!($\sigma u$에서 $U\Sigma$로 가 위치가 바뀌는 건, 행렬연산을 하게되면 연산 규칙에 따라 당연히 바뀌어야 하는 부분입니다. 실제로 계산이 올바로 되는 형태가 $U \Sigma$죠.)

그리고 보기 좋게 "$A$라는 행렬에 대해서(즉, 행렬을 분해)"한 형태로 쓰면

$ A = U\Sigma V^{-1} $

이렇게 나오겠죠! 근데, 정규직교 행렬에서는 역행렬과 전치행렬이 똑같다고 했으므로

$ A = U\Sigma V^T $

로 최종 정리 할 수 있겠습니다.

그리고 이 형태가 바로 특이값 분해 입니다.

용어도 한번 살펴보자면, '출력축'인 $U$는 Left Singular Vector라고 하고, '입력축'인 $V$는 Right Singular Vecoter라고 합니다. 그리고 가운데 특이값 행렬은 당연히 Singular Value죠.

 

 

3) 또 다르게 생각해 볼 수 없나? 기하학적 접근

위에서는 우리가 지금까지 구한 벡터식을 행렬식으로 변환시켜주면서 자명하게 유도되는 결과를 가지고 설명드렸는데요

이제 조금 다르게 기하학적으로 생각해보겠습니다.

 

$x$라는 벡터가 있습니다.

이 벡터를 $A$라는 행렬로 선형 변환을 할 때를 생각해 볼까요?

단순히 $x$벡터에 행렬$A$를 곱하면 수행되는 선형변환을 이제부터 낱낱히 뜯어보겠습니다.

 

출처: wikipedia.org

 

1. 일단 $x$벡터는 행렬$A$의 공간에 들어오면서 행렬 $A$의 입력축에 맞게 회전합니다.(좌표축 변환, $V$)
   
   
2. 그리고 행렬$A$의 '스케일링'효과를 받아 각 축 방향으로 길이가 늘어나거나 줄어들죠.(스케일링, $\Sigma)
   
   
3. 이제 마지막으로 행렬$A$의 공간을 나가면서 출력축에 맞게 다시 회전하죠.(좌표축 변환, $U$)

 

이것이 바로 단순히 $x$벡터에 행렬$A$를 곱하면 나오는 값을 조각조각 나눠봤을 때 벌어지는 상황입니다.

 

자, 그럼 위 상황을 수식으로 써볼까요?

$ Ax = U (\Sigma (V (x) ) ) $

겠죠 일단 $x$를 $V$로 작업해야 하고, 그 결과를 $\Sigma$로 작업해야 하고, 그 결과를 $U$로 작업해야 하니까요?

 

그런데, 여기서 행렬 연산으로 바꾸면 벡터와 곱하기 위해서는 $V$행렬을 전치시켜주어야 합니다.

따라서 행렬식으로 다시써보면

$ Ax = U \Sigma V^T x $

모든 x에 대해서 성립하려면 행렬 자체가 같아야 하니까, 양변 소거되어

$ A = U \Sigma V^T $

즉, $A$라는 행렬이 임의의 선형변환을 할때 실제로는 어떤 자세한 과정을 거치는지 '분해'해 놓은 결과인겁니다.

그리고 바로 이것이 "특이값 분해"!!

 

 

4) 한 걸음 더

이전에  $A^TA$가 n x n이 되면서 '입력축'을 결정하는 행렬이 되고, 반대로 $AA^T$는 m x m으로 '출력축'을 결정하는 행렬이 된다고 말씀드렸던 것 기억하시나요?

 

행렬식까지 싹 다 정리를 해봤으니, 이번엔 $AA^T$가 '출력축'을 결정하는 행렬이 되는 과정을 한번 따라가 봅시다.

 

$ A = U \Sigma V^T $와 $Av_i = \sigma_i u_i$을 가지고 진행해보죠.

 

SVD의 행렬 정의: $ A = U \Sigma V^T $

SVD의 전치 정의: 위 식을 전치하면, $ A^T = (U \Sigma V^T)^T = V\Sigma^TU^T $(괄호 안에 전치를 적용하면 행렬 순서가 싹 뒤집어집니다)

U와 V의 성질: U와 V는 정규직교 행렬(Orthonormal Matrix)입니다.

이는 U의 열벡터들끼리, V의 열벡터들끼리 각각 서로 직교하고 크기가 1이라는 의미입니다.

따라서 다음 관계가 성립합니다: $U^TU = I, \ V^TV = I $ ($I$는 단위행렬)
(여기서 $V^{-1} = V^T$관계도 나옵니다.)

 

자 지금 '입력', '출력'이라는 단어로 두 공간을 설정했었잖아요?

그리고 지금까지 입력에서 출력으로 가는 식을 구한건데.. 그럼 반대도 가능하지 않을까요?

 

출력에서 입력으로!

$ A^TU = V\Sigma^T $

따라서 위의 행렬식을 보면 $A$의 전치행렬에 '출력축'을 곱하면 $\sigma$배가 된 입력축이 나오지 않겠습니까?

 

벡터식으로 보면 바로 $ A^T u_i = \sigma_i v_i $가 나옵니다!

이건 바로 출력에서 입력으로 가는 관계를 나타낸 건데요

 

여기서 처음에 $ v_i^T v_j = 0, \ (Av_i)^T (Av_j) = 0 $ 이렇게 계산했던거 기억나시나요?

 

서로 직교인 두 축을 찾으려고 한 건데요, 이미 우리는 출력축도 직교임을 알고 있습니다.

[$(A^Tu_i)^T (A^Tu_j) = (\sigma_i v_i)^T (\sigma_j v_j) = \sigma_i \sigma_j (v_i^T v_j)$
$V$의 벡터들은 서로 직교하므로, i ≠ j일 때 $v_i^T v_j = 0$ 입니다.
따라서 $(A^Tu_i)^T (A^Tu_j) = 0$ 은 항상 참입니다.]

 

그렇다면 $ (A^Tu_i)^T (A^Tu_j) = 0 $일 것이고 식을 정리하면

$ u_i^T(AA^T)u_j = 0 $

이 나오겠죠!

 

이전에 쭉 진행했었던 논리로 똑같이 $ AA^T $를 풀어내면 결국 $ AA^T $의 고윳값 분해 결과가 됩니다.

여기서 $ AA^T $가 바로 m x m 크기를 가지는 대칭행렬이고, 출력축에서의 변환이 되는 겁니다!

참고로 $ AA^T $의 0이 아닌 고윳값은 $ A^TA $의 0이 아닌 고윳값과 같고, $ AA^T $의 고유벡터는 $u_i$가 됩니다.

 

그리고 둘 중 무엇을 골라도 바로 다른 하나를 계산으로 구할 수 있기 때문에, 우리는 보통 $A^TA$나 $AA^T$ 중 크기가 작은 정방행렬을 골라서 고유값 분해를 하게 됩니다. 왜냐면 고유값 분해 자체가 굉장히 로드가 큰 계산작업이므로, 가능하면 작은 행렬로 수행하는게 이득이기 때문이죠.

 

 

5) 최종정리

다시한번 정리하자면,

1. 특이값 분해하고 싶은 행렬 A를 고릅니다.
2. 1) $ A^TA $ 혹은 2) $ AA^T $중 더 크기가 작은 친구를 골라서 고유값 분해를 합니다.
   1번을 골랐다면 여기서 나오는 고유벡터는 V입니다.
   2번을 골랐다면 여기서 나오는 고유벡터는 U입니다.
3. 두 경우 모두 고윳값은 루트씌워서 크기대로 대각선 나열하면 $\Sigma$죠.
4. 반대편 축을 계산합니다.
   1번을 골랐다면 $ U = AV\Sigma^{-1} $로 $U$를 구해줍니다.
   2번을 골랐다면 $ V = A^T U (\Sigma^T)^{-1} $로 $V$를 구해줍니다.
   ($\Sigma$ 행렬에 전치가 붙는 이유는 $U$와 $V$ 행렬의 크기가 다르기 때문입니다.)
   (Reduced SVD에서는 $\Sigma$행렬이 정방대각행렬이므로 전치행렬대신 그냥 $\Sigma$로 써도 됩니다.)
5. $ A = U \Sigma V^T $ 형태로 정리합니다.
6. 특이값 분해 끝!

 

 

6) 마무리

이제 특이값 분해도 행렬식까지 완성하며 끝을 향해 도달했습니다.

하지만, 다음 포스팅이 하나 남았는데요

지금까지는 벡터식으로 쌓아왔다면, 이제 행렬식을 알기 때문에, 반대로 행렬식으로 특이값 분해를 유도해볼까 합니다.

그리고 전반적으로 행렬의 크기를 시각적으로 보여드리고, 여기서 Full SVD와 Reduced(혹은 Truncated) SVD도 한번 더 살펴볼까 합니다.