https://www.youtube.com/watch?v=_PDyi5BVY-E
1.1 Power method란?
Power method의 목적은 어떤 임의의 행렬(matrix)의 가장 큰 고유값(largest eigenvalue)과 이에 해당하는 고유 벡터(eigenvector)를 찾는 것을 말한다. 이에 대한 내용을 담은 강의 주소를 위에 올려두었다.
이제 power method에 대해 설명할 것이다.
예를 들어, 다음과 같이 n × n 실수행렬 (real matrix)인 A 가 있다고 하자.
이때, matrix A 는 실수 고유값 (real eigenvalues)과 이에 해당하는 eigenvector를 갖고 있으며, eigenvalue의 경우 n개의 분명하게(distinct) 구분되는 실수 값(real value)이다.
이제 이러한 eigenvalues가 다음과 같이 나열(ordering) 된다고 가정하자. 즉, 다음과 같이 "크기가 큰 순서대로 정의되어 있다"고 하자. 여기서 람다(lambda) 값은 eigenvalue에 해당하며, 이를 "양수" 혹은 "음수"라고 정의하는 것은 중요하지 않다. 그 이유는 lambda 값이 갖는 의미는 단순히 vector에 대한 "크기"를 의미하기 때문이다.
이러한 eigenvalues는 다음과 같은 eigenvectors에 대한 값이다. 여기서 eigenvectors는 서로 선형적으로 독립 (linearly independent) 이다. 즉, n개의 linearly independent한 eigenvectors가 있다.
따라서, 어떠한 (any) n × 1만큼의 차원 (dimension)을 갖는 열 벡터 (column vector)로 표현할 때,
위와 같은 n개의 eigenvectors의 선형 결합 (linear combination)으로 표현할 수 있다.
1.2 Power method의 예
예를 들어보자.
다음과 같이 n × 1의 dimension을 갖는 vector x_0 가 있다고 하자. 우리는 이러한 vector를 아래와 같이 e_1 에서부터 e_n 까지의 eigenvectors의 linear combination으로 표현할 수 있다.
여기서 c 는 각 eigenvectors의 크기를 나타내는 " (실상수) real constant"이다.
이를 일반 (generation)식으로 표현하기 위해, 합 기호 (summation notation)를 사용하면 아래와 같다.
그럼 이제, 이러한 vector에 matrix A를 곱하면 어떤 일이 일어날까?
vector x_0 에 matrix A를 곱한 것을 x_1 이라 하자. 그럼, x_1 vector는 다음과 같이 표현할 수 있다.
아래 식에서 빨간색으로 표시한 부분을 자세히 보자.
빨간색 박스안의 e_i 는 "λ_i 라는 eigenvalue를 갖는 A의 eigenvector"를 의미한다.
우리는 이와같은 사실을 이용하여 x_1 vector를 다음과 같다고 표현할 수 있다.
즉, matrix A를 곱한다는 것의 의미는 합 기호 안에 있는 각 수식 (term)들과 "eigenvalue"를 곱하는 것과 같다.
이제 다음과 같은 물음을 할 수 있다.
그럼, matrix A를 p 만큼 제곱하여 곱하면 어떻게 될까?
결론적으로, eigenvalue에 p만큼 제곱한 형태가 된다.
마지막으로, x_p 에 대해서 우리는 어떤 결론을 지을 수 있을까?
맨 처음으로 돌아가서, 우리는 λ_1 이 가장 큰 값을 갖는 고유값(dominant eigenvalue)이라 정의했었다.
따라서, λ_1 에 p 만큼 제곱한 값은 다른 eigenvalue에 p 를 제곱한 값에 비해 "매우 큰 수"가 된다.
따라서, vector x_p 는 다음과 같이 정리할 수 있으며, 첫번째 eigenvalue λ_1 의 값이 다른 eigenvalue에 비해 매우 크기 때문에, 빨간색으로 표현한 부분은 0으로 수렴한다.
결과적으로, 다음과 같이 근사화 (approximation)되어, dominant eigenvalue와 이에 해당하는 eigenvector를 얻을 수 있다.
그럼, 우리가 이제 dominant한 eigenvalue λ_1 에 대해서 문제를 풀려고 한다. 이때, 어떻게 문제에 해당하는 λ_1 을 구할 수 있을까? 다음과 같이 p+1 만큼 제곱하여 x_{p+1} 을 구하고, 바로 위에서 구했던 x_p 를 이용하여 λ_1 을 구할 수 있다. 이에 해당하는 eigenvector e_1 또한 구할 수 있다.
1.3 마무리
λ_1 가 가장 dominant한 eigenvalue이므로, 이를 p만큼 제곱하면 다른 λ 에 비해 매우 큰 수로 정의된다.
즉, 행렬 A 와 벡터 x 의 곱으로 이루어진 식이 가장 dominant한 하나의 값 λ_1 과 이에 해당하는 하나의 벡터 e_1 의 곱으로 표현되며, 이에 해당하는 벡터 e_1 은 eigenvector이다.