Power Iteration
べき乗法は、行列をベクトルに繰り返し掛けて v_{k+1}=Av_k/||Av_k|| と更新し、絶対値が最大の固有値に対応する固有ベクトルへ収束させる。
目的
優越固有値とその固有ベクトルを効率的に近似するもので、PageRankやPCAで利用される。
メカニズム
vは主固有ベクトルへ収束し、比 ||Av_k||/||v_k|| は主固有値へ収束する。収束速度は |λ_1/λ_2| に依存する。加速手法として、レイリー商、シフト反復、QRアルゴリズムがある。
ユースケース
- PageRankの計算
- PCAによる次元削減近似
- スペクトル解析