Suppose ${x_1, \ldots, x_N}$ are the data points and we have to find $K$ clusters using Kernel K Means.
Let the kernel be $Ker$ (not to confuse with $K$ number of clusters)
Let $\phi$ be the implicit mapping induced by this kernel.
Now if $\phi$ were finite dimensional, there was no problem. However, assume $phi$ to be infinite dimensional, such has induced by RBF kernel
Now, everywhere I have read about kernel K means, it only says that we can do kernel K Means using
$||\phi(x_i) - \phi(x_j)||^2 = Ker(x_i, x_i) + Ker(x_j, x_j) - 2Ker(x_i, x_j) \;\; \ldots(1)$
I get this, but it is not so simple for my brain and nobody gives an explicit algorithm for kernel K means which leaves me with following doubts:
In what space do we initialise the K centroids? In the original space, or the space induced by $\phi$? I am guessing, we initialise in the original space only because we can't even comprehend the data points in space induced by $\phi$ Suppose we initialise randomly these $K$ centroids $\mu_1, \ldots \mu_K$ in the original space only. (Please correct me if I assuming wrong)
After initialisation, we have to assign every data point to one of the clusters. Suppose we want to assign $x_n$ to a cluster, this can be easily done using (1) to compute $\mu_k$ = $\text{arg min}_j\; ||\phi(x_n) - \phi(\mu_j)||^2$
After assigning clusters, how do I calculate the new centroids? Obviously I can't take mean in the space induced by $\phi$ as it is infinite dimensional, so what do I do now?
What is the work around this problem? I am assuming there is someway that we don't have to store the centroids at all. But I can't think of how to achieve this.
I have read Finding the cluster centers in kernel k-means clustering
However, the community wiki answer doesn't explains where $(1)$ comes from.