0
$\begingroup$

Let $S$ be a set of points in $\mathbf{R^d}$ and let $m$ be the median of this set of points, i.e. $\sum_{x \in S} || x - y||$ is minimized when we have $y=m$. Now let $z$ be an arbitrary point in $\mathbf{R^d}$. Is the following true?

$$\sum_{x \in S} ||x-z|| \leq K \cdot (\sum_{x \in S} ||x-m|| + |S| \cdot ||m-z||)$$ where $K$ is a constant.

We know that if we replace all the $||a-b||$ expressions by $||a-b||^2$, and we consider the mean instead of the median(i.e. replace $m$ with $\mu$), then actually we will have equality and $K=1$. So I want to know if similar things hold for the median.

I was thinking maybe the following is true. Is it?

$$\sum_{x \in S} ||x-z|| \leq \cdot (\sum_{x \in S} ||x-m|| + 4|S| \cdot ||m-z||)$$

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Doesn't triangle inequality give you $\| x - z\| \le \|x - m\| + \|m - z\|$? In which case the inequality holds even with $K=1$ and replacing "$|S|$" with 1. And for arbitrary $m$? What am I missing? $\endgroup$
    – Neal Young
    Feb 16 at 11:49
  • $\begingroup$ @NealYoung The $|S|$ thing is still needed, as you are summing $|S|$ triangle inequalities together. $\endgroup$
    – Emil Jeřábek
    Feb 16 at 11:58
  • $\begingroup$ Oh, I thought that term was inside the summand. It makes more sense that it is not. $\endgroup$
    – Neal Young
    Feb 16 at 17:03

1 Answer 1

Reset to default
1
$\begingroup$

Yes. By the triangle inequality, $\|x-z\| \le \|x-m\| + \|m -z\|$, which implies the desired inequality (with $K=1$) for any $m$ and $z$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.