PCAの主成分を高速に求める方法について

主成分分析(PCA)はデータの圧縮手法の一つです.PCAを用いることでデータを拘束している高次元空間中の部分空間を取り出すことができます. 部分空間の基底を求める方法は一般には共分散行列の固有値問題に帰着されますが, 固有値問題は計算時間のオーダーがO(n^3)であるので次元が高いデータに対しては時間がかかりすぎてしまいます.しかしこれはすべての固有値・固有ベクトルを求める時の話であって, PCAに於いては値の大きい方から数個の固有値及び対応する固有ベクトルしか必要ないという場合が多々あるので真面目に固有値問題を解くのは効率がよくありません.
今回は数値計算の授業中に思いついたデータの主成分を効率よく必要な数だけ取ってくるアルゴリズムを紹介します. このアルゴリズムは大きい方から固有値及び対応する固有ベクトルを必要なだけ取ってくるアルゴリズムであるのでKPCAやCCA, KCCA などに応用することもできます. あとで調べて分かったのですがこの方法はGoogle がPagerank を求める時にも用いているそうです. 残念←

Principal Component Analysis (PCA) is one of the method of data compression. We can bring out the subspace in high dimension space which constrains data. Generally the method of calculate basis of the subspace is the eigenvalue problem of covariance matrix. However this method takes too long time for high dimension data because the eigenvalue problem takes time O(n^3). If you need not all eigenvalues and eigenvectors of covariance matrix and only need several these from the lager one, it is not efficient to solve the eigenvalue problem straight (in particular PCA).
In this item, I introduce the algorithm to calculate principal value of data efficiently as needed(I came up with this algorithm at the time of the lecture of numerical computation). This algorithm can be also applied to KPCA, CCA and KCCA because it calculate eigenvalues and eigenvectors of covariance matrix from the larger one as needed. Afterwards, I found this algorithm has already used by Google to calculate Pagerank.