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).



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.

| improve this answer | |
  • $\begingroup$ 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 $\endgroup$ – lucasrodesg Dec 22 '16 at 20:03
  • $\begingroup$ Sorry, I used incorrect definition of covariance matrix. I edited the answer now. I actually can't think of a case when I would use this. It doesn't really happen, that you have a vector and you need to check, if it's eigenvector. You usually compute the eigenvector and then you know you have it. And comparing to vectors isn't really difficult anyway. Maybe the autor uses this statement further in the book for something? $\endgroup$ – Tom83B Dec 23 '16 at 16:01

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.