행렬 분해(Decomposition) - SVD 분해

 

 

성균관대학교 행렬이론 연구실

 

Made by Sang-Gu Lee with MyungGuk Baik and DukSun Kim

 

 

 

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

 

(복소)행렬 는 다음과 같이 분해 될 수 있다.  =   는 유니타리(unitary)이고 는 대각(diagonal)행렬이다. 만약 행렬 가 실수성분을 가지면 ,는 실수의 직교성(real orthogonal) 을   갖는다. 이러한 분해를 특이값 분해(singular-value decomposition), 또는 행렬 SVD라 부른다.

앞으로의 MATHEMATICA를 이용하기 위한 이론적 배경의 준비와 MATHEMATICA에서 구현되는 SVD 의 구동 원리에 대해서 알아보기로 하자.

 

 

 [정리] SVD(Singular Value Decomposition)

 

  계수(rank)가 실계수 행렬 에 대하여, 행렬 를  

로 분해할 수 있다. 여기서 행렬 는 대각선 성분이 실수로서 아래의 성질을 만족하는 대각성분이

,

대각행렬이고, 는 각각 , 인 직교행렬들이다.

 

  이때, 행렬 의 대각선성분 를 행렬 의 singular values라 하며,은 대칭행렬(symmetric) 의 고유값이 되며, 이들은 유일하게 정해진다. 한편, 행렬 의 열(column)들은 의 고유벡터들이며 각각을 행렬 의 left singular vectors라 하고, 행렬 의 열(또는 의 행)들은 의 고유벡터들이며 각각을 행렬 의 right singular vectors라 한다.

 

 

특이값 분해(SVD) 정리  를 다시 쓰면 다음과 같다.

 

정리 3.1 행렬 × 의 실계수 행렬이라 하자. 그러면 다음과 같은 직교행렬 가 존재한다.

    

은 비가역의 대각(nonsingular diagonal) 행렬이고 행렬 의 대각성분은 모두 음이 아니며 증가하지 않는(nonincreasing) 순서로 배열 할 수 있다.

 

정의 3.1 안의 행렬 의 대각성분들을 행렬 특이값(singular values) 이라 하고, 의 열을 좌특이벡터(left singular vectors), 에 대해서는 우특이벡터(right singular vectors) 라고 한다.

 

Singular Value Decomposition의 유일성

× 의 행렬 A에 대하여, (, )=의 특이값(singular value)이라 하자. 행렬 의 계수(rank)를 이라 하면, 개의 positive singular values가 있다. 이들은 (또는 )의 이 아닌 고유값(eigenvalue)의 양의 제곱근이다. 만약 이면, (-)개의 특이값이 이 된다. 그러므로 특이값은 유일하다. 그러나 특이 벡터는 유일하지 않다. 예를 들어, 행렬 의 특이값이 ()의 상수배이면 행렬 의 열은 의 고유값 상수배한 값에 의한 고유벡터에 의해서 일차결합(span)되는 공간의 직교기저(orthonormal basis)로써 나타내어진다.

 

예제 3.1 다음 행렬 의 특이값과 특이벡터를 구하여라.

 

 

1. 특이값을 계산하기 위하여, 의 고유값을 계산하면 42.8600과 0.1400 이 된다.

 

2. 을 계산하기 위한 단계로서, 의 고유값들의 고유벡터로 구성된 행렬을 라 하자. = 2이기 때문에 이 된다.

  

3. , 이고, 이 unitary 행렬이 되게 하는 벡터라 하자. 그럼 가 된다.

 

4. 따라서 행렬 의 SVD의 ,  그리고 는    다음과 같다.

, 그리고

 

정리 3.2 행렬 × ( )의 SVD라 하고 을 행렬 의 차수(rank)라 하자. 그러면

  1.

  2.

 

증명)

            

는  대각 성분이 ×  대각행렬이다. 따라서

유사한 방법에 의하여

 

따름정리 3.1 × 행렬 가 비가역(nonsingular)이기 위한  필요충분조건은 행렬의 특이값이  이 아니어야 한다.

 

증명) ()=(det )이므로 행렬 가 비가역이기 위한 필요충분조건은 가 비가역 이어야 한다. 그런데 행렬이 비가역이기 위한 필요충분조건은 그것의 고유값이 이 아니어야 하므로, 정리 3.2에 의하여 특이값이 이 아니어야 한다.

 

 

 

[참고] The Reduced Singular Value Decomposition방식

 

 실제로 MATHEMATICA에서는 빠른 Singular Value Decomposition을 계산하기 위하여, zero singular value를 제외한다. 이 경우, 각 행렬에서는 zero singular의 값만큼 즉, U에서는 column과 V에서는 row를 빼 주고 계산하게 된다. 이것이 The Reduced Singular Value Decomposition방식의 원리인데, 다음 예를 이용하여 확인해보자.

  MATHEMATICA에서 "In[1]="는 각종 식과 값의 입력을 뜻하면, "Out[1]="는 입력값에 대한 결과이다. 곱셈은 "."을 쓰거나 공백을 사용한다.

임의로 행렬을 정하여 U, S, VT로 정의해 주자.

          

In[1]=

U=N[{   { 1/2, -1/2,  1/2,  1/2},  

        { 1/2,  1/2, -1/2,  1/2},

         { 1/2,  1/2 ,  1/2, -1/2},  

        { 1/2, -1/2, -1/2, -1/2}}]

S=N[{    {12,  0, 0},

         { 0,.05, 0},

         { 0,  0, 0},

         { 0,  0, 0}}]

VT=N[{{2/3,  2/3,  1/3},

        {2/3, -1/3, -2/3},

        {1/3, -2/3,  2/3}}]

         ←입력값이 소수로 처리되었다

 

     

In[4]= A = U.S.VT

 ←U, S, VT를 곱하였다.

 

← 결과를  행렬 형태로 변환시킨다.

 

위의 행렬에서 Reduced Method를 사용할 수 있는지 해 보자.

          

In[6]= VrT = Take[VT,2]

           ←Zero singular value가 두개이므로 먼저 VT에서

           0이 아닌 singular value에 대응하는 2열만을 고른다.

 

TakeColumns라는 함수를 쓰기 위해서 다음의 Package를 사용하자.

        In[7]= Needs["LinearAlgebra`MatrixManipulation`"]

 

        In[8]= Sr = TakeColumns[Take[S,2],2]

             ← S의 처음 2열을 택한 후, 다시 0을 제외한 2행을

             택하여 Sr로 정의한다.

 

        In[9]= Ur = TakeColumns[U,2] ←U의 2열을 택한다.

        In[11]= Ur.Sr.VrT // MatrixForm  

        ←새로 정의된 Ur, Sr, VrT를 곱하여

          MatrixFrom으로 살펴본다.

 

  Out[11]은 Reduced Method를 사용하여 계산된 결과이다. 처음의 A와 비교해 보자.

        In[12]= Chop[A-Ur.Sr.VrT]//MatrixForm

        Out[12]//MatrixForm=

             

0 행렬이 나왔으므로 동일한 결과임을 알 수 있다. 따라서 Reduced Method나 일반적인 SVD는 동일한 형태를 갖는다. 이러한 방법으로 계산하는 SVD를 Reduced SVD algorithm이라 한다.

  이러한 Reduced SVD Algorithm은 일반적인 SVD Algorithm과 달리 일단 zero singular value를 배제하고 계산함으로서 행렬 간의 속도를 굉장히 많이 향상시킬 수 있을 뿐만이 아니라 일반적으로 SVD가 많이 쓰이는 압축기술에도 유용하게 사용될 수 있다.

 

 

3.2 특이값(Singular Values)의 민감성(sensitivity)

 

행렬 의 특이값의 제곱은 실수의 대칭(symmetric) 행렬 의 고유값이 되고, 대칭행렬은 고유값의 간섭(perturbations)에 민감하지 않으므로(insensitive) 특이값도 민감하지 않다. 즉, 행렬의 특이값은 불량조건이 아니다(well-conditioned).

 

정리 3.3 특이값에 대한 간섭(perturbation) 정리

행렬 , 을 두개의 × 행렬이라 하자(). , (=1,2,...,)을 각각 행렬 , 의 특이값이라 하자(증가하지 않는 순서). 그러면, 각각의 에 대하여 | - |이 성립한다.

 

 

3.3 The Singular Value Decomposition과 행렬 구조(Structure)

 

정리 3.4 (Norms과 Condition Number)

× 행렬 에서 개의 특이값을 이라 하자, 그러면

1. = =

2. =  

3. = = , (×이고 비가역)

4. ×이고 비가역성 일 때, Cond() = = =

 

증명)

1. = = = max() = =

2. = = =

3. 의 가장 큰 특이값은 이 된다.

4. 위의 1, 3에 의하여   =

 

정리 3.5 × 행렬 에서 개의 특이값을 이라 하자, 그러면 행렬 는 다음과 같다.

  

 

정의 3.2 를 행렬 outer-product expansion 이라 한다.

 

Numerical Rank

행렬 의 수치적계수( )는 상대적으로 큰 특이값에 의하여 결정된다. 이 값을 이라고 하면 행렬 의 수치적계수( )는 이 된다.

 

 

 

SVD Visualization in MATHEMATICA

 

  MATHEMATICA에는  MATLAB과는 달리 자체에 SingularValues라는 내장함수(Built-in Function)가 있다. 이 함수를 이용하면 손쉽게 임의의 행렬의 Singular Value값을 구할 수 있다.

먼저 임의의 행렬을 정의하기 위하여 다음과 같은 임의의 행렬을 정의할 수 있는 함수인 randint함수를 정의하고 시작하자.

        

In[1]= Clear[randint]

      randint[m_,n_,k_:9] :=

      Table[ Random[Integer,{-k,k}], {m},{n}]

 

      randint[m_] := randint[m,m]

 

      randint[m_, n_Integer?Positive, k_, r_Integer?Positive] /;

                    r<=Min[m,n] :=

              Module[{p,A,done=False},

            p = Ceiling[k/r];      While[Not[done],

         A = randint[m,r,p].randint[r,n,1];

         A = Map[(If[Abs[#]<=k,#,0])&,A,{2}];

         done = (n - Length[NullSpace[A]] == r)];

      A]

 

그러면 -9에서 9까지의 Random한 정수를 성분으로 하고 계수(rank)가 5인 8×6 행렬을 만들어 보자.

←8은 8행, 6은 6열, 9는 절대값의 범위,

                                     5는 rank이다.

Singular Value와 Singular Value Decomposition에 의해 구할 수 있는 orthogonal matrix인 U와 V를 구하기 위해 다음 함수를 실행시킨다.

←"Tolerance→0"은 가능한 작은 singular   value를 구하라는 option이다.

          Out[42]=

 **

 

참고로 SVD에 의해 나온 값의 모든 행렬은 Tranpose과 가 취해져서 나온다. 따라서 원래의 행렬을 구할 때에는 U의 transpose와 VT를 그대로 곱하여 우리가 알고있는 알고리즘의 반대를 적용하면 된다.

        Out[43]//MatrixForm=

 

U는 분명 우리가 알고 있는 대로라면 8x8행렬이 나와야 하지만 8×6이다. 이는  MATHEMATICA에서 연산의 속도를 빨리 하기 위해서 Reduced SVD Algorithm을 사용하고 있기 때문이다. 따라서 우리가 알고 있는 일반적인 SVD를 이론적으로 보이기 위해서는 따로 알고리즘을 구현해야 한다.

 

Singular값이 점점 감소함을 볼 수 있다.

 

        Out[45]//MatrixForm=

      

VT(V의 Transpose)는 6x6행렬의 거의 정확한 형태가 나온다.

 

←U의 transpose와  sigs의 대각행렬, VT를 곱한 결과를 Matrix형태로 보자

 

이 행렬의 결과가 맞는지 보기 위하여 12자리 이하의 작은 수는 0으로 하는 Chop라는 함수를 써서 살펴보자.

 

 

 

이는 원래 행렬인 A와 같다. 실제로 빼보면

 

정확히 0행렬이 나온다.

 

다른 예제를 해 보자.

←4행 3열의 rank가 1인 -7에서 7까지의 성분으로 만든 임의의 행렬 A1

   ←A1을 SVD하여 U1,sigs1,VT1으로  정의하자.

←singular value도 1개이다.

 ←U1의 transpose,           sigs1의    대각행렬, V T1을 곱하여  Matrix 형태로 만든다.

 

역시 정확히 맨 처음 선언한 A1 행렬의 값이 나온다.

이상에서 살펴본 바와 같이 MATHEMATICA를 활용하면 SVD이론을 임의로 주어진 행렬에 적용하여 그 분해되는 과정을 단계별로 살펴볼 수 있다. 이는 이론의 전개와 더불어 실제로 분해되는 과정을 software를 이용하여 확인함으로서 학습동기와 숙지도를 높이는데 큰 역할을 한다고 생각한다.

 

 이제 이를 이용하여 실제로 이미지의 압축과 처리를 할 수 있다.

 References

 

Biswa Nath Datta, Numerical Linear Algebra and Applications, An International Thomson Publishing Company, (1995)

 

Horn & Johnson, Matrix Analysis, Cambridge Univ. Press, 1993,

 

Golub and Van Loan, Matrix Computations,  

 

********************************************