Kernel k-means formula notation

Question

the kernel k-means problem is notated as:

$ \overset{min}{U \in \{0,1\}^{kxs}} \overset{max}{c_k(\cdot) \in \mathcal{H}_{K}} \sum_{j=1}^{k}\sum_{i=1}^{S} \frac{U_{ji}}{s} \left \| c_j(\cdot)-\kappa(x_i, \cdot)) \right \|^2_{\mathcal{H}_K} $

U is the cluster membership matrix which is 1 if a point is in the cluster and 0 if it is not. $ c_k(\cdot) $ are the cluster centers and $ \kappa (x_i, \cdot) $ is the kernel function (use RBF for example). K are the clusters and S are the points.

It might be an easy question, but could somebody explain in easy words what's going on here?

Usually in k-means we are trying to minimize the distances between the points and the cluster centers (as done with $c_{j}(\cdot) - \kappa(x_i, \cdot) $. Fine, but what is the max doing here? What means that $\overset{max}{c_k(\cdot)}$? Are we searching the maximum cluster center point? Why?

Unfortunately I did not find a youtube video or paper where this formula is explained in detail. Thanks a lot in advance.

Additional info:

The whole formula comes from "Stream Clustering: efficient kernel-based approximation using importance sampling" by Radha Chitta, Jin & Jain 2016 but I think a better and easier introduction is given in "Kernel-based clustering of Big Data" by Radha Chitta 2015 in formula 1.7.

$ \overset{min}{U \in \rho} \overset{max}{c_k(\cdot) \in \mathcal{H}_{K}} \sum_{k=1}^{C}\sum_{i=1}^{n} U_{ki} \left \| c_k(\cdot)-\kappa(x_i, \cdot)) \right \|^2_{\mathcal{H}_K} $

Where U is the cluster membership matrix, which is one if a point is in a cluster, domain $\rho = {U \in {0, 1}^{C×n} : U^T = 1}$, where 1 is a vector of all ones, $\mathcal{H}_{K}$ is the reproducing hilbert space, $c_k(\cdot)$ are the cluster centers, C are the clusters, n are the points.

Answer 1

So, the classical $k$-means can be written as an optimization problem: $$ \mathcal{U}^* = \text{arg}\min_{\hspace{-1in}\phantom{\hat{U}}U\in\mathcal{P}}\,\max_{c_k\in\chi} \sum_{k=1}^C \sum_{i=1}^n U_{k,i} ||c_k - \vec{x}_i||_d^2 $$ for some distance $||\cdot||_d$, membership matrix $U$ (which assigns clusters to each $\vec{x}$, $c_k$ is the $k$th cluster center, and $\vec{x}_j$ is the $j$th data point. Basically, $U_{i,k}$ is $1$ if $\vec{x}_i$ is in the $k$th cluster and $0$ otherwise. The summations basically compute the total distance of each data point to its cluster center.

We can rewrite this as: $$ \mathcal{U}^* = \text{arg}\min_{\hspace{-1in}\phantom{\hat{U}}U\in\mathcal{P}}\,\max_{c_k\in\chi} \sum_{k=1}^C |\mathcal{C}_k|\,\mathbb{V}[\mathcal{C_k}] $$ where $\mathbb{V}[\mathcal{C_k}]$ is the variance of cluster $k$. Note that having huge, high-variance clusters seems undesirable; we want compact, tight, dense groups instead! So instead of just minimizing the total intra-cluster variance, we actually minimize the maximal intra-cluster variance. It's like the Hausdorff distance. If you want to enforce something, you could minimize some energy averaged over a set, but some outliers can escape unscathed if other members can compensate. This is stronger: it says, "minimize the worst case, not just the average one".

For more details, look up "MinMax $k$-Means". (e.g. here).

---

Now for the kernelized case. Using a kernel is necessary to be able to cluster data that are non-linearly organized. (The hope is that they will be linearly clusterable in some higher-dimensional space). We look at: $$ \mathcal{U}^* = \text{arg}\min_{\hspace{-1in}\phantom{\hat{U}}U\in\mathcal{P}}\, \max_{c_k\in\mathcal{H}} \sum_{k=1}^C \sum_{i=1}^n U_{k,i} ||\tilde{c}_k - \Phi(\vec{x}_i)||_{d,K}^2 $$ where $\Phi$ maps to the higher space (where $\tilde{c}_k$ is) and the new distance function is efficiently computed with the kernel $K$. Notice all our interpretations apply the same way in this case. :)

---

There's something important to keep in mind, which is that: $$ \max_a \min_b f(a,b) \leq \min_t \max_s f(s,t) $$ just in case you are wondering why we can't switch the ordering (in some cases).

Also, I will note that it is rare to see this formulation (at least for me). Normally, people either leave out the max or they replace the outer sum with it. This notation by Chitta may be a way to capture both cases. If someone else knows better, let me know :)