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.

  • $\begingroup$ 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. $\endgroup$
    – amoeba
    Jul 11 '16 at 19:56

To get the intuition, consider what happens when this is not true.

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.

This means that the equations (1) and (2) are not equivalent. All solutions to (1) are solutions to (2), but not vice versa.

It is a multivariate analogue of taking an equation and multiplying both sides by $0$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.