1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.