Principal Component Analysis, Eigenvectors lying in the span of the observed data points?

I have been reading several papers and articles related to Principal Component Analysis (PCA) and in some of them, there is one step which is quite unclear to me (in particular (3) in [Schölkopf 1996]).

Let me reproduce their reasoning below.

Consider the centered data set $D = \{\textbf{x}_k\}_{k=1}^M$ with $\textbf{x}_k \in \textbf{R}^N$ and $\sum_{k=1}^M \textbf{x}_k = 0$. PCA diagonalizes the (sample) covariance matrix

$$C = \frac{1}{M} \sum_{j=1}^M \textbf{x}_j \textbf{x}_j^T. \tag{1}$$

To do this we find the solution to the eigenvector equation

$$\lambda \textbf{v} = C \textbf{v} \tag{2}$$

for eigenvalues $\lambda \geq 0$ and eigenvectors $\textbf{v} \in \textbf{R}^N\backslash \{{0}\}$. As

$$\lambda \textbf{v} = C \textbf{v} = \frac{1}{M} \sum_{j=1}^M (\textbf{x}_j^T \textbf{v}) \textbf{x}_j, \tag{3}$$

all solutions $\textbf{v}$ with $\lambda \neq 0$ must lie in the span of $\textbf{x}_1, \dots, \textbf{x}_M$, hence (2) is equivalent to

$$\lambda(\textbf{x}_k^T \textbf{v}) = \textbf{x}_k^T C \textbf{v}, \qquad \text{for } k = 1, \dots, M \tag{4}$$

In (4), doesn't $\lambda(\textbf{x}^T \textbf{v}) = \textbf{x}^T C \textbf{v}$ hold for $\textbf{any}$ value of $\textbf{x}$? Why does (4) only hold when $\textbf{x} \in D$? I do not understand how their end up with (4).

Thanks.

The statement says, that (2) and (4) are equal. That means (2)$\Rightarrow$(4) and (4)$\Rightarrow$(2). The first implication is trivial, as you correctly pointed out. $$\lambda v=Cv$$ implies $$\lambda x^Tv=x^TCv$$ for all $v$, not just those from $D$. But the second implication is a bit more tricky, but that is what the proof is about. It tells you, that if you want to check, whether a vector is an eigenvector of $C$, you don't have to check if (2) is satisfied. It tells you, that when (4) is satisfied, (2) is satisfies as well.
Imagine you have 2 points in 3D space. Those 2 points are $$x_1=(-1,-1,0)$$ $$x_2=(1,1,0)$$ (please excuse me for not making this "dataset" centered) Note, that both points lie in the $xy$ plane. Now the correlation matrix is $$C=\begin{bmatrix} 1/2 & -1/2 & 0 \\[0.3em] -1/2 & 1/2 & 0 \\[0.3em] 0 & 0 & 0 \end{bmatrix}$$ Now you want to know, whether $v=[1\ -1\ 0]^T$ is an eigenvector with eigenvalue 1. The statement tells you, that you can either just check, if (2) is satisfied (3 equations) or if $$\frac{1}{2}x_1^Tv=x_1^TCv=0$$ and $$\frac{1}{2}x_2^Tv=x_2^TCv=0$$ which are only two equations.
• Thanks! Only two comments: (1) How did you compute the covariance? $.5(x_1 x_1^T+x_2 x_2^T)$ or $.5((x_1-\mu)(x_1-\mu)^T+(x_2-\mu)(x_2-\mu)^T$ does not give me the same covariance matrix. (2) I guess this method makes only sense if the number of points is lower than the dimension of the feature space (so that we reduce the number of operations)? Thanks once again! @tom83b Commented Dec 22, 2016 at 20:03