행렬 곱셈과 고유값 분해 (eigendecomposition)

행렬 거듭 제곱에 대해서 생각난 것이 있어서 정리합니다.

오늘 알고리즘 스터디에서 행렬 거듭 제곱의 연산비용을 줄이는 이슈에 대해서 잠시 얘기를 했었는데요,

오는길에 생각해보니 선형대수학의 '고유값분해'를 사용하면 훨씬 효과적으로 될 것 같네요.

A라는 정방행렬을 n번 곱하는 A^n라고 한다면,

A^n = AAAAAAA... 이되겠죠. 만약 고유값분해가 가능하다고 한다면(불가능하기도 합니다)

A = SLS^-1 라고 표시됩니다. (S^-1 은 S의 역행렬, L은 대각행렬)

그러면,

A^n = SLS^-1SLS^-1SLS^-1...SLS^-1 = SL^nS^-1  이 되겠죠 (SS^-1 = 단위행렬이므로)

여기서 L은 대각행렬 이므로 n번 거듭 곱해도 일반적인 행렬 연산보다는 훨씬 쉽게 계산 됩니다.

이를 이용해서 A^n 를 계산 할 때마다 고유값분해가 가능한지 확인하고 가능한 시점부터는 알고리즘을 급격히 효과적으로 작성 할 수 있겠네요 :)

http://darkpgmr.tistory.com/105 에 이와 관련된 자세한 내용이 있으니 참고하세요.

추가:

octave를 깔 일이 있어서 깔고 생각난 김에 octave로 행렬의 거듭제곱을 해보니 바로바로 결과가 나옵니다.

octave:16> A = [0.5, 0.3; 0.4, 0.7]
A =

   0.50000   0.30000
   0.40000   0.70000

octave:17> A ** 2
ans =

   0.37000   0.36000
   0.48000   0.61000

octave:18> A ** 1000
ans =

   1.2028e-18   1.3849e-18
   1.8465e-18   2.1261e-18

어떤 최적화 기법(위와 같은)이 있지 않을까 추측해봅니다.