Why $l_1$ norm is the convex hull of the intersection of $l_0$ norm and $l_\inf$ norm?

Question

Under the topic of convex optimization, I am reading in my notes that "the $l_1 norm$ ball is the convex hull of the intersection between the $l_0$ “norm” ball and the $l_\inf $-norm ball". Why is this the case? Isn't the intersection of these two norms just $l_0$-norm? How come that their convex hull is $l_1$ norm?

Answer 1

I understand that $\ell_0$ "norm" means the number of nonzero components of the vector. Thus, the "$\ell_0$ unit ball" is the union of all coordinate axes. For example, in three dimensions it is $$\{(x,0,0):x\in\mathbb{R}\}\cup \{(0,y,0):y\in\mathbb{R}\} \cup \{(0,0,z):z\in\mathbb{R}\}$$

Intersecting this set with the $\ell^\infty$-unit ball, we get the union of segments such as $$\{(x,0,0):|x|\le 1\}\cup \{(0,y,0):|y|\le 1 \} \cup \{(0,0,z):|z|\le 1 \}$$ The convex hull of the latter set is the same as the convex hull of $\{(\pm 1, 0, 0), (0, \pm1,0), (0,0,\pm1)\}$, i.e., an octahedron, the unit ball of $\ell^1$. Same in other dimensions.