<p>Yes. By the triangle inequality, <span class="math-container">$\|x-z\| \le \|x-m\| + \|m -z\|$</span>, which implies the desired inequality (with <span class="math-container">$K=1$</span>) for any <span class="math-container">$m$</span> and <span class="math-container">$z$</span>.</p>

CC BY-SA 4.0
2023-02-17T21:45:24.327Z
2023-02-17T21:45:24.327Z
Neal Young
<p>Let <span class="math-container">$S$</span> be a set of points in <span class="math-container">$\mathbf{R^d}$</span> and let <span class="math-container">$m$</span> be the median of this set of points, i.e. <span class="math-container">$\sum_{x \in S} || x - y||$</span> is minimized when we have <span class="math-container">$y=m$</span>. Now let <span class="math-container">$z$</span> be an arbitrary point in <span class="math-container">$\mathbf{R^d}$</span>. <em>Is the following true?</em></p>
<p><span class="math-container">$$\sum_{x \in S} ||x-z|| \leq K \cdot (\sum_{x \in S} ||x-m|| + |S| \cdot ||m-z||)$$</span>
where <span class="math-container">$K$</span> is a constant.</p>
<p>We know that if we replace all the <span class="math-container">$||a-b||$</span> expressions by <span class="math-container">$||a-b||^2$</span>, and we consider the mean instead of the median(i.e. replace <span class="math-container">$m$</span> with <span class="math-container">$\mu$</span>), then actually we will have equality and <span class="math-container">$K=1$</span>. So I want to know if similar things hold for the median.</p>
<p>I was thinking maybe the following is true. Is it?</p>
<p><span class="math-container">$$\sum_{x \in S} ||x-z|| \leq \cdot (\sum_{x \in S} ||x-m|| + 4|S| \cdot ||m-z||)$$</span></p>

CC BY-SA 4.0
2023-02-16T11:49:48.880Z
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?
Neal Young
CC BY-SA 4.0
2023-02-16T11:58:34.803Z
@NealYoung The $|S|$ thing is still needed, as you are summing $|S|$ triangle inequalities together.
Emil Jeřábek
CC BY-SA 4.0
2023-02-16T17:03:48.733Z
Oh, I thought that term was inside the summand.  It makes more sense that it is not.
Neal Young
<ds.algorithms><approximation-algorithms><optimization><linear-algebra><high-dimensional-geometry>
An inequality about median of points in higher dimensions
David
# An inequality about median of points in higher dimensions

(Asked by: username_0 on 2023-02-16)

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||)$$

**Tags:** ds.algorithms, approximation-algorithms, optimization, linear-algebra, high-dimensional-geometry
> **Comments:**
> **username_1**: 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?  
> **username_2**: @NealYoung The $|S|$ thing is still needed, as you are summing $|S|$ triangle inequalities together.  
> **username_1**: Oh, I thought that term was inside the summand.  It makes more sense that it is not.  

---

## 1 answers

### Answer by username_1 on 2023-02-17. Score: 1

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$.


---

