6

I want to show that the sample median $\tilde{x}$ minimizes the sum of absolute deviations,

i.e., $\tilde{x} = \underset{a}{argmin}\sum_{i=1}^{n}\begin{vmatrix} x_i-a\end{vmatrix}$

To show this, so far I have:

Sum of absolute deviation about a is

$=\sum_{i=1}^{n}\begin{vmatrix} x_i-a\end{vmatrix}$

Assume that $x_1\leq x_2\leq ...\leq x_n$

CASE 1: When n is ODD (n = 2m + 1)

We get,

$x_1\leq x_2\leq ... \leq x_m\leq x_{m+1}\leq ... \leq x_{2m} \leq x_{2m+1}$

From this we can see that

$\begin{vmatrix} x_1-a\end{vmatrix} + \begin{vmatrix} x_{2m+1}-a\end{vmatrix}$ is least when $x_1\leq a \leq x_{2m+1}$

$\begin{vmatrix} x_2-a\end{vmatrix} + \begin{vmatrix} x_{2m}-a\end{vmatrix}$ is least when $x_2\leq a \leq x_{2m}$

...

Thus,

$\begin{vmatrix} x_{m+1}-a\end{vmatrix}$ is least when $a=x_{m+1}=median$

CASE 2: When n is EVEN (n = 2m) We get,

$x_1\leq x_2\leq ... \leq x_m\leq x_{m+1}\leq ... \leq x_{2m-1} \leq x_{2m}$

From this we can see that

$\begin{vmatrix} x_1-a\end{vmatrix} + \begin{vmatrix} x_{2m}-a\end{vmatrix}$ is least when $x_1\leq a \leq x_{2m}$

...

Thus,

$\begin{vmatrix} x_{m}-a\end{vmatrix} + \begin{vmatrix} x_{m+1}-a\end{vmatrix}$ is least when $x_m\leq a \leq x_{m+1}$

Is this enough to show that sample median minimizes the sum of absolute deviations?

user155019
  • 61
  • 1
  • 2
  • 1
    The idea of a proof is explained under "Absolute ($L_1$) Loss" in my answer at http://stats.stackexchange.com/a/114363/919. The generalization to any percentile (the median is the 50th percentile) is addressed at http://stats.stackexchange.com/questions/251600. Neither one requires splitting into odd and even cases: they can be handled in the same manner. – whuber Mar 28 '17 at 22:56
  • 1
    The proof seems to be absolutely correct to me. I like the fact that you knew that the self-study tag was required. – Michael R. Chernick Mar 28 '17 at 21:47

1 Answers1

1

When all of the $x_i$ are distinct, this is easy. If $$f(m) = \sum_{i=1}^{n} |x_i - m|$$ then $$f'(m) = \sum_{i=1}^{n} {\rm sign}(x_i - m)$$ which equals zero when there are an equal number of elements of $x_1, ..., x_m$ that are above and below $m$, which is the definition of the median, $m^{\star}$. As a function of $m$, this is decreasing on $(-\infty, m^{\star})$ and increasing on $(m^{\star}, \infty)$, so $m^{\star}$ is a minimizer.

Note: If $n$ is even, the sample median is not necessarily uniquely defined. In that case, what is the "right" point estimate of the median is debatable. So, $m^{\star}$ could be called any value over the open interval where $f'$ is zero (a common convention is taking the midpoint... e.g. see what happens when you type median(1:4) into R....you will get 2.5), but the basic logic of what I wrote above proves it would still minimize the MAD....But so would any value between 2 and 3...

gammer
  • 1,456
  • 10
  • 21
  • 1
    The problem with this proof is that $f'$ is not generally zero on an open interval, or anywhere. Example, $f(x) = |x-1| + |x-2| + |x-3|$. Or even $f(x) = |x|$. – Flounderer Mar 29 '17 at 02:55
  • Not sure if this was your point but I can see this proof won't always work if there are ties in the data set, e.g. if the $x_i$ are 1,1,1,3. I modified the answer to indicate this applies when the $x_i$ are all distinct, e.g. the median of a sample from a continuous distribution. – gammer Mar 29 '17 at 03:09