# Eigenvalue equation for kernel PCA

In Nonlinear component analysis as a kernel eigenvalue problem, Schölkopf et al start by describing PCA.

Given a set of data instances $x_1, \dots, x_M$, with $x_k \in \mathbb{R}^N, k=1,\dots,M$, and the corresponding $N\times N$ covariance matrix $C$, the principal components are found by solving, for each eigenvalue $\lambda \geq 0$,

$$\lambda v = Cv$$ for $v \in \mathbb{R}^N \backslash \{0\}$.

So far so good. However, the next argument states the following: since all solutions $v$ must lie in the span of $x_1, \dots, x_M$, then the following equation is equivalent to the previous one.

\begin{array}{c c} \lambda x_k^Tv = x_k^TCv & \mbox{for } k=1,\dots, M \end{array} I see how this equation is equivalent to the first one, in that both sides are basically multiplied by the input data. What I don't see is how that is a consequence of the eigenvectors lying in the span of $x_1, \dots, x_M$. Wouldn't the equations be equivalent regardless of that fact?

I suspect that this might be related to the fact that the projection of $x_k \in V$ onto $U=L(v_1, \dots, v_N)$ is only defined when $U\subseteq V$, but I still would like to be sure and know when the equations might not be equivalent.

• I realized that my answer was not correct (the idea was correct, but the implementation had an error). It does not work in 2D. I fixed it by considering a $3\times 3$ matrix. – amoeba says Reinstate Monica Jul 11 '16 at 19:56

Let $C = \begin{pmatrix}2&0&0\\0&0&0\\0&0&0\end{pmatrix}$. It has only one eigenvector $v_1 = (1, 0,0)^\top$ with eigenvalue $\lambda_1 = 2$; they are solution to $$Cv=\lambda v.\tag{1}$$
Now take $x_1=(0,1,0)^\top$. We can multiply equation (1) with $x_1$ from the left: $$x_1 C v = \lambda x_1 v.\tag{2}$$ But $x_1 C$ is just a zero vector $(0,0,0)$, so any $v$ that is orthogonal to $x_1$ is a solution to (2), not only $v_1$. For example, $v_2=(0,0,1)^\top$ is another solution.
It is a multivariate analogue of taking an equation and multiplying both sides by $0$.