How does the l1 norm exclude outliers? I have read that using the l1 norm is useful as it excludes the effect of outliers when, for example, finding a linear approximation to a set of data points. However, I can't quite see how this works.
Any hints?
 A: The $\ell_1$-norm is less sensitive to outliers than the $\ell_2$-norm.  For example, suppose that we are trying to find a vector $x$ such that $Ax \approx b$, but certain components of $b$ are "wrong" or corrupted.  So it's ok for $(Ax - b)_i$ to be large if the $i$th component of $b$ is corrupted -- we only care about agreement with the uncorrupted components of $b$.  
We could try minimizing $\| Ax - b \|_2^2$, but the $\ell_2$-norm simply hates for any of the components of the residual $Ax - b$ to be large, because the $\ell_2$-norm squares those components, making them huge -- a disaster.  The $\ell_1$-norm, on the other hand, does not mind so much if some of the components of the residual $Ax - b$ are large.  (Those large components don't get squared, so it's not such a big deal.)
The $\ell_1$-norm is also more irritated by small components in the residual than the $\ell_2$-norm.  (The $\ell_2$-norm squares small components, making them tiny and negligible.)  So the $\ell_1$-norm is willing to have a few components of the residual be large (not a disaster), if it helps to avoid having a lot of small nonzero components (which would be quite irritating).
A slightly different viewpoint is that penalizing the $\ell_1$-norm of the residual $Ax - b$ encourages the residual $Ax - b$ to be sparse: most components equal to $0$, with a few large components allowed.  That's just what we want to happen if a few of the components of $b$ are outliers.  You can find a picture here (and similar pictures elsewhere) that help to explain why penalizing the $\ell_1$-norm promotes sparsity.
Another useful penalty function is the Huber penalty, which is a smoothed out version of the $\ell_1$-norm.  It's like the $\ell_1$-norm, except it's quadratic near the origin.  The Huber penalty, like the $\ell_1$-norm, is not so sensitive to outliers.
This is discussed more thoroughly in chapter 6 of Boyd and Vandenberghe.  See figure 6.5 and 6.2, for example.
A: A better way to look at this is to note that the $\ell_1$ norm (or absolute error) is minimized by the median of the target distribution. See Why does minimizing the MAE lead to forecasting the median and not the mean? Therefore, for instance, the $\ell_1$ loss is used in quantile regression for the median.
And of course the median (and therefore the $\ell_1$ minimizer) is much less influenced by the tails of your distribution.
The potential downside is that the median of your distribution will usually not be the same as the mean. That is: the $\ell_1$ minimizing prediction will not be the conditional expectation. That in turn is: it will be biased. The optimizing point prediction is a functional of the target distribution and depends on the eliciting error measure (Kolassa, 2020 - yes, that is self-promotion).
Note that "outliers" may well be bona fide members of your distribution. Blindly removing outliers without good reason is not good practice. This is related to the bias mentioned in the previous paragraph: don't just use an error measure because "it is useful as it excludes the effect of outliers". Think about which functional of the target distribution you want to elicit, and then choose an appropriate error measure.
