§ Median minimizes L1 norm

Consider the meadian of xs[1..N]xs[1..N]. We want to show that the median minimizes the L1 norm L1(y)=∑i∣xs[i]−y∣L_1(y) = \sum_i |xs[i] - y|. If we differentiate L1(y)L_1(y) with respect to yy, we get:
dL1(y)/y=∑i−sign(xs[i]−y) d L_1(y)/y = \sum_i - \texttt{sign}(xs[i] - y)
Recall that d(∣x∣)/dx=sign(x)d(|x|)/dx = \texttt{sign}(x) Hence, the best yy to minimize the L1L_1 norm is the value that makes the sum of the signs ∑isign(xs[i]−y)\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+12k + 1, kk elements will have sign −1-1, the middle element will have sign 00, and the kk elements after will have sign +1+1. The sum will be 00 since half of the −1-1 and the +1+1cancel each other out.
  2. Similar things happen for even, except that we can get a best total sign distance of +1+1using 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 xsxs has only two elements, with xs[0]<xs[1]xs[0] < xs[1]. Then the objective function to minimize the L1 norm, ie, to minimize ∣xs[1]−y∣+∣xs[2]−y∣|xs[1] - y| + |xs[2] - y|. This is satisfied by any point in between xs[1]xs[1] and xs[2]xs[2]. In the general case, assume that xs[1]<xs[2]⋯<xs[N]xs[1] < xs[2] \dots < xs[N]. Pick the smallest number xs[1]xs[1] and the largest number xs[N]xs[N]. We have that any yy between xs[1]xs[1] and xs[N]xs[N] satisfies the condition. Now, drop off xs[1]xs[1] and xs[N]xs[N], knowing that we must have y∈[xs[1],xs[N]]y \in [xs[1], xs[N]]. Recurse. At the end, we maybe left with a single element xs[k]xs[k]. In such a case, we need to minimize ∣xs[k]−y∣|xs[k] - y|. That is, we set xs[k]=yxs[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∈[l,r]y \in [l, r] minimizes ∣y−l∣+∣y−r∣|y - l| + |y - r|!