Minimizing the Sum of Absolute Deviation ($ {L}_{1} $ Distance)

Question

I have a data set $x_{1}, x_{2}, \ldots, x_{k}$ and want to find the parameter $m$ such that it minimizes the sum $$\sum_{i=1}^{k}\big|m-x_i\big|.$$ that is

$$\min_{m}\sum_{i=1}^{k}\big|m-x_i\big|.$$

Answer 1

Probably you ask for a proof that the median solves the problem? Well, this can be done like this:

The objective is piecewise linear and hence differentiable except for the points $m=x_i$. What is the slope of the objective is some point $m\neq x_i$? Well, the slope is the sum of the slopes of the mappings $m\mapsto |m-x_j|$ and this is either $+1$ (for $m>x_j$) or $-1$ (for $m<x_j$ ). Hence, the slope indicates how many $x_i$'s are smaller than $m$. You see that the slope is zero if there are equally many $x_i$'s smaller and larger than $m$ (for and even number of $x_i$'s). If there is an odd number of $x_i$'s then the slope is $-1$ left of the "middlest" one and $+1$ right of it, hence the middlest one is the minimum.

Answer 2

A generalization of this problem to multiple dimensions is called the geometric median problem. As David points out, the median is the solution for the 1-D case; there, you could use median-finding selection algorithms, which are more efficient than sorting. Sorts are $O(n\log n)$ whereas selection algorithms are $O(n)$; sorts are only more efficient if multiple selections are needed, in which case you could sort (expensively) once, and then repeatedly select from the sorted list.

The link to the geometric median problem mentions solutions for multidimensional cases.

Answer 3

The explicit solution in terms of the median is correct, but in response to a comment by mayenew, here's another approach.

It is well-known that $\ell^1$ minimization problems generally, and the posted problem in particular, can be solved by linear programming.

The following LP formulation will do for the given exercise with unknowns $z_i,m$:

$$ min \sum z_i $$ such that: $$ z_i \ge m - x_i $$ $$ z_i \ge x_i - m $$

Clearly $z_i$ must equal $|x_i - m|$ at the minimum, so this asks the sum of absolute values of errors to be minimized.

Answer 4

The over-powered convex analysis way to show this is just take subgradients. In fact this is equivalent to the reasoning used in some of the other answers involving slopes.

The optimization problem is convex (because the objective is convex and there are no constraints.) Also, the subgradient of $\left|m-x_i\right|$ is

-1 if $m<x_i$

[-1,1] if $m=x_i$

+1 if $m>x_i$.

Since a convex function is minimized if and only if it's subgradient contains zero, and the subgradient of a sum of convex functions is the (set) sum of the subgradients, you get that 0 is in the subgradient if and only if $m$ is the median of $x_1,\ldots x_k$.

Answer 5

We're basically after: $$ \arg \min_{m} \sum_{i = 1}^{N} \left| m - {x}_{i} \right| $$

One should notice that $ \frac{\mathrm{d} \left | x \right | }{\mathrm{d} x} = \operatorname{sign} \left( x \right) $ (Being more rigorous would say it is a Sub Gradient of the non smooth $ {L}_{1} $ Norm function).
Hence, deriving the sum above yields $ \sum_{i = 1}^{N} \operatorname{sign} \left( m - {x}_{i} \right) $.
This equals to zero only when the number of positive items equals the number of negative which happens when $ m = \operatorname{median} \left\{ {x}_{1}, {x}_{2}, \cdots, {x}_{N} \right\} $.

One should notice that the median of a discrete group is not uniquely defined.
Moreover, it is not necessarily an item within the group.