5
$\begingroup$

Let $S=\{x_1,...,x_n\}$ be a set of vectors in $\mathbb{R}^d$. Now we have to pick a vector $\mu$, such that the following expression is minimized:

$$ L(\mu)=\sum_{x\in S} ||x-\mu||_2^2. $$

I think that the best option to minimize $L(\mu)$, would be to use the mean of the vectors as $\mu$. However, I can't prove why this is so.

Here's a complete answer that I solved thanks to the help of David K.

$$ \begin{align*} \mu^*&= \arg\min_\mu \sum_{x\in S} ||x-\mu||_2^2 \\ &= \arg\min_\mu \sum_{x\in S} <x-\mu,x-\mu> \\ &= \arg\min_\mu \sum_{x\in S} \big(<x,x> -2<x,\mu>+<\mu,\mu>\big) \\ &= \arg\min_\mu n<\mu,\mu>-2\sum_{x\in S}<x,\mu> \\ &= \arg\min_\mu n<\mu,\mu>-2n\left<\frac{1}{n}\sum_{x\in S}x,\mu\right> \\ &= \arg\min_\mu <\mu,\mu>-2<\overline{x},\mu> \\ &= \arg\min_\mu <\mu,\mu>-2<\overline{x},\mu> + <\overline{x},\overline{x}> \\ &= \arg\min_\mu <\mu-\overline{x},\mu-\overline{x}> \\ &= \arg\min_\mu ||\mu-\overline{x}||_2^2. \end{align*} $$ The $||\cdot ||_2$ can never be smaller than $0$. Therefore, choosing $\mu=\overline{x}$ minimizes the expression, as $||\mu-\overline{x}||_2^2$ becomes $0$. Hence, $\mu^*=\overline{x}$.

$\endgroup$
2
  • $\begingroup$ You can remove the $n$ in line 5 because its a constant multiplier and has no effect on the solution when optimizing for $\mu$, right? $\endgroup$
    – Chris
    Commented May 6, 2021 at 8:11
  • 1
    $\begingroup$ @Chris Yes, that’s right. $\endgroup$
    – ndrizza
    Commented May 12, 2021 at 21:28

2 Answers 2

4
$\begingroup$

Since the symbol $\mu$ is already in use in the question, let's write $\bar x$ to denote the mean of the vectors in $S$; that is, $$ \bar x = \frac1n \sum_{x\in S} x. $$

Then by the linearity of the inner product, \begin{align} \sum_{x\in S} \langle x, \mu\rangle &= \left\langle \sum_{x\in S} x, \mu\right\rangle \\ &= n \left\langle \frac1n\sum_{x\in S} x, \mu\right\rangle \\ &= n \left\langle \bar x, \mu\right\rangle. \\ \end{align}

With this, you can eliminate the individual $x$s from your last formula, leaving only $\mu$ and $\bar x$.

Now consider the quantity $\lVert \mu - \bar x\rVert_2^2$. That's something that clearly minimized when $\mu = \bar x$, since the norm $\lVert \cdot\rVert_2$ can never be less than zero. That is, $$ \arg\min_\mu \, \lVert \mu - \bar x\rVert_2^2 = \bar x \tag1 $$ So it would be really convenient if we could reduce your minimization problem to something that looks like the left-hand side of Equation $(1)$.

Now consider some of the techniques you already used in your first attempt. You know that $\lVert \mu - \bar x\rVert_2^2 = \lVert\mu\rVert_2^2 - 2 \langle\mu,\bar x\rangle + \lVert\bar x\rVert_2^2$, and you know you can add or subtract a constant from the value inside the $\arg\min$ without changing the $\mu$ that minimizes the value. Also notice that in your second attempt, you found that $$ \mu^* = \arg\min_\mu \, (- 2 \langle\bar x,\mu\rangle + \lVert\mu\rVert_2^2). $$

At this point, you're just a couple of steps away from showing that $\mu^* = \bar x$. (I'm trying not to spoil this too much, because it's so much fun when a problem resolves like this, especially when you get to make the final "aha!" step yourself.)

$\endgroup$
6
  • $\begingroup$ Thank you! That got me a bit further. However, I'm still stuck at the very last step. Do you have a good argument for justifying $\mu=\overline{x}$ on the last line? $\endgroup$
    – ndrizza
    Commented May 2, 2016 at 8:14
  • $\begingroup$ It's probably easier if you back up a couple of lines. I extended the answer a bit to show what I had in mind. $\endgroup$
    – David K
    Commented May 2, 2016 at 12:59
  • $\begingroup$ This is very neat! $\endgroup$ Commented May 2, 2016 at 16:36
  • $\begingroup$ Thank you very much for your help @DavidK! I've written down a complete answer that uses the tricks you showed me. $\endgroup$
    – ndrizza
    Commented May 3, 2016 at 21:09
  • $\begingroup$ I looked at your revisions to the proof in your question, they look fine to me! $\endgroup$
    – David K
    Commented May 3, 2016 at 21:12
1
$\begingroup$

Since $S = \{x_1, ..., x_n\}$ is finite let $L(\mu) = \sum_{i = 1}^{n} ||x_i-\mu||_2^2$, which is a function from $\mathbb{R}^d$ to $\mathbb{R}$. In the following I will use upper indices to denote the respective components of the vectors involved, e.g. $x_1 = (x_1^1, x_1^2, ... x_1^d)$. Calculating the partial derivatives of $L(\mu)$ with respect to $\mu^k$ where $1 \leq k \leq d$ we get

$\frac{\partial L}{\partial \mu^k} = 2n\mu^k - 2\sum_{i=1}^{n} x_i^k$. Now, if we want this to vanish we get

$2n\mu^k - 2\sum_{i=1}^{n} x_i^k = 0 \Leftrightarrow \mu^k = 1/n \cdot \sum_{i=1}^{n} x_i^k$.

That is $\mu = \frac{1}{n} \begin{pmatrix} \sum_{i=1}^{n} x_i^1 \\...\\ \sum_{i=1}^{n} x_i^d \end{pmatrix} = \frac{1}{n} \sum_{j=1}^{n} x_j$.

Now you need to go on and prove this gives a global minima for $L$.

$\endgroup$
1
  • $\begingroup$ Thank you! It's nice to also have an approach that uses derivation. The end would involve building the Hesse matrix and showing that it's positive definite (and it most likely will be symmetric and thus positive definite). $\endgroup$
    – ndrizza
    Commented May 2, 2016 at 8:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .