Is nearest point to $\mu$ also nearest to all other points?

Suppose a set of points $$\mathcal{X} = \{ x_1, …, x_n\} \subset \mathbb{R}^p$$. Define

$$\mu = \frac1n \sum_i x_i$$

We know that $$\mu$$ is the point which minimizes (over $$\mathbb{R}^p$$) the sum of squared distances between it and all other points in $$\mathcal{X}$$.

Is it true that the point in $$\mathcal{X}$$ that is closest to $$\mu$$ is also the point in $$\mathcal{X}$$ that is closest to all other points in $$\mathcal{X}$$? In other words what I am asking is whether the following equality holds:

$$\arg\min_{x_i \in \mathcal{X}} \| \mu - x_i \|_2^2 = \arg\min_{x_j \in \mathcal{X}} \sum_i \| x_j - x_i \|_2^2$$

How can this be shown? I’m finding it difficult to write a proof due to the fact that $$\mathcal{X}$$ is a set of points (non-convex, disconnected, countable, etc)

If yes, does this still hold when we use other $$p$$-norms in place of $$\ell_2$$ to compute distance?

• When we use other $p$-norms in place of $\ell_2$, then $\mu$ is no longer the point minimizing the sum of distances to $\mathcal X$, so I wouldn't expect anything special to happen at the point closest to $\mu$ either. Commented Apr 21, 2022 at 3:57
• What I mean is, suppose we define $\mu_p = \arg\min \sum_i \| x_i - \mu\|_p$ for $p \geq 1$. Would that imply that the closest point to $\mu$ in $\ell_p$ distance is also the closest point to all other points in $\mathcal{X}$ also in $\ell_p$ distance? Commented Apr 21, 2022 at 10:23
• Do you want to minimize the sum of $\ell_p$ distances, or of their $p^{\text{th}}$ powers? Commented Apr 21, 2022 at 13:55
• Just the sum, not taken to any power. I know that even for $p=2$, this is a different problem with a different solution than the original $\mu$ case (which is squared $\ell_2$ norms). But as a follow up question, what (intuitively) does the quantity represent when taken to the $p^{th}$ power? Commented Apr 21, 2022 at 22:04

I will switch to $$x^1, \dots, x^n$$ as the notation for $$\mathcal X$$, so that I can use subscripts for components of a vector: $$x^i = (x^i_1, x^i_2, \dots, x^i_p)$$.

Let's begin by understanding the function $$f(x) = \sum_{i=1}^n \|x - x^i\|_2^2 = \sum_{i=1}^n \sum_{j=1}^p (x_j - x^i_j)^2.$$ Switching the order of summation and taking the $$j^{\text{th}}$$ term of the sum over $$j$$, we get $$\sum_{i=1}^n (x_j - x^i_j)^2$$. This is a quadratic equation in $$x_j$$ where the coefficient of $$x_j^2$$ is $$n$$, so it can be written as $$n(x_j - h_j)^2 + k_j$$ for some $$h_j, k_j \in \mathbb R$$. Summing these together again, we get $$f(x) = \sum_{j=1}^p n(x_j - h_j)^2 + k_j = n \|x - h\|_2^2 + \sum_{j=1}^p k_j.$$ In other words, $$f(x)$$ is $$n$$ times the distance to some point $$h$$, plus a constant.

By the characterization of $$\mu$$ as the point minimizing $$f(x)$$, we know that actually $$h = \mu$$. This tells us what the additive constant must be: it is $$f(\mu)$$ (the sum of distance from $$\mu$$ to the points in $$\mathcal X$$). We conclude that $$f(x) = n\|x - \mu\|_2^2 + f(\mu).$$ The point $$x^i \in \mathcal X$$ closest to all other points in $$\mathcal X$$ is the point $$x^i$$ for which $$f(x^i)$$ is the smallest. We see now that it must be the point for which $$\|x^i - \mu\|_2$$ is the smallest, therefore your equality holds.

Regarding the possibility of the same thing happening with other norms: the key thing that makes this work for $$\ell_2$$ is the fact that the sum of squared distance functions is a multiple of a distance function. (Plus a constant.) In the simplest case, for two points $$y, z$$, we have $$\|x - y\|_2^2 + \|x - z\|_2^2 = 2\|x - \tfrac{y+z}{2}\|_2^2 + \frac12\|y-z\|_2^2.$$ This lets us rewrite the function $$f(x)$$ above in terms of distance from the mean.

It is easy to check that the same "coincidence" does not occur for other norms, so when we work with a different norm, the function $$f(x)$$ will have a more complicated shape: it will not solely depend on the distance from some center point.

When $$\mathcal X$$ is very large, adding a new point or two will not change the shape of $$f(x)$$ very much. So we can add two new points $$x^{n+1}, x^{n+2}$$ with the following properties:

• $$x^{n+1}$$ is the new closest point to what we computed the center point to be.
• When we draw two contour lines through $$x^{n+1}$$ - the contour line of $$f(x)$$, and of distance to the center point - $$x^{n+2}$$ is inside the first and outside the second.

Then the first argmin in the question will be $$x^{n+1}$$, and the second will be $$x^{n+2}$$; this outlines how to come up with a counterexample for other norms.

• This is really helpful. Thanks a lot for the comprehensive and informative arguments here Misha. Commented Apr 22, 2022 at 13:56