I am reading books about linear regression. There are some sentences about the L1 and L2 norm. I know the formulas, but I don't understand why the L1 norm enforces sparsity in models. Can someone give a simple explanation?
Consider the vector $\vec{x}=(1,\varepsilon)\in\mathbb{R}^2$ where $\varepsilon>0$ is small. The $l_1$ and $l_2$ norms of $\vec{x}$, respectively, are given by

$$||\vec{x}||_1 = 1+\varepsilon,\ \ ||\vec{x}||_2^2 = 1+\varepsilon^2$$

Now say that, as part of some regularization procedure, we are going to reduce the magnitude of one of the elements of $\vec{x}$ by $\delta\leq\varepsilon$. If we change $x_1$ to $1-\delta$, the resulting norms are

$$||\vec{x}-(\delta,0)||_1 = 1-\delta+\varepsilon,\ \ ||\vec{x}-(\delta,0)||_2^2 = 1-2\delta+\delta^2+\varepsilon^2$$

On the other hand, reducing $x_2$ by $\delta$ gives norms

$$||\vec{x}-(0,\delta)||_1 = 1-\delta+\varepsilon,\ \ ||\vec{x}-(0,\delta)||_2^2 = 1-2\varepsilon\delta+\delta^2+\varepsilon^2$$

The thing to notice here is that, for an $l_2$ penalty, regularizing the larger term $x_1$ results in a much greater reduction in norm than doing so to the smaller term $x_2\approx 0$. For the $l_1$ penalty, however, the reduction is the same. Thus, when penalizing a model using the $l_2$ norm, it is highly unlikely that anything will ever be set to zero, since the reduction in $l_2$ norm going from $\varepsilon$ to $0$ is almost nonexistent when $\varepsilon$ is small. On the other hand, the reduction in $l_1$ norm is always equal to $\delta$, regardless of the quantity being penalized.

Another way to think of it: it's not so much that $l_1$ penalties encourage sparsity, but that $l_2$ penalties in some sense discourage sparsity by yielding diminishing returns as elements are moved closer to zero.
