34
$\begingroup$

I know that $p$-norm of $x\in\Bbb{R}^n$ is defined as, for all $p\ge1$,$$\Vert{x}\Vert_p=\left(\sum_{i=1}^{n} \vert{x_i}\vert^p\right)^{1/p}.$$

The textbook refers to "Every norm is convex" for an example of convex functions.

I failed to prove $f(x)=\Vert{x}\Vert_p$ for all $p\ge1$, then tried to find the proof on the internet but I cannot find it.

Can someone let me understand why $p$-norm is convex for all $p\ge1$.

$\endgroup$
2
  • 6
    $\begingroup$ en.wikipedia.org/wiki/Minkowski_inequality or did you want an intuition? Anyway using the triangle inequality: $||\lambda a+(1-\lambda) b|| \le ||\lambda a|| +||(1-\lambda) b||=\lambda ||a|| +(1-\lambda)||b||$ $\endgroup$
    – Felix B.
    Commented May 14, 2017 at 10:41
  • $\begingroup$ @FelixB. Triangular inequality?? Hmm... I will try it again. Thank you. $\endgroup$
    – Danny_Kim
    Commented May 15, 2017 at 14:43

1 Answer 1

66
$\begingroup$

The Definition of a norm is:

Be V a Vectorspace, $\|\cdot\|: V \rightarrow \mathbb{R} $ is a norm $:\iff $

  1. $\forall v \in V: \|v\|\ge0$ and $\|v\| =0 \iff v=0$ (positive/definite)
  2. $\forall v\in V, \lambda\in \mathbb{R}: |\lambda|\|v\| =\|\lambda v\|$ (absolutely scaleable)
  3. $\forall v,w\in V : \|v+w\| \le \|v\|+\|w\|$ (Triangle inequality)

The Definition of convex is:

$f:V\rightarrow\mathbb{R}$ is convex $:\iff$ $\forall v,w \in V, \lambda \in [0,1]: f(\lambda v+(1-\lambda )w)\le \lambda f(v) +(1-\lambda)f(w)$

So using the Triangle inequality and the fact that the norm is absolutely scalable, you can see that every Norm is convex: $$\|\lambda v+(1-\lambda )w\|\le\|\lambda v\|+\|(1-\lambda)w\| = \lambda\|v\|+(1- \lambda)\|w\|$$

So by definition every norm is convex. What is left to show is, that the p-norm is in fact a norm. The first two requirements are pretty easy to show, the third is hard. That is why it has its own name: the Minkowski Inequality which is a result of the Hölder inequality and shows that the triangle inequality holds for every p-norm (if p>1) and thus that it is a norm.


EDIT: Since this seems to be somewhat popular, I thought I would add a sketch of the proof of the Minkowski inequality.

  1. You show Young's Inequality: $xy\le \frac{x^p}{p}+\frac{y^q}{q}\quad \forall q,p>1 \text{ with } \frac{1}{p}+\frac{1}{q}=1,\ \forall x,y\ge 0$.

You can do that by looking at the function $f(x)=\frac{x^p}{p}+\frac{y^q}{q}-xy$ find the critical point, show it is a minimum and is greater zero (derivatives).

  1. You show the Hölder Inequality: $\|fg\|_1 \le \|f\|_p\|g\|_q \quad \forall q,p>1 \text{ with } \frac{1}{p}+\frac{1}{q}=1$

You can do that by setting $x=\frac{|f|}{||f||_p}$ and $y=\frac{|g|}{||g||_q}$ and plug them into young's inequality. You get \begin{align} &&\frac{|fg|}{\|f\|_p\|g\|_q}&\le \frac{|f|^p}{p\|f\|_p^p} + \frac{|g|^q}{q\|g\|_q^q} \\ \Rightarrow &&\int \frac{|fg|}{\|f\|_p\|g\|_q} d\mu &\le \int \frac{|f|^p}{p\|f\|_p^p}d\mu + \int \frac{|g|^q}{q\|g\|_q^q}d\mu \\ \Rightarrow &&\frac{\|fg\|_1}{\|f\|_p\|g\|_q}&\le \frac{1}{p}+\frac{1}{q}=1 \end{align} It works just the same for sequences or $\mathbb{R}^n$, you just use young's inequality for every index and then sum over it instead of using the integral.

  1. And last the Minkowski Inequality: $\|x+y\|_p\le\|x\|_p+\|y\|_p \quad \forall p>1$

Set $q=\frac{p}{p-1}$ thus $q(p-1)=p$ and $\frac{1}{p}+\frac{1}{q}=1$. Then: \begin{align} \|x+y\|_p^p&=\int |x+y|^pd\mu\le\int |x+y|^{p-1}|x|d\mu+ \int |x+y|^{p-1}|y|d\mu \\ &\le \left(\int|x+y|^{q(p-1)}d\mu\right)^{1/q}\left(\int|x|^pd\mu\right)^{1/p} + \left(\int|x+y|^{q(p-1)}d\mu\right)^{1/q}\left(\int|y|^pd\mu\right)^{1/p} \\ &=\left(\int|x+y|^{p}d\mu\right)^{\frac{1}{p}\frac{p}{q}}(\|x\|_p+\|y\|_p) =\|x+y\|_p^{p/q}(\|x\|_p+\|y\|_p) \end{align}

If you realize that $p-\frac{p}{q}=p(1-\frac{1}{q})=1$ you are done.

$\endgroup$
3
  • 1
    $\begingroup$ This is the perfect explanation among what I have seen so far. Thank you. $\endgroup$
    – Danny_Kim
    Commented May 17, 2017 at 4:25
  • $\begingroup$ Is it correct that the : means the relation: "What is left of the : does/means what is right of the :? I derived that meaning from the function arrow description on en.wikipedia.org/wiki/List_of_mathematical_symbols, but I could not find a direct reference. $\endgroup$
    – a.t.
    Commented Feb 23, 2019 at 12:57
  • 1
    $\begingroup$ @a.t. Yes, in $:\Leftrightarrow$ and $:=$, the colons indicate that it is a definition. The colon by itself between two statements is simply a separator and should be read as "such that". For example $\forall x\in X : f(x)=y$ "For all x in X such that f(x)=y" $\endgroup$
    – Felix B.
    Commented Feb 23, 2019 at 17:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .