L1 ball contained in convex hull of L0 ball
Matthew Harrington 
Consider the set $S$: the set of vectors whose $L^0$ pseudo-norm is upper bounded by $s$. Also, consider the $L^1$ ball of radius $\sqrt{s}$. It is apparently a well known fact that the $L^1$ ball is contained in 2 x the convex hull of $S$.
I am referring to the proof of lemma 3.1 here:
What I don't understand, is why is it that
$\sum_{i} \| x_{T_i} \|$ has to be bounded to show that the scaling factor is 2?
$\endgroup$1 Answer
$\begingroup$We want to check that $x$ is expressible as a convex combination of points in $2 S_{n,s}$. That is, we want $$ x = \sum_i \theta_i y_i $$ Where $\sum_i \theta_i = 1$, $\theta_i \ge 0$, and $y_i \in 2 S_{n,s}$. Actually, since $0\in 2S_{n,s}$, it's sufficient to show that $\sum_i \theta_i \le 1$.
Let $y_i = 2 x_{T_i} /\|x_{T_i}\|$ and $\theta_i = \|x_{T_i}\|/2$. Then $y_i \in 2 S_{n,s}$, and $\theta_i \ge 0$ and then the condition $\sum_i \theta_i \le 1$ is equivalent to:
$$ \sum_i \|x_{T_i}\|/2 \le 1 $$
which is the condition proved in the paper.
$\endgroup$
