Mathematics에서 Power Iteration(혹은 power method라고 부름)은 eigenvalue algorithm이다.

Diagnoalizable Matrix A가 주어지면 이 알고리즘은 가장 큰 값을 가지는 A에 대한 Eignevalue인 lambda와 해당 lambda의 eigenvector인 0이 아닌 vector v를 생성를 생성한다.

Power Iteration은 매우 간단한 알고리즘이지만 converge가 매우 느리다.

벡터와 행렬 곱으로 알고리즘의 가장 시간이 걸리는 작업이며, 적절한 구현과 매우 큰 희소 행렬에 효과적이다.

Code Imp 1.

import numpy as np

def power_iteration(A, num_simulations):
    # Ideally choose a random vector
    # To decrease the chance that our vector
    # Is orthogonal to the eigenvector
    b_k = np.random.rand(A.shape[1])

    for _ in range(num_simulations):
        # calculate the matrix-by-vector product Ab
        b_k1 = np.dot(A, b_k)

        # calculate the norm
        b_k1_norm = np.linalg.norm(b_k1)

        # re normalize the vector
        b_k = b_k1 / b_k1_norm

    return b_k

power_iteration(np.array([[0.5, 0.5], [0.2, 0.8]]), 10)

Code Imp 2.

Finding the eigenvalue:

• if  v is an eigenvector of A, then its eigenvalue is

$$ \lambda = \frac{v^TA^Tv}{v^Tv}=\frac{(Av)^Tv}{v^Tv} $$

• This is called Rayleigh Quotent
• proof: suppose lambda is eigenvalue of A and v is its eigenvector

$$ \frac{(Av)^Tv}{v^Tv} = \frac{\lambda v^Tv}{v^Tv} = \lambda $$

def eigenvalue(A, v):
    Av = A.dot(v)
    return v.dot(Av)

def power_iteration(A):
    n, d = A.shape

    v = np.ones(d) / np.sqrt(d)
    ev = eigenvalue(A, v)

    while True:
        Av = A.dot(v)
        v_new = Av / np.linalg.norm(Av)

        ev_new = eigenvalue(A, v_new)
        if np.abs(ev - ev_new) < 0.01:
            break

        v = v_new
        ev = ev_new

   return ev_new, v_new

Power Iteration Process