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.

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.
