# Point $x \in \mathbb{R}^n$ that minimizes sum of distance squares $\sum_{\mathcal{l}=1}^{k} \Vert x-a^{\mathcal{(l)}} \Vert _2^2$

Let $$a^{(1)},...,a^{(k)} \in \mathbb{R}^n$$.

How can one find the point $$x \in \mathbb{R}^n$$, which minimizes the sum of distance squares $$\sum_{\mathcal{l}=1}^{k} \Vert x-a^{\mathcal{(l)}} \Vert _2^2$$

I know that a function $$h(t) = \sum_{l=1}^{k}(t-x_i)^2$$ has its minimum when $$t = \overline{x}$$. So for the average $$\overline{x}$$ of the numbers $$x_1,...,x_n$$ the sum of squares of the deviations $$\overline{x}-x_i$$ is minimal.

So to get the center of a set of points

$$S=\{(x_1,y_1),(x_2,y_2),\dots (x_n,y_n)\}$$ we can get their centroid by $$(\bar x,\bar y) = \left(\frac{1}{n}\sum_{i=0}^n x_i, \frac{1}{n}\sum_{i=0}^n y_i\right).$$

I don't really know if this point actually minimizes the sum of distance squares given above. I'd also like to know if only one such point exists or if there are more.

## 2 Answers

I believe your intuition is correct.

Consider the following:

$$\sum_{l=1}^k || x - a^{(l)}||_2^2 = \sum_{l=1}^k \sum_{m=1}^n (x_m - a^{(l)}_m)^2$$

Where $$a_m^{(l)}$$ is the $$m$$th component of the $$l$$th vector, and $$x_m$$ is the $$m$$th component of $$x$$.

To find the minimum of this with respect to $$x$$, we can use standard differentiation procedures.

First, differentiate with respect to one direction (i.e. differentiate with respect to some $$x_j$$): \begin{align} \frac{\partial}{\partial x_j} \sum_{l=1}^k \sum_{m=1}^n (x_i - a^{(l)}_m)^2 &=\sum_{l=1}^k \sum_{m=1}^n \frac{\partial}{\partial x_j} (x_m - a^{(l)}_m)^2 \\ &=\sum_{l=1}^k 2(x_j-a_j^{(l)}) \end{align} Setting this expression to zero you will obtain: \begin{align} \sum_{l=1}^k 2(\hat{x}_j-a_j^{(l)}) &= 0\\ \hat{x}_j &= \frac{1}{k}\sum_{l=1}^k a_j^{(l)} \end{align}

This shows that for any direction $$j$$, there is a stationary point of the function $$\sum_{l=1}^k || x - a^{(l)}||_2^2$$ (which we will show is a global minimum) given by the average of the $$j$$th component of the vectors $$\{a\}_{l=1}^k$$.

Now, to show that this is a unique global minimum, we will use the fact that a function $$f(x)$$ is strongly convex (which implies that $$f(x)$$ has a unique minimum point) if its Hessian $$H$$ (matrix containing the second derivatives) is positive definite (We say that $$H$$ is positive definite if $$\forall c \in \mathbb{R}^n/\{0\}, c^THc > 0$$).

Consider the second derivatives of $$\sum_{l=1}^k || x - a^{(l)}||_2^2$$:

\begin{align} \frac{\partial^2}{\partial_i\partial x_j} \sum_{l=1}^k \sum_{m=1}^n (x_m - a^{(l)}_m)^2 &=\sum_{l=1}^k \frac{\partial}{\partial x_i}2(\hat{x}_j-a_j^{(l)})\\ &=\begin{cases} 2 & i=j\\ 0 & i\neq j \end{cases} \end{align}

This means that the Hessian $$H$$ will be diagonal, and that there will be strictly positive entries on the diagonal. Thus $$H$$ is positive definite, implying that $$\sum_{l=1}^k || x - a^{(l)}||_2^2$$ is strongly convex with respect to $$x$$.

Hence, we can conclude that the stationary point which we found above is indeed a unique minimum.

You can use this relation: $$\sum_{i=1}^n \|x-a_i\|^2=n\|\bar{a}-x\|^2+\sum_{i=1}^n \|\bar{a}-a_i\|^2$$ where $$\bar{a}=\frac{1}{n}\sum_{i=1}^n a_i$$

If you want to minimize w.r.t. $$x$$, just take $$x=\bar{a}$$ to cancel the $$\|\bar{a}-x\|^2$$ term. Therefore the answer is: $$x=\bar{a}=\frac{1}{n}\sum_{i=1}^n a_i$$

To prove the first relation, you must notice that: $$\sum_i^{n}\|a_i-\bar{a}\|^2=\dots=\left(\sum_i^{n}\|a_i\|^2\right)-n\|\bar{a}\|^2$$ then simply develop $$\sum_{i=1}^n \|x-a_i\|^2=\sum_{i=1}^n (\|x\|^2-2\langle x,a_i \rangle+\|a_i\|^2)=\dots$$ (I can write the details if you want, just ask)