rambo

Power method及其应用

2015年8月16日 Numerical Optimization 0 Comments

Power method是一个特征值算法 。对于一个对称阵，求最大特征值对应的特征向量。

  • 给定一个n\times n的矩阵A，该算法会产生\lambda（特征值）和非零向量v（特征向量）使得Av=\lambda v。
  • 该算法不需要求解矩阵分解，所以适用于A是一个很大的稀疏矩阵。
  • 每一轮迭代，find only one eigenvalue (the one with the greatest absolute value) and it may converge only slowly.

Its extension to the inverse power method is practical for finding any eigenvalue provided that a good initial approximation is known.

一些求解特征值的方法可以快速收敛，但精度有限。

Power Iteration算法：

初始点的选择(an approximation to the dominant eigenvector or a random vector)

QQ截图20150816153728

伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for each(''simulation'') {
    // calculate the matrix-by-vector product Ab
    for(i=0; i<n; i++) {
         tmp[i] = 0;
         for (j=0; j<n; j++)
              tmp[i] += A[i][j] * b[j];
             // dot product of i-th row in A with the column vector b
    }
 
    // calculate the length of the resultant vector
    norm_sq=0;
    for (k=0; k<n; k++)
         norm_sq += tmp[k]*tmp[k];
    norm = sqrt(norm_sq);
 
    // normalize b to unit vector for next iteration
    b = tmp/norm;
}

 

结论：If we assume A has an eigenvalue that is strictly greater in magnitude than its other eigenvalues and the starting vector b_0 has a nonzero component in the direction of an eigenvector associated with the dominant eigenvalue, then a subsequence \left( b_{k} \right) converges to an eigenvector associated with the dominant eigenvalue.

 

收敛性说明：The convergence is geometric, with ratio|\lambda_{2}/\lambda_{1}|。

\lambda_2 是第二大的特征值. Thus, the method converges slowly if there is an eigenvalue close in magnitude to the dominant eigenvalue. (具体证明见wiki）

应用：

Google用于PageRank的计算；Twitter用于给用户推荐who to follow.对于well-conditioned以及像web matrix那样稀疏的矩阵，power iteration method在寻找dominant eigenvector方面比其他方法更为高效。

Truncated Power Iteration

QQ截图20150816181005

 

 

 

 

 

参考资料：

1) http://mathfaculty.fullerton.edu/mathews/n2003/PowerMethodMod.html

2)https://en.wikipedia.org/wiki/Power_iteration

3)http://www4.ncsu.edu/~ipsen/ps/slides_imacs.pdf

3)