Consider the setup of the [$k$-means problem][1] and assume that the data points are confined to $k$ balls of radius $\varepsilon$ while the pairwise distances between the centers of the balls are $> 2 \varepsilon$, and each ball contains the same number of points. It seems to me that it should be possible to show that the solution of the $k$-means problem puts all the centers in these balls, exactly one per each ball (in which case it is clear that each center will be the mean of the points in the corresponding ball). I have trouble showing this, but I feel that this has to be known. Any reference? or am I missing some additional necessary condition?

More precise statement: Let $B_2$ be the unit $\ell_2$ ball in $\mathbb R^d$ and consider datapoints $\{x_i, i=1,\dots,n\} \subset \mathbb R^d$ and (true) centers $\{v_1,\dots,v_k\} \subset \mathbb R^d$ such that

• for each $i$, $x_i \in v_j + \varepsilon B_2$ for some $j \in [k]$, and
• $\|v_j - v_\ell\|_2 > 2\varepsilon$ for all $j \neq \ell$, and
• $|\{i:\; x_i \in v_j + \varepsilon B_2\}|$ is the same for all $j \in [k]$.

Let $\{v^*_1,\dots,v^*_k\}$ be an optimal solution to the k-means problem. We would like to show that $v^*_j \in v_{\pi(j)} + \varepsilon B_2$ for all $j \in [k]$ and some permutation $\pi : [k] \to [k]$.

(It would be nice if this can be extended to constant-factor approximate solutions of the k-means problem.) [1]: https://en.wikipedia.org/wiki/K-means_clustering

Consider the setup of the $k$-means problem and assume that the data points are confined to $k$ balls of radius $\varepsilon$ while the pairwise distances between the centers of the balls are $> 2 \varepsilon$, and each ball contains the same number of points. It seems to me that it should be possible to show that the solution of the $k$-means problem puts all the centers in these balls, exactly one per each ball (in which case it is clear that each center will be the mean of the points in the corresponding ball). I have trouble showing this, but I feel that this has to be known. Any reference? or am I missing some additional necessary condition?

More precise statement: Let $B_2$ be the unit $\ell_2$ ball in $\mathbb R^d$ and consider datapoints $\{x_i, i=1,\dots,n\} \subset \mathbb R^d$ and (true) centers $\{v_1,\dots,v_k\} \subset \mathbb R^d$ such that

• for each $i$, $x_i \in v_j + \varepsilon B_2$ for some $j \in [k]$, and
• $\|v_j - v_\ell\|_2 > 2\varepsilon$ for all $j \neq \ell$, and
• $|\{i:\; x_i \in v_j + \varepsilon B_2\}|$ is the same for all $j \in [k]$.

Let $\{v^*_1,\dots,v^*_k\}$ be an optimal solution to the k-means problem. We would like to show that $v^*_j \in v_{\pi(j)} + \varepsilon B_2$ for all $j \in [k]$ and some permutation $\pi : [k] \to [k]$.

(It would be nice if this can be extended to constant-factor approximate solutions of the k-means problem.)

Alternative formulation in terms of measure approximation (see Pollard 82): Let $\mu$ be a measure on $\mathbb R^d$ supported on a collection $S_1,\dots,S_k$ of disjoint sets. Let $\mathcal P_k$ be the collection of discrete measures on $\mathbb R^d$ with at most $k$ atoms (objects of the form $\sum_{j=1}^k \pi_j \,\delta_{v_j}$).

Assume that

• Diameter of $S_j < 2\varepsilon$, for all $j$.
• $S_j$ and $S_\ell$ are suitably separated (?) relative to $\varepsilon$.
• $\mu(S_j)$ are equal for all $j \in [k]$.

Let $\mu^*_k$ be a solution of $\min_{\nu \in \mathcal P_k} W_2(\mu,\nu)$ where $W_2$ is the $2$-Wasserstein distance. Then $\mu^*_k$ will have exactly $k$ atoms one within each $S_j, j \in [k]$.

Consider the setup of the [$k$-means problem][1] and assume that the data points are confined to $k$ balls of radius $\varepsilon$ while the pairwise distances between the centers of the balls are $> 2 \varepsilon$. It seems to me that it should be possible to show that the solution of the $k$-means problem puts all the centers in these balls, exactly one per each ball (in which case it is clear that each center will be the mean of the points in the corresponding ball). I have trouble showing this, but I feel that this has to be known. Any reference? or am I missing some additional necessary condition?

More precise statement: Let $B_2$ be the unit $\ell_2$ ball in $\mathbb R^d$ and consider datapoints $\{x_i, i=1,\dots,n\} \subset \mathbb R^d$ and (true) centers $\{v_1,\dots,v_k\} \subset \mathbb R^d$ such that

• for each $i$, $x_i \in v_j + \varepsilon B_2$ for some $j \in [k]$, and
• $\|v_j - v_\ell\|_2 > 2\varepsilon$ for all $j \neq \ell$.

Let $\{v^*_1,\dots,v^*_k\}$ be an optimal solution to the k-means problem. We would like to show that $v^*_j \in v_{\pi(j)} + \varepsilon B_2$ for all $j \in [k]$ and some permutation $\pi : [k] \to [k]$.

EDIT: Maybe we need to assume that the number of points in each ball are the same (or roughly the same).

(It would be nice if this can be extended to constant-factor approximate solutions of the k-means problem.) [1]: https://en.wikipedia.org/wiki/K-means_clustering

Consider the setup of the [$k$-means problem][1] and assume that the data points are confined to $k$ balls of radius $\varepsilon$ while the pairwise distances between the centers of the balls are $> 2 \varepsilon$, and each ball contains the same number of points. It seems to me that it should be possible to show that the solution of the $k$-means problem puts all the centers in these balls, exactly one per each ball (in which case it is clear that each center will be the mean of the points in the corresponding ball). I have trouble showing this, but I feel that this has to be known. Any reference? or am I missing some additional necessary condition?

More precise statement: Let $B_2$ be the unit $\ell_2$ ball in $\mathbb R^d$ and consider datapoints $\{x_i, i=1,\dots,n\} \subset \mathbb R^d$ and (true) centers $\{v_1,\dots,v_k\} \subset \mathbb R^d$ such that

• for each $i$, $x_i \in v_j + \varepsilon B_2$ for some $j \in [k]$, and
• $\|v_j - v_\ell\|_2 > 2\varepsilon$ for all $j \neq \ell$, and
• $|\{i:\; x_i \in v_j + \varepsilon B_2\}|$ is the same for all $j \in [k]$.

Let $\{v^*_1,\dots,v^*_k\}$ be an optimal solution to the k-means problem. We would like to show that $v^*_j \in v_{\pi(j)} + \varepsilon B_2$ for all $j \in [k]$ and some permutation $\pi : [k] \to [k]$.

(It would be nice if this can be extended to constant-factor approximate solutions of the k-means problem.) [1]: https://en.wikipedia.org/wiki/K-means_clustering