'SvD'에 해당되는 글 1건

  1. 2016.04.21 [선형대수] 특이값 분해 (SVD, Singular Value Decomposition) (5)

지난번 포스팅에서는 행과 열의 개수가 같은 정방행렬(square matrix)에 대해 고유값 분해(eigenvalue decompositon)를 활용한 대각화(diagonalization)와, 이를 마아코프 과정(Markov Process)의 안정상태확률 계산에 적용한 사례에 대해서 소개하였습니다.

 

복습하는 차원에서 고유값 분해에 대해서 정리해보면 아래와 같습니다. 

 

  • 고유값 분해 (eigenvalue decomposition)

 

고유값 분해는 n*n 정방행렬 (n by n square matrix)에 대해서만 적용 가능하다는 점과 가운데에 D 행렬에 고유값이 들어가 있다는 점은 다시 한번 상기하시기 바랍니다.  m*n 직사각행렬(m by n rectangular matrix)에 대해서는 고유값 분해는 사용할 수 없다는 뜻입니다.

 

 

 

 

이번 포스팅에서는 실수(real number)나 복소수(complex number)로 이루어진 공간의 원소로 이루어진 m개의 행과 n개의 열을 가진 모든 직사각행렬 (rectangular matrix)에 폭넓게 사용 가능한 특이값 분해 (SVD, singular value decomposition)에 대해서 알아보겠습니다.

 

특이값 분해는 행렬의 스펙트럼 이론을 임의의 직사각행렬에 대해 일반화한 것으로 볼 수 있습니다. 스펙트럼 이론을 이용하면 직교 정사각행렬을 고유값을 기저로 하여 대각행렬로 분해할 수 있습니다. (* 위키피디아) 

  • 스펙트럼 분해 (spectral decomposition)

p*p 대칭행렬 A에 대한 스펙트럼 분해(spectral decomposition)는 다음과 같습니다.  p*p 대칭행렬 A는 직교행렬 P에 의해 대각화(diagonalization)된다고 합니다.

 

 

이때 를 만족하는 직교행렬 P는 로 이루어지며, (람다, lambda)는 A의 고유값(eigenvalue)들로만 이루어진 대각행렬(diagonal matrix)인

 입니다.  대각행렬 이 성립합니다.

 

 

 

위의 스펙트럼 분해 (혹은 분광분해)를 일반화한 특이값 분해는 아래와 같습니다. 

 

 

 

  • 특이값 분해 (SVD, Singular Value Decomposition)

m*n 직사각행렬 A에 대한 특이값 분해(SVD, Singular Value Decomposition)는 아래와 같이 나타낼 수 있습니다.

 

 

 

행렬 A의 계수(rank)가 k 라고 할 때,

 

를 고유값분해(eigenvalue decomposition)로 직교대각화하여 얻은 m*m 직교행렬 (orthogonal matrix)이며, 특히를 좌특이벡터(left singular vectors, gene coefficient vectors) 라고 합니다.

 

 

는  를 고유값분해로 직교대각화하여 얻은 n*n 직교행렬이며, 특히 를 우특이벡터(right singular vectors, expression level vectors)라고 합니다.

 

 

는 (의 0이 아닌 고유값이 일 때)  를 대각성분으로 가지고 나머지 성분은 0을 가지는 m*n 직사각 대각행렬(diagonal matrix) 입니다.

 

 

 

 

m*n 직사각행렬 A의 특이값 분해 를 다시 한번 풀어서 쓰면 아래와 같습니다.

 

 

 

 

위의 식에서 특이값(singular value)는 가 됩니다.

 

 

참고로,

U, V가 직교행렬(orthogonal matrix)이면 가 성립합니다. 

직교행렬(orthogonal matrix) Q는 다음을 만족하는 정방행렬이기 때문입니다.

 

 

 

 

서두에서 정방행렬에 국한된 고유값 분해보다 모든 m*n 행렬에 적용가능한 특이값 분해가 일반화면에서 활용성이 더 넓다고 했는데요, 이 둘이 사실은 서로 관련이 되어 있습니다.

 

 

 

  • 특이값 분해와 고유값 분해의 관계

아래의 수식 전개를 보면 확인할 수 있는데요, 서두에서 소개했던 고유값 분해 형식()과 같아졌습니다.  m*n 행렬 A의 특이값 분해의 U는  의 고유벡터(eigenvector)이고, V는의 고유벡터(eigenvector) 이며, A의 0이 아닌 특이값들의 제곱() 은 , 의 고유값과 같음을 알 수 있습니다.

 

결국 SVD를 계산한다는 것은 의 고유벡터와 고유값을 구하는 것이라는 것을 알 수 있습니다.

 

 

 

다음으로, 특이값 분해의 기하학적인 의미를 살펴보겠습니다.

  • 특이값 분해의 기하학적인 의미 (visualization of SVD)

아래의 그림을 가지고 의 특이값 분해가 가지는 선형변환의 의미를 기하학적으로 설명하자면, 먼저 직교행렬 에 의해서 원 행렬 M이 회전(방향 변환)을 하게 되며, 에 의해서 크기가 달라졌고 (scale 변환), 다시 직교행렬 에 의해서 에 의한 회전과는 반대로 회전(방향 변환)하였습니다.

 

* 그림 출처 : https://en.wikipedia.org/wiki/Singular_value_decomposition

 

위의 설명을 애니메이션을 넣어서 설명해주는 그림은 아래와 같습니다.

 

Singular value decomposition

* 출처 : By Kieff (Own work) [Public domain], via Wikimedia Commons

 

 

고유값 분해를 통한 대각화의 경우 고유벡터의 방향은 변화가 없고, 크기(scale 변환)만 고유값(eigenvalue) 만큼 변한다고 설명드렸었습니다.  반면, 특이값 분해는 위의 그림 결과를 보면 처음의 행렬 U, V^T에 의해 M이 방향이 변하고, Σ 특이값(singular values)들 만큼의 크기(scale)가 변했음을 알 수 있습니다.

 

 

  • Redeced SVD (Singular Value Decomposition)

위에서 SVD(Singular Value Decomposition)를 설명할 때 full SVD를 설명해 드렸습니다만, 실전에서는 많은 경우 아래 그림에서 소개드린 것처럼 reduced SVD를 합니다. full SVD 대비 reduced SVD는 특이값(singular value) 들 중에서 0인 것들을 제외하고 SVD를 한다는 점이 서로 다릅니다.

 

 

 

아래의 그림을 보면 조금 더 이해하기가 쉬울텐데요, 빨간색 점선으로 표시한 부분을 제외하고 행렬 A의 계수(rank) k 개 만큼의 특이값들을 가지고 SVD를 진행하는 것이 reduced SVD 입니다.

 

 

  • 특이값 분해 예제 (example of full SVD)

이해를 돕기 위해서 4 by 2 직사각행렬 (rectacgular matrix) A를 가지고 (full) SVD 계산 예를 들어보겠습니다.  아래 예에서의 고유값과 고유벡터 계산은 R 분석툴을 사용했습니다.  손으로 푸는 방법은 ☞ [선형대수] 고유값, 고유벡터 구하기 (calculation of eigenvalue and eigenvector) 를 참조하시기 바랍니다.

 

 

 

4 by 2 행렬 을 가지고 해보겠습니다.

 

특이값 분해가  라고 했는데요,

 

(1) 먼저 의 고유벡터(eigenvectors)인 U를 구해보겠습니다.

 

 

 

 

위의 풀이에서 사용한, R로 의 고유벡터를 구해서 U를 구하는 방법은 아래와 같습니다.

 

> A <- matrix(c(3, 2, 0, 0,  6, 3, 0, 0), nc=2, byrow = FALSE)
> A
     [,1] [,2]
[1,]    3    6
[2,]    2    3
[3,]    0    0
[4,]    0    0
> t(A)
     [,1] [,2] [,3] [,4]
[1,]    3    2    0    0
[2,]    6    3    0    0
> ##--- (1) calculation of U
> # A%*%t(A)
> W_1 <- A%*%t(A)
> W_1
     [,1] [,2] [,3] [,4]
[1,]   45   24    0    0
[2,]   24   13    0    0
[3,]    0    0    0    0
[4,]    0    0    0    0
> 
> 
> # eigenvalue, eigenvector of W
> eigen(W_1)
$values
[1] 57.8444102  0.1555898  0.0000000  0.0000000

$vectors
          [,1]       [,2] [,3] [,4]
[1,] 0.8816746 -0.4718579    0    0
[2,] 0.4718579  0.8816746    0    0
[3,] 0.0000000  0.0000000    0    1
[4,] 0.0000000  0.0000000    1    0

> 
> # U
> U <- eigen(W_1)[[2]] # eigenvectors
> U
          [,1]       [,2] [,3] [,4]
[1,] 0.8816746 -0.4718579    0    0
[2,] 0.4718579  0.8816746    0    0
[3,] 0.0000000  0.0000000    0    1
[4,] 0.0000000  0.0000000    1    0

 

 

 

 

(2) 다음으로,  의 고유벡터(eigenvectors of A^T*A)  를 구해보겠습니다.  위의 (1)번 풀이 과정과 동일합니다.

 

 

R로 풀이한 것은 아래와 같습니다.

 

> > ##---- (2) calculation of V^T > # t(A)%*%A > W_2 <- t(A)%*%A > W_2 [,1] [,2] [1,] 13 24 [2,] 24 45 > > # eigenvalue of W > eigen(W_2) $values [1] 57.8444102 0.1555898 $vectors [,1] [,2] [1,] 0.4718579 -0.8816746 [2,] 0.8816746 0.4718579 > > # V > V <- eigen(W_2)[[2]] # eigenvectors > V [,1] [,2] [1,] 0.4718579 -0.8816746 [2,] 0.8816746 0.4718579 

 

 

 

(3) 다음으로, 의 고유값(eigenvalue)의 제곱근(square root)을 특이값(singular value) 대각원소로 가지고 나머지는 '0'인 대각행렬 Σ 를 구해보겠습니다.

 

 

R로 고유값에 square root를 취해서 특이값(singular value) 구하는 절차는 아래와 같습니다.

 

> ##--- (3) calculation of Σ
> # square root of eigenvalues
> W_2_eigenvalue_sqrt <- sqrt(eigen(W_2)[[1]])
> W_2_eigenvalue_sqrt
[1] 7.6055513 0.3944487
> 
> S <- matrix(rep(0, 8), nc=2, byrow=F) # all zeros, temp matrix
> S
     [,1] [,2]
[1,]    0    0
[2,]    0    0
[3,]    0    0
[4,]    0    0
> 
> S[1,1] <- W_2_eigenvalue_sqrt[1] 
> S[2,2] <- W_2_eigenvalue_sqrt[2]
> S
         [,1]      [,2]
[1,] 7.605551 0.0000000
[2,] 0.000000 0.3944487
[3,] 0.000000 0.0000000
[4,] 0.000000 0.0000000 

 

 

 

(4) 위에서 구한 U, V^T, Σ 를 종합하면 끝이네요.

 

 

 

R 로 그동안 풀었던거 다시 한번 불어와보면 아래와 같습니다.

 

> # overall (aggregation)

> > A # 4 by 2 rectacgular matrix [,1] [,2] [1,] 3 6 [2,] 2 3 [3,] 0 0 [4,] 0 0 >

> U # eigenvectors of A*t(A) [,1] [,2] [,3] [,4] [1,] 0.8816746 -0.4718579 0 0 [2,] 0.4718579 0.8816746 0 0 [3,] 0.0000000 0.0000000 0 1 [4,] 0.0000000 0.0000000 1 0 >

> S # square root of eigenvalues of t(A)*A [,1] [,2] [1,] 7.605551 0.0000000 [2,] 0.000000 0.3944487 [3,] 0.000000 0.0000000 [4,] 0.000000 0.0000000 >

> V # eigenvectors of t(A)*A [,1] [,2] [1,] 0.4718579 -0.8816746 [2,] 0.8816746 0.4718579 > > SVD_of_A <- U %*% S %*% t(V) > SVD_of_A [,1] [,2] [1,] 3.328201 5.824352 [2,] 1.386750 3.328201 [3,] 0.000000 0.000000 [4,] 0.000000 0.000000 

 

 


많은 도움이 되었기를 바랍니다.

 

도움이 되었다면 아래의 '공감 ♡'를 꾸욱~ 눌러주세요. ^^

 

Posted by R Friend R_Friend

댓글을 달아 주세요

  1. 임태준 2017.05.08 18:49  댓글주소  수정/삭제  댓글쓰기

    마지막에 U * 시그마* V에서 2번째 컬럼이 왜 -로 된거죠~?

    • R Friend R_Friend 2018.01.04 22:33 신고  댓글주소  수정/삭제

      안녕하세요 임태준 님,
      댓글 달린 줄 모르고 있다가 한참이나 지나서 이제서야 봤네요. 늦어서 죄송합니다. 댓글 남겨주셔서 감사합니다.

      제가 실수로 V를 transpose 하는 걸 빼먹어서 잘못 계산된 것이었습니다.
      (기존 U*Sigma*V => 수정 U*Sigma*t(V) )

      본문에 잘못되었던 부분을 바로 잡아서 수정해놓았습니다.

      참고로, 원래의 행렬 A와 일부 차이가 나는 것은 특이값분해 과정에서 일부 오차에 의한 것입니다.

      댓글 감사합니다.

  2. songhunhwa@naver.com 2018.10.30 18:03  댓글주소  수정/삭제  댓글쓰기

    선생님, 정말 훌륭한 내용의 블로그 올려주셔서 감사드립니다. 선형대수 카테고리의 모든 글을 읽어보았는데, 이전에 손에 잡힐듯 안 잡혔던 내용들이 너무 많아서 고생 했었습니다. 이제야 다 이해가 됩니다. 퍼즐조각이 딱딱 맞아 들어가는 이느낌이 저를 행복하게합니다. 다시한번 감사드립니다.

  3. 나그네 2019.01.25 01:21  댓글주소  수정/삭제  댓글쓰기

    안녕하세요.
    주성분 분석 중 알게 되었습니다.
    덕분에 주성분 분석 C = AB' = UDV' 를 손으로 풀 수 있게 되었습니다.
    감사합니다. 꾸벅
    질문이 있습니다.
    행렬 위에 첨자 m은 각 원소를 m 제곱 하라는 기호인지요?