Must convex function $f(x)$ bounded by $\|x\|_0$ be bounded by $\|x\|_1$? One of my professors stated the following result without proof: Suppose that $f \colon \mathbb{R}^p \to \mathbb{R}$ is convex such that $f({\bf x}) \leq \|{\bf x}\|_0$, then $f({\bf x}) \leq \|{\bf x}\|_1$. (Recall that $\|{\bf x}\|_0$ counts the number of non-zero components of ${\bf x}$). The argument for $p = 1$ is fairly easy, but I did not see a way to prove this result in higher dimensions. Thank you very much!
Edit: we might need $f$ to be defined only on a bounded (convex) subset of $\mathbb{R}^p$ in order to avoid triviality.
 A: Here is a proof when $f : X \to \mathbb{R}$ such that $\{\mathbf{x} \in \mathbb{R}^p : \|\mathbf{x}\|_1 \leq p\} \subseteq X$ that requires no special tools.
Let $\mathbf{x} \in X$.  If $\|\mathbf{x}\|_1 \not\in (0, p)$, then $f(\mathbf{x}) \le \|\mathbf{x}\|_0 \leq \|\mathbf{x}\|_1,$ so we may assume $\|\mathbf{x}\|_1 \in (0,p)$.  Then $\frac{p}{\|\mathbf{x}\|_1}\mathbf{x} \in X$ and
$$\begin{align*}f(\mathbf{x}) &= f\left(\left(1 - \frac{\|\mathbf{x}\|_1}{p}\right)\mathbf{0} + \frac{\|\mathbf{x}\|_1}{p}\left(\frac{p}{\|\mathbf{x}\|_1}\mathbf{x}\right)\right) \\ &\leq \left(1 - \frac{\|\mathbf{x}\|_1}{p}\right)f(\mathbf{0}) + \frac{\|\mathbf{x}\|_1}{p}f\left(\frac{p}{\|\mathbf{x}\|_1}\mathbf{x}\right) \\ &\leq \left(1 - \frac{\|\mathbf{x}\|_1}{p}\right)\|\mathbf{0}\|_0 + \frac{\|\mathbf{x}\|_1}{p}\left\|\frac{p}{\|\mathbf{x}\|_1}\mathbf{x}\right\|_0 \\ &\leq \left(1 - \frac{\|\mathbf{x}\|_1}{p}\right)(0) + \frac{\|\mathbf{x}\|_1}{p}(p) \\ &= \|\mathbf{x}\|_1\end{align*}$$
Note that as long as $X$ contains a neighborhood of $\mathbf{0}$, it becomes more difficult to prove as $X$ shrinks, so my result here is not unexpected if you accept the proof that it's true when $X$ is the unit ball in $(\mathbb{R}^p, \|\cdot\|_\infty)$.
A: First, this is true on the $l^\infty$ ball only. Once you make that assumption, you are trying to prove that the $l^1$ norm is the tightest convex envelope of the $l^0$ norm, so what you are trying to prove is that the Fenchel dual of the Fenchel dual of $\| \cdot \|_0$ is the $\| \cdot\|_1.$ Now, the fenchel dual of $f$ is
$$f^*(\mu) = \sup_x ( \mu \cdot x - f(x)).$$
It is not hard to see that $$\|\mu\|^* = \sum_{i=1}^p (|\mu_i| -1).$$ Whence the result follows (exercise to do the second dual).
Form more detail on Fenchel duals, check out Rockafellar or Boyd and Vanderberghe.
