7
$\begingroup$

There is a set A which contains some discrete points (1-dimension), for example {1, 3, 37, 59}. And I want to pick one point from A which can minimize the sum of distances between this point and others.

For this "1-D line", many people say the median is the right point, but could anybody give me a concrete proof on it?

$\endgroup$
4
  • 1
    $\begingroup$ @copper.hat: What do you mean? The median does minimize the sum of absolute deviations. $\endgroup$
    – user856
    Mar 2, 2013 at 5:25
  • 2
    $\begingroup$ The proof is by showing that if you move away from the median the sum of the distances does not decrease. Just think about how you are going away from at least as many points as you are approaching, when you move away from the median. $\endgroup$ Mar 2, 2013 at 6:02
  • $\begingroup$ My apologies, I need to eat crow. I see. Thanks Gerry, nice explanation (I was busy computing the generalized gradient...) $\endgroup$
    – copper.hat
    Mar 2, 2013 at 6:20
  • 1
    $\begingroup$ It would be more correct to say that a point that minimizes the sum of distances is the median. $\endgroup$
    – copper.hat
    Mar 2, 2013 at 7:06

1 Answer 1

5
$\begingroup$

I should apologize for my earlier rude and incorrect comment.

Here is a rather tedious proof that the median is a minimizer of $\min_x f(x)$ ($f$ defined below):

I need some notation: Let the set of points by $d_1,...,d_n$, let $\Omega = \{d_k\}_k$ (some points may be repeated) and define $f(x) = \sum_k |x-d_k|$. If $R$ is a relation on $\mathbb{R}$, let $I_R(x) = \{ k \,|\, x R d_k \}$ (eg, $I_=(x)$ is the set of indices such that $d_k = x$).

We note that $f$ is convex, and we have $f(x) = \sum_{k \in I_<(x)}d_k-x + \sum_{k \in I_>(x)}x-d_k$. Since $f$ is continuous, we see that $f$ is piecewise linear (affine), and for $x \notin \Omega$, $f'(x) = |I_>(x)|-|I_<(x)|$. Furthermore, since $f$ is convex, $f'(x)$ is non-decreasing on $\Omega^C$.

For $x < \min_k d_k$, we have $f'(x) = -n$, and for $x > \max_k d_k$, we have $f'(x) = +n$. Hence the problem $\min_x f(x)$ has a minimum on $[\min_k d_k, \max_k d_k]$.

Let $\phi_1,...,\phi_m$ be the non-decreasing sequence of values that $f'$ takes on $\Omega^C$, and let $J_1,...,J_m$ be the corresponding open intervals. (We have $\phi_1 = -n, \phi_m = +n$, of course.) There are two case to consider:

Case (1): For some $k$, we have $\phi_k = 0$, and for $x \in J_k$, $|I_>(x)|=|I_<(x)|$. It follows that $n$ is even, and since the median lies in $J_k$, we see that the median is a minimizer (in fact, $x$ is a minimizer iff $x \in \overline{J_k}$).

Case (2): For some $k$, we have $\phi_k <0, \phi_{k+1} >0 $. Let $\hat{x}$ be the point separating $J_k, J_{k+1}$ (hence $\hat{x} \in \Omega$). Then $\hat{x}$ is the minimizer of $f$. For $x \in J_k$, we have $f'(x) = |I_>(\hat{x})|-|I_=(\hat{x})|-|I_<(\hat{x})|$, and for $x \in J_{k+1}$, we have $f'(x) = |I_>(\hat{x})|+|I_=(\hat{x})|-|I_<(\hat{x})|$, or, in other words, $$|I_=(\hat{x})| > \left| |I_>(\hat{x})|-|I_<(\hat{x})| \right| $$ To see why the median is $\hat{x}$, let $l=|I_>(\hat{x})|, p=|I_<(\hat{x})|$ and $e=|I_=(\hat{x})|$ ($l+e+p = n$, of course). The above shows that $e > |p-l|$. If $l+e+p$ is even, then let $k=\frac{1}{2}(e+p-l)>0$. Then we have $l+k = p+e-k$, from which it follows that the $l+k$th and $l+k+1$st (ordered) points are equal to $\hat{x}$, and hence $\hat{x}$ is the median.If $l+e+p$ is odd, then let $k=\frac{1}{2}(e+p-l-1)\geq 0$. Then the $l+k+1$st (ordered) point is equal to $\hat{x}$, and hence the median is equal to $\hat{x}$.

Alternative:

One may use the convex subdifferential to obtain the same characterization. A quick computation shows that $\partial f(x) = -\{|I_<(\hat{x})|\}+\{|I_>(\hat{x})|\}+[-|I_=(\hat{x})|,+|I_=(\hat{x})|]$, and $x$ is a minimizer iff $0 \in \partial f(x)$, or equivalently, $x$ is a minimizer iff $|I_=(\hat{x})| \geq \left| |I_>(\hat{x})|-|I_<(\hat{x})| \right| $. Then a little work (essentially the same as the cases above) shows that the median satisfies the latter characterization.

$\endgroup$
3
  • $\begingroup$ What do "average" point minimizes? $\endgroup$
    – Nathan G
    Apr 15, 2023 at 12:28
  • 1
    $\begingroup$ @NathanB if $f(x) = \sum_k |x-d_k|^2 $, then the (unique in this case) minimiser is the average. Is that what you were asking? $\endgroup$
    – copper.hat
    Apr 16, 2023 at 1:26
  • $\begingroup$ Yes, exactly. So median minimizes sum of distances, and average minimizes sum of square distances. $\endgroup$
    – Nathan G
    Apr 17, 2023 at 11:25

You must log in to answer this question.

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