3
$\begingroup$

Let $x_1, \ldots, x_n \in \mathbb{R}^d$ denote $n$ points in $d$-dimensional Euclidean space, and $w_1, \ldots, w_n \in \mathbb{R}_{\geq 0}$ any non-negative weights.

In some paper I came across the following equation:

$$\arg\min_{c \in \mathbb{R}^d} \sum_{i=1}^n w_i \|c - x_i\|^2 = \frac{\sum_{i=1}^n w_i x_i}{\sum_{i=1}^n w_i}$$

However, I cannot see why this holds.

Googling suggests that this is related to minimizing the Moment of Inertia by the Center of Mass, as well as to the Fréchet mean for Euclidean distances, but both these contexts seem to be much too general to let me get the key insight here.

So, is there a simple straightforward proof of the above?

$\endgroup$

1 Answer 1

4
$\begingroup$

Let $f(x) = \sum_i w_i (c - x_i) \cdot (c - x_i)$. Then the partial derivative of $f$ wrt $c_j$ is
$$ 2\sum_i w_i (c - x_i)\cdot e_j $$ where $e_j$ is the $j$th standard basis vector. Setting this to zero gives

$$ \sum_i w_i (c_j - x_{i,j}) = 0 \\ c_j\sum_i w_i = \sum_i w_i x_{i,j} \\ c_j= \frac{\sum_i w_i x_{i,j}}{\sum_i w_i } $$ where $x_{i, j}$ denotes the $j$th entry of vector $x_i$.

That shows that there's a unique critical point. The function clearly goes to infinity as $\|c\|$ gets large, so this critical point must be a min. You're done.

$\endgroup$
1
  • $\begingroup$ Ah, "of course" starting with squared Euclidean distance = scalar product. Thank you! Now it's no longer strange to me. $\endgroup$ Commented Jan 10, 2014 at 17:46

You must log in to answer this question.

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