next up previous contents
Next: B.2 Kernel PCA speed-up Up: B. Algorithms Previous: B. Algorithms


B.1 Power method with deflation

The power method is a common method to extract the eigenvector with the largest eigenvalue (Diamantaras and Kung, 1996). Starting with a random vector $ \bf a$, the principal eigenvector of a matrix $ \bf K$ is computed by iterating:

$\displaystyle {\frac{{{\bf K}{\bf a}}}{{\Vert\mbox{max}({\bf K}{\bf a})\Vert}}}$ $\displaystyle \rightarrow$ $\displaystyle \bf a$ . (B.1)

max($ \bf K$$ \bf a$) is the component of the vector $ \bf K$$ \bf a$ with the largest absolute value (some variants of the power method use |$ \bf a$| instead). This iteration converges to the largest eigenvector with the eigenvalue $ \lambda{^\prime}$ = |max($ \bf K$$ \bf a$)|. Further eigenvectors are obtained using deflation. After the eigenvector $ \bf a_{i}^{}$ (number i, ordered by the size of the corresponding eigenvalue) is computed, a new matrix $ \bf K_{{i+1}}^{}$ is obtained from the previous one $ \bf K_{i}^{}$ by iterating

$\displaystyle \bf K_{{i+1}}^{}$ = $\displaystyle \bf K_{i}^{}$ - $\displaystyle \lambda_{i}{^\prime}$$\displaystyle {\frac{{{\bf a}_i {\bf a}_i^T}}{{{\bf a}_i^T {\bf a}_i}}}$ , (B.2)

where $ \lambda_{i}{^\prime}$ is the eigenvalue corresponding to $ \bf a_{i}^{}$.


next up previous contents
Next: B.2 Kernel PCA speed-up Up: B. Algorithms Previous: B. Algorithms
Heiko Hoffmann
2005-03-22