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.

Rodrigo de Azevedo
  • 1
Fei Cao
  • 2,830
  • I would assume you need a bounded domain in order to be interesting. Isn't a convex function $f : \mathbb{R}^p \to \mathbb{R}$ which is bounded above (here, $f \leq p$) a constant function? In which case $f(\mathbf{x}) = f(\mathbf{0}) \leq |0|_0 = 0 \leq |\mathbf{x}|_1$? – Brian Moehring Mar 29 '21 at 03:10
  • Thanks for your comment. I am actually not familiar with the result that you mentioned, it might be true that we need $f$ to be defined only on a bounded (convex) subset of $\mathbb{R}^p$ – Fei Cao Mar 29 '21 at 03:14

2 Answers2

1

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)$.

Brian Moehring
  • 21,088
0

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.

Rodrigo de Azevedo
  • 1
Igor Rivin
  • 25,994
  • 1
  • 19
  • 40
  • Thanks! However, I didn't expect an answer that requires such level of technicality. I am expecting for a more elementary treatment... – Fei Cao Mar 29 '21 at 03:11
  • 1
    @FeiCao And I am expecting a million dollars in the mail. Let's hope we both get lucky. – Igor Rivin Mar 29 '21 at 03:32
  • On your first statement ("this is true on the $\ell^\infty$ ball only"), it seems to me that if it works for the $\ell^\infty$ unit ball, then it would also be true for any convex domain containing the $\ell^\infty$ unit ball as a subset (since in particular the statement becomes trivial outside $|x|_1 < p$), but that the $\ell^\infty$ unit ball is the crucial case. Does that make sense, or am I missing something? – Brian Moehring Mar 29 '21 at 03:33
  • @BrianMoehring Notice that the $l^0$ norm is not really a norm, and in particular is bounded, so the Fenchel duality argument breaks down completely - the sup blows up. – Igor Rivin Mar 29 '21 at 03:36
  • 1
    This is the first I've heard of the Fenchel dual, but I'm not commenting on whether your proof extends to larger domains, so I didn't figure it mattered. I'm just saying that the larger the domain, the easier it would seem to be for a convex function $f$ to satisfy $$(\forall \mathbf{x}, f(\mathbf{x}) \leq |\mathbf{x}|_0) \implies (\forall \mathbf{x}, f(\mathbf{x}) \leq |\mathbf{x}|_1).$$ It definitely fails for very small domains where $|x|_1 \approx 0$, and it eventually becomes trivially true for very large domains (anything containing the ball ${|x|_1 < p}$) – Brian Moehring Mar 29 '21 at 03:48
  • @BrianMoehring May I know why my question is trivial ? (since the domain of $f$ contains the ball ${|{\bf x}|_1 \leq p }$) – Fei Cao Mar 29 '21 at 17:41
  • @FeiCao Conceptually, it's because $|\cdot|_1$ is linear on any ray starting at the origin, so all you have to show is that $|\cdot|_1$ majorizes $f$ at some point far enough out on the ray. In case you want to see the details or have any more questions, I'm writing an answer for this case. – Brian Moehring Mar 29 '21 at 19:28
  • @IgorRivin " And I am expecting a million dollars in the mail. Let's hope we both get lucky." Based on your profile, it seems that you are already a professor! That's cool! – Fei Cao Mar 29 '21 at 21:26