2
$\begingroup$

How can one prove that the optimal kPCA solution $a^*=\{a_1...a_K\}$ are the $k$-largest Eigenvectors of the (centered) kernel matrix $K$?

I referred to a lot of resources and couldn't find a proper explanation.

$\endgroup$
1
  • $\begingroup$ We aim to choose a direction in which all of the features have the highest variance. why is that? because features low variance doesn't really have that much influence in predicting the outcome, because it does not vary that much for different samples. Hence, we choose the direction with the largest amount of variance for all the features that's also more informative. In order to choose the direction with the highest variance, we choose the eigenvectors as directions that lead to highest variance. $\endgroup$ Jul 15 '19 at 1:04
1
$\begingroup$

Let us say $K$ is an $m \times n$ matrix.

You want to find a vector $a$ that maximizes $\frac{||Ka||}{||a||}$.

Now maximizing $\frac{||Ka||}{||a||}$ implies maximizing its square:

$$\begin{eqnarray*} \frac{||Ka||^2}{||a||^2} \\ = \frac{(Ka)^TKa}{a^Ta} \\ = \frac{a^TK^T Ka}{a^Ta} \\ = \frac{a^T(K^TK) a}{a^Ta} \\ = \frac{a^TSa}{a^Ta} \end{eqnarray*} $$

where $S = K^TK$ is always an $n \times n$ symmetric positive semidefinite matrix for all $K$

Now symmetric positive semidefinite matrices have several special properties one of which is that they always have REAL eigen values. Also the eigen vectors associated with these eigen values are always orthogonal to each other.

What this means is that if you locate the eigen vector for $S$ with the highest eigen value - you have basically found the vector that maximizes: $\frac{a^TSa}{a^Ta}$

So in essence the eigen vector with the largest eigen value for $S$ or $K^TK$ maximizes both $\frac{a^TSa}{a^Ta}$ and the original $\frac{||Ka||}{||a||}$ Use the same analogy for the remainder eigen vectors - i.e the second best vector that maximizes $\frac{a^TSa}{a^Ta}$ is the eigen vector corresponding to the second highest eigen value.

$\endgroup$
0
$\begingroup$

An indirect way would be the ratio of variance in all the dimensions if we know the eigenvalues corresponding to eigenvectors. So if an eigenvector has eigenvalues $e1$ then the ratio contributed by it will be $e1\over (e1+e2+e3+e4.... +en)$. The largest eigenvector will have the largest eigenvalue.

$\endgroup$

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.