## § Median minimizes L1 norm

Consider the meadian of $xs[1..N]$. We want to show that the median minimizes the L1 norm $L_1(y) = \sum_i |xs[i] - y|$. If we differentiate $L_1(y)$ with respect to $y$, we get:
$d L_1(y)/y = \sum_i - \texttt{sign}(xs[i] - y)$
Recall that $d(|x|)/dx = \texttt{sign}(x)$ Hence, the best $y$ to minimize the $L_1$ norm is the value that makes the sum of the signs $\sum_i \texttt{sign}(xs[i] - y)$ minimal. The median is perfect for this optimization problem.
1. When the list has an odd number of elements, say, $2k + 1$, $k$ elements will have sign $-1$, the middle element will have sign $0$, and the $k$ elements after will have sign $+1$. The sum will be $0$ since half of the $-1$ and the $+1$cancel each other out.
2. Similar things happen for even, except that we can get a best total sign distance of $+1$using either of the middle elements.

#### § Proof 2:

Math.se has a nice picture proof abot walking from left to right.

#### § Proof 3:

Consider the case where $xs$ has only two elements, with $xs < xs$. Then the objective function to minimize the L1 norm, ie, to minimize $|xs - y| + |xs - y|$. This is satisfied by any point in between $xs$ and $xs$. In the general case, assume that $xs < xs \dots < xs[N]$. Pick the smallest number $xs$ and the largest number $xs[N]$. We have that any $y$ between $xs$ and $xs[N]$ satisfies the condition. Now, drop off $xs$ and $xs[N]$, knowing that we must have $y \in [xs, xs[N]]$. Recurse. At the end, we maybe left with a single element $xs[k]$. In such a case, we need to minimize $|xs[k] - y|$. That is, we set $xs[k] = y$. On the other hand, we maybe left with two elements. In this case, any point between the two elements is a legal element. We may think of this process as gradually "trapping" the median between the extremes, using the fact that that any point $y \in [l, r]$ minimizes $|y - l| + |y - r|$!