A Sampler of Useful Computational Tools for Applied Geometry, Computer Graphics, and Image Processing

Dimensionality Reduction 141

dot product of two high-dimensional vectors in the feature space,

while the right-hand side is the dot product of two size-n vectors.

We shall not provide a proof of the above claim here; interested

readers should refer to [SSM97].

From Equation (9.1), we see that to derive the embedding of

point x

j

, 1 ≤ j ≤ n, via kernel PCA, we simply let x := x

i

. We

are thus projecting the i-th row of the matrix K onto e

k

. Since e

k

is the k-th eigenvector of K, Ke

k

= λ

k

e

k

, the resulting projection

is nothing but the j-th entry of e

k

scaled by the k-th eigenvalue

λ

k

of K. If the projection is performed on the first k eigenvectors,

we obtain