this scenario as *geometric clustering*. From now on, we discretize the measures: $\NU = \sum_{\IdxCentroid = 1}^{K}\NUL{\IdxCentroid}\delta[\yL{\IdxCentroid}], \MUL{i} = \sum_{j=1}^{n_i}\MU(\xL{j})\delta[\xL{j}]$ and assume that $n_i \gg K,\ \forall i$.

Regularized K-Means Clustering {#sec:regularized_kmeans}
------------------------------

In light of the discovery of VWBs for unbalanced measures in \[sec:unbalanced\_ot\], we now introduce a relaxed version of the constrained K-means problem. We call it *regularized K-means*.

The classic K-means problem has the objective as follows: $$\label{eq:kmeans}
    \min_{\bm{\Region}}\sum_{\IdxCentroid = 1}^{K}\sum_{\x \in \RegionL{\IdxCentroid}}\|\x - \yL{\IdxCentroid}\|_{2}^{2},\ \ \yL{\IdxCentroid} = \frac{1}{|\RegionL{\IdxCentroid}|}\sum_{\x \in \RegionL{\IdxCentroid}} \x,$$ where $|\RegionL{\IdxCentroid}|$ is the number of samples supported in $\RegionL{\IdxCentroid}$. By adding the marginal constraint $\NUL{\IdxCentroid} = \sum_{\x \in \RegionL{\IdxCentroid}}\MU(\x)$ with pre-defined, fixed measures $\{\NUL{\IdxCentroid}\}_{\IdxCentroid = 1}^{K}$, we turn  into the *constrained K-means* problem [@bradley2000constrained; @cuturi2014fast], or the *Wasserstein Means* problem coined in [@ho2017multilevel]. As discussed in Section \[sec:unbalanced\_ot\], when the total measures do not equal, such constraints instead become regularizers. Then, we define the objective of the regularized K-means clustering problem as: $$\label{eq:regularized_kmeans}
    \min_{\bm{\Region}, \bm{\y}}\sum_{\IdxCentroid = 1}^{\K}\sum_{\x \in \RegionL{\IdxCentroid}}\|\x - \yL{\IdxCentroid}\|_{2}^{2} + \lambda \sum_{\IdxCentroid = 1}^{\K} \left( \NUL{\IdxCentroid} - w_{\IdxCentroid} \right)^{2},$$ where $w_{\IdxCentroid} = \sum_{\x \in \RegionL{\IdxCentroid}}\MU(\x)$. If $\lambda = 0$, becomes K-means; if $\lambda \rightarrow \infty$, becomes Monge OT. As practiced in [@cuturi2014fast; 