# L1 regression versus L2 regression

I am trying to develop an intuition for why L1 regression is more expensive than L2 regression. Can somebody point me to some material that explains why this is the case

• Because this doesn't point to material, it isn't an answer, but it may give you some insight: L1 regression of $n$ values against a constant fits a median (which might not be unique), whereas L2 regression fits the mean. Finding the mean is obviously a $O(n)$ computation needing only $O(1)$ local storage. Finding a median naively takes $O(n^2)$, requires $O(n\log(n))$ with the best available sorting algorithms, and actually needs only $O(n)$ time and $O(n)$ storage provided a clever algorithm is used. That algorithm is considerably harder to code than one for the mean.
– whuber
Oct 18, 2011 at 18:53
• Oct 18, 2011 at 19:12
• @whuber: A very simple randomized linear-time algorithm exists for finding a median. It can probably be written in a handful of lines of code in a modern programming language and is a very popular implementation of this in numerical-algorithm libraries, particularly because it is fully general (i.e., the same algorithm works for all order statistics). :) Oct 18, 2011 at 19:18
• @cardinal Yes, I'm aware of those algorithms. But do you really think they are comparable in ease of coding and understanding to the simple loop that computes a mean? And then consider the online problem: when you are fed a stream of numbers and need to update a running mean or median (or quantile), the difficulty of re-computing a median (compared to the mean) becomes apparent. But I'm not claiming either problem is hard in any absolute sense...
– whuber
Oct 18, 2011 at 19:40
• @whuber: I agree that in an online situation, the difficulties mount. Viewing the L1 regression as an LP makes somewhat clearer why it might be more "expensive" than standard regression in many cases. Oct 18, 2011 at 19:49