Does L1 regularization always generate a sparse solution?
I think with your red cross you have in mind the case where $w_1 = w_2$. You are right that in this scenario the solution will not be sparse, since you will also get $w^*_1 = w^*_2$. 

However, whenever the coordinates of the red cross are off the line $y=x$ ($w_1\neq w_2$), you can shrink the regularization region so much that eventually you will end up with a similar picture as Figure 3.4 above. 

Say your red cross has the coordinates $w_1=r_1$ and $w_2=r_2$ and say your regularization strength is such that $||w||_1 = |w_1|+|w_2| \leq C$ where $C$ defines the size of the shaded region.



Then, for the circular contours, the optimal solution will be where the line $w^*_2 = C- w^*_1$ (for the boundary region) and the line through the red cross at $(r_1,r_2)$ running orthogonal to the boundary region intersect. You can see that the latter has the form $w_2 = f(w_1) = 1\cdot w_1 + r_2 - r_1$. (Orthogonality gives you slope +1 because the boundary region has slope -1.) Setting them equal gives you the intersection at coordinates $w^*_1 = \frac{C+r_1-r_2}{2}$ and $w^*_2 = \frac{C-r_1+r_2}{2}$.

Now, if $r_2=r_1$ you have $w^*_1=w^*_2$ independent of $C$ and the solution won't be sparse.

If $r_1&gt;r_2$ (i.e. you are below the first diagonal) shrinking $C$ to $r_1-r_2&gt;0$ yields $w^*_2=0$ but $w^*_1&gt;0$. You end up in the right corner of the regularization region. (Similar to my image.)

If $r_2&gt;r_1$ (i.e. you are above the first diagonal) shrinking $C$ to $r_2-r_1&gt;0$ yields $w^*_1=0$ but $w^*_2&gt;0$. You end up in the top corner of the regularization region. (Similar to your image.)

As Emre mentioned in the comments, this holds in general and you can "see" this from the Kuhn-Tucker conditions of the optimization problem.