Question $5-$ Kernel PCA $($Bonus $10$ points$)$

PCA is a useful tool to lower the dimensions of the data and get much less feature that yet represent the data. Even though, sometimes the original data is not good enough, so we want to map the data into higher $($or same$)$ dimension!

Recall that in PCA, we require the samples to be mean$-$centered, $\frac{1}{n}{\displaystyle \underset{i=1}{\overset{n}{}}}{x}_i=0.$

We now want to do the same thing, but after x was mapped into $(x).$ Denote the following, mean$-$centered version of $(x)$ :

$v_i=(x_i)-\frac{1}{n}{\displaystyle \underset{t=1}{\overset{n}{}}}(x_t)$

However, we won't always have access to $/$ costs a lot of computation $($and won't be able to compute $v_1,$dots,$v_n).$

Therefore, we will use the kernel trick. Denote $K^{\text{'}}$ as the kernel matrix for $v_1,$dots,$v_n.$ Show how $K^{\text{'}}$ can be calculated using only the original kernel matrix $K$ on $x_1,$dots,$x_n.$

Reminder: $K_{i,j}^{\text{'}}=($:$v_i,v_j$:$)($since the new kernel is linear in terms of $(x)).$

$2.$ Now, for the rest of the question we assume that $\frac{1}{n}{\displaystyle \underset{i=1}{\overset{n}{}}}(x_i)=0.$

We would like to apply PCA to the vectors $(x_i).$ Denote by $u_1,$dots,$u_{k}in{R}^{d^{\text{'}}}$ the first k principal components, the eigenvectors of the scatter matrix S $.$

Show that $u_j($for $j=1,$dots,$k)$ is linear combination of $(x_1),$dots,$(x_n).$

Moreover, show who are the ${}_{j,1},$dots,${}_{j,k}$ such that $u_j={\displaystyle \underset{i}{\overset{?}{}}}{}_i(x_i).$

$3.$ Use the expression for ${}_{j,1},$dots,${}_{j,n}$ and find an algorithm to obtain the entire ${}_j=[{}_{j,1},$dots${}_{j,n}]$ using K$.$

Hint: substitute $u_j$ you found in the expression for ${}_{i,j}$ you found.

$4.$ Since we don't really know $,$ we can't use $u_j.$ But we also don't need them!

Their only purpose was to project $(x)$ onto the new dimension, using the dot product, $z_j=($:$u_j,(x)$:$)($and $($:$z^i=\left[\begin{array}{ccc}{z}_1^i& \text{d}\text{o}\text{t}\text{s}& z_k^i\end{array}\right]\}.$

Show how to calculate $z_j$ without using $.$

$5.$ Now, use sklearn and apply Kernel PCA with 'cosine' kernel $($doesn$\text{'}$t have hyperparameters$)$ and classify with KNN using $125$ neighbors, on the same data from question $3.$

Did it do better than the regular PCA $($on the test set$)?$

MAKE SURE TO SAVE IT TO COLAB