7
$\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$
  • 5
    $\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. May 14 '17 at 10:41
  • $\begingroup$ @FelixB. Triangular inequality?? Hmm... I will try it again. Thank you. $\endgroup$ – Danny_Kim May 15 '17 at 14:43
23
$\begingroup$

The Definition of a norm is:

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

  1. $\forall v \in V: \|v\|\ge0$ and $\|v\| =0 \Leftrightarrow 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 $:\Leftrightarrow$ $\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 scaleable, 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 extremum, 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$
  • 1
    $\begingroup$ This is the perfect explanation among what I have seen so far. Thank you. $\endgroup$ – Danny_Kim May 17 '17 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. Feb 23 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. Feb 23 at 17:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.