Don't panic !: Eigenvector(고유벡터) 와 Eigenvalue(고유값) 구하기

책속에서 존재하는 eigenvector와 eigenvalue구하기의 난제는 다항식을 푸는 문제로 귀결된다.
하지만, 컴퓨터로 구현하고자 한다면 다항식을 푸는 문제 자체도 대단히 어려운 일이다.
해가 있는지 (허근인지 실근인지) 무엇보다도 소인수 분해와 같은 암호 해독과 같이 어려운 문제에 봉착하게 된다.

그래서 다항식 해법으로 접근하지 않고 eigenvetor와 eigenvalue의 property(속성)을 이용하여 반복적인 연산을 통하여 실제 eigenvector와 eigenvalue에 수렴할 수 있는 근접한 값을 찾아 내는 방법을 사용한다. 여기에는 여러가지 방법들이 존재한다. power iteration method, shifted inverse iteration method, Rayleigh quotient method, simultaneous iteration method, QR method 이와 같은 반복적인 연산을 이용한 방식은 eigenvalue와 eigenvector가 존재한다는 가정하에 다음과 같은 속성을 이용한다.

존재한다고 가정한 eigenvalue들은 {q_{i}}이고 eigenvalue들은 {lambda_{i}}이다.
여기서,

 | lambda_{1} | > | lambda_{2} | > ... > | lambda_{n} |

의 조건을 갖는다.

그리고 추정하고자하는 eigenvector는 실제 eigenvector의 span으로 표현할 수 있다. 왜냐하면 eigenvector는 해당 공간의 basis가 되기 때문이다. 그래서 다음과 같이 eigenvector의 linear combination으로 표현할 수 있다.

  v_{0} = c_{1} * q_{1} + ... + c_{n} * q_{n}.

이와같은 추정치가 eigenvector라고 한다면 실제의 eigenvector의 정의에 해당하는 조건식에도 부합되어야한다.

 A * x = lambda *x

에서 부터

 A * v_{0} = c_{1} * lambda_{1} * q_{1} + ... + c_{n} * lambda_{n} * q_{n}

그리고

  A^k * x = lambda^k * x

의 확장된 속성에 이르기 까지로 부터 다음과 같이 유도 된다.

 A^k * v_{0} = c_{1} * lambda_{1}^k * q_{1} + ... + c_{n} * lambda_{n}^k * q_{n}  
          = lambda_{1}^k * [ c_{1} * q_{1} + c_{2} * (lambda_{2} / lambda_{1})^k * q_{2} + ... + c_{n} * (lambda_{n} / lambda_{1})^k * q_{n} ]

즉 위와 같은 방정식으로 전제할 수 있다. 여기서 주의 깊게 살펴보아야할 부분은 (lambda_{i} / lambda_{1})^k의 부분이다. 분모에 해당하는 lambda_{1}는 가장 큰 절대값을 갖는 eigenvalue이기 때문에 k값이 커질 수록 0의 값으로 수렴하게 된다. 그럼 나머지 항들은 사라지고 lambda_{1}에 해당하는 eigenvector의 값으로 v_{0}의 값은 수렴하게 된다. 기본적으로 이러한 개념하에 위의 반복적인 연산이 이루어진다.

그리고 이러한 기본 개념하에 power iteration방식과 shifted inverse iteration방식이 설명된다. 기타 다른 방식들도 이 방식에서 확장해 나아가는 형식을 취하고 있다.

power iteration

이 방식은 eigen value중 가장 큰 값에 해당하는 eigen vector만 구할수 있다.

psudo code of power iteration

 v = random vector with its norm "1"  
 do {  
  w = A * v;  
  if (w == v) break;  
  v = w / |w|;  
 } while (1);

inverse iteration

이 방식은 eigen value중 가장 작은 값에 해당하는 eigen vector만 구할 수 있다. power iteration 방식은 A의 eigen value가 lambda_{i}라면 A^{-1}의 eigen value이 1/lambda_{i}가 되는 특성을 이용하여 A^{-1}에 power iteration을 적용한다.

psudo code of inverse iteration

 v = random vector with its norm "1"  
 do {  
  w = A^{-1} * v;  
  if (w == v) break;  
  v = w / |w|;  
 } while (1);

shifted inverse iteration

A의 특정 eigen value에 근접하는 값을 임의로 선택한 값이 u라고 하면 (A - u * I)의 eigen value은 lambda_{i} - u가 된다. 그리고 (A - u * I)에 inverse iteration을 적용하면 u값에 근접하는 eigen value에 해당하는 eigen vector를 구할 수 있다.

psudo code of shifted inverse iteration (finding eigen vector corresponding to eigen value closed to u)

 v = random vector with its norm "1"  
 do {  
  w = (A - u * I)^{-1} * v;  
  if (w == v) break;  
  v = w / |w|;  
 } while (1);

Rayleigh quotient iteration

이 방식은 shifted inverse iteration에서 u값과 v값을 동시에 근사화 시켜서 연산 시간을 줄여주는 방식이다.

psudo code of Rayleigh quotient iteration (finding eigen vector corresponding to eigen value closed to u)

 v = random vector with its norm "1"  
 do {  
  w = (A - u * I)^{-1} * v;  
  if (w == v) break;  
  v = w / |w|;  
  u = v^{T} * A * v;  
 } while (1);

Simultaneous iteration

이 방식은 이전의 방식들이 한번에 하나의 eigen vector만을 구할 수 있지만 한번에 모두 구할 수 있다.

psudo code of simultaneous iteration

  V = [v_{i} : random vector with its norm "1" and i = 1..n]; // QR decomposite Q * R = QR_decomposite(V); do {  W = A * Q;  
  Q * R = QR_decomposite(W);  
  if (Q is not changed) break;  
 } while (1);  
 the columns of Q will converge towards a basis of eigenvectors of A

The QR method

이 방식은 QR 분해를 반복적으로 수행하는 것이다. 이론이고 뭐고 orthogonal column vector들은 항상 Q 행렬에 모이게 되고 Upper triangular 행렬은 R에 모이는 QR 분해를 Q 행렬에 반복적으로 recursive하게 적용하면 뭔가 유일한 orthogonal columns vector가 나올 법하게 느껴진다.

psudo code of QR method

 B = A;  
 do {  
  Q * R = QR_decomposite(B);  
  B = R * Q;  
  if (Q is not changed) break;  
 } while (1);

Don't panic !

2012년 1월 25일 수요일

Eigenvector(고유벡터) 와 Eigenvalue(고유값) 구하기