§ Median minimizes L1 norm
Consider the meadian of . We want to show that the median minimizes
the L1 norm . If we differentiate with
respect to , we get:
Hence, the best to minimize the norm is the value that makes the sum
of the signs minimal. The median is perfect
for this optimization problem.
- When the list has an odd number of elements, say, , elements will have sign , the middle element will have sign , and the elements after will have sign . The sum will be since half of the and the cancel each other out.
- Similar things happen for even, except that we can get a best total sign distance of 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 has only two elements, with .
Then the objective function to minimize the L1 norm, ie, to minimize
. This is satisfied by any point in
between and .
In the general case, assume that . Pick the smallest
number and the largest number . We have that any between
and satisfies the condition. Now, drop off and , knowing
that we must have . Recurse.
At the end, we maybe left with a single element . In such a case, we need
to minimize . That is, we set .
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 minimizes