Interpreting norm definition

Book: Convex Optimization (Author: Stephen Boyd), Appendix A, Topic: A.1.2 Norm,distance, and unit ball

$$\| x \| =(\sup\{ t \geq0 \mid tx \in C\})^{-1}$$

where $C\subseteq R^n$ and satisfies these three properties 1) $C$ is symmetric. 2) $C$ is convex. 3) $C$ is closed,bounded, and has non empty interior.

I am familiar with $\parallel x \parallel_{p}$ norm definition but I have not been able to establish the equivalence between the two definitions.

• The $\lVert\,\cdot\,\rVert_p$ norms are special cases. The definition is such that for every $x$, $\lVert x\rVert$ is the factor by which $C$ must be scaled so that $x$ is on the boundary of the scaled set $\lVert x\rVert\cdot C$. It would probably have been better to indicate the dependence on $C$, e.g. by writing $\lVert x\rVert_C$. That is also known as the Minkowski functional of $C$, googling "Minkowski functional" may turn up enlightening links. – Daniel Fischer Jan 10 '15 at 23:52
• Could you please clarify your question? Any function $p$ defined in $R^n$ that satisfies: i) $p(a\cdot x)=|a|\cdot p(x)$ for any $a$ scalar; ii) $p(x+y)\le p(x)+p(y)$; and iii) $p(x)=0$ iff $x=0$; is what we call a norm. – Sergio Parreiras Jan 10 '15 at 23:52
• Why do "expert people" find questions like this so bad that they vote negatively. I had tagged it under "self learning". This is like very unfair. I asked for someone to help me understand a definition from a well referenced text book…is it a crime. I am sorry, I couldn't come up with a challenging question that could give you a chance to show off your expertise – NAASI Jan 11 '15 at 0:14
• @ Daniel. Thank you for giving some clue. – NAASI Jan 11 '15 at 0:15
• Ignore the votes. – copper.hat Jan 11 '15 at 0:24

An equivalent definition is $\|x\|_C = \inf \{ t>0 | {x \over t } \in C \}$. This is a little more convenient here.

Let $C = \bar{B}(0,1)$, with the $\|\cdot\|_p$ norm.

If $\|x\|_p \le t$, then ${x \over t} \in C$, and so $\|x\|_C \le t$.

If $\|x\|_p > t$, then for some $\epsilon>0$ we have $\|x\|_p > t+\epsilon$. Then $\|{x \over s} \|_p >1$ for all $0<s \le t+\epsilon$ and so ${x \over s} \notin C$ for all $0<s \le t+\epsilon$, and so $\|x\|_C \ge t+\epsilon > t$.

Hence $\|x\|_p = \|x\|_C$.

Note: The above argument works for any norm $\|\cdot\|_*$ (not just the $\|\cdot\|_p$ norm) and shows that we have $\|\cdot\|_* = \|\cdot\|_{\{x | \|x\|_*\le 1\}}$.

First, note that on $\mathbb{R}^n$, all norms are equivalent. Hence requiring $C$ to have some topological aspects (boundedness and non empty interior) are not as circular as they might appear at first.

If $\|\cdot\|$ is any norm, let $C = \{x | \|x\| \le 1 \}$. Then the above argument shows that $\|\cdot\| = \|\cdot\|_C$. If $x \in C$, then since $\|-x\| = \|x\|$, we have $-x \in C$ and so $C$ is symmetric. Since $x \mapsto \|x\|$ is convex, it follows that $C$ is convex. $C$ is obviously bounded, and since $\{ x | \|x\|<1 \} \subset C$, we see that $C$ has a non empty interior.

Now suppose that $C$ is convex, balanced, bounded and has a non empty interior. Note that these conditions imply that $0$ is in the interior of $C$.

Let $n(x) = \inf \{ t>0 | {x \over t } \in C \}$. We want to show that $n$ is a norm. Since ${0 \over t} \in C$ for all $t >0$, we see that $n(0) = 0$. Now suppose $x \neq 0$. Since $C$ is bounded, there is some $s >0$ such that $x \notin t C$ for all $t \le s$, and so $n(x) \ge s >0$. Since $0 \in C^\circ$, we see that there is some $t>0$ such that ${x \over t} \in C$, and so $n(x) < \infty$, hence it takes values in $(0,\infty)$.

If $\lambda \ge 0$, we see that $\{ t>0 | {\lambda x \over t } \in C \} = \lambda \{ t>0 | {x \over t } \in C \}$, and since $C$ is balanced, we have $\{ t>0 | {x \over t } \in C \} = \{ t>0 | {-x \over t } \in C \}$, from which we get $\{ t>0 | {\lambda x \over t } \in C \} = |\lambda| \{ t>0 | {x \over t } \in C \}$, and so $n(\lambda x) = |\lambda| n(x)$.

Finally, suppose ${x \over \alpha} \in C$ and ${y \over \beta} \in C$ for some $\alpha,\beta >0$, then since $C$ is convex, we have ${\alpha \over \alpha + \beta} {x \over \alpha} + {\beta \over \alpha + \beta} {y \over \beta} = {x+y \over \alpha + \beta} \in C$. Consequently, we have $n(x+y) \le \alpha+\beta$, and taking the $\inf$ over the appropriate $\alpha,\beta$ gives $n(x+y) \le n(x)+n(y)$, and so $n$ is subadditive.

Hence $n$ is a norm.

• This is good, but of course $C$ does not need to be a norm ball. (Well, it is once you define a norm with it! But that is self-referential.) – Michael Grant Jan 11 '15 at 23:21
• @MichaelGrant: The question is a wee bit ambiguous, so I interpreted it as showing the equivalence between the $\|\cdot\|_p$ norm and the gauge-based definition. (Of course, I neglected to show that the $C$ above is symmetric, bounded and absorbing...) – copper.hat Jan 11 '15 at 23:48
• @MichaelGrant: I added a lot more detail... – copper.hat Jan 12 '15 at 6:40
• Great! Too bad I can't vote twice! ;-) – Michael Grant Jan 12 '15 at 12:37

For any norm (with respect to the definiton you are familiar with) $\Vert \cdot \Vert$ look at $C= \{ x \in \mathbb R : \Vert x \Vert \le 1 \}$

This set satisfies the 3 conditions and if you define a norm using the "new" definition and this $C$, the result is the norm you started with.

Hope this helps

• As I commented with copper.hat, this is self-referential. What if C is not the ball of a previously-defined norm? – Michael Grant Jan 11 '15 at 23:23
• This answer is supposed to show the connection between both definitions of a norm... – GenericNickname Jan 12 '15 at 7:16