Norms

Notation: for $x, y \in \mathbb{R}^n, x\cdot y = x^T y = \sum_{i=1}^n x_i y_i$

Definition

A function $f$ : $\mathbb{R}^n \rightarrow \mathbb{R}$ with $\text{dom}f = \mathbb{R}^n$ is called a norm if

$f$ is nonnegative: $f(x) \geq 0$ for all $x\in \mathbb{R}^n$
$f$ is definite: $f (x) = 0$ only if $x = 0$
$f$ is homogeneous: $f (t x) = | t | f (x)$ , for all $x \in \mathbb{R}^n$ and $t\in \mathbb{R}$
$f$ satisfies the triangle inequality: $f(x+y) \leq f(x) + f(y)$ , for all $x, y \in \mathbb{R}^n$

Unit ball

The set of all vectors with norm less than or equal to one,

$\mathcal{B} = \{ x \in \mathbb{R}^n | \|x\| \leq 1\},$

is called the unit ball of the norm $\|\cdot\|$ .

The unit ball satisfies the following properties:

$\mathcal{B}$ is symmetric about the origin, i.e., $x \in \mathcal{B}$ if and only if $-x \in \mathcal{B}$
$\mathcal{B}$ is convex
$\mathcal{B}$ is closed, bounded, and has nonempty interior

Conversely, if $C \subseteq \mathbb{R}^n$ is any set satisfying these three conditions, then it is the unit ball of a norm, which is given by

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

Exercise

Show that the triangle inequality for the norm is equivalent to convexity of the norm unit ball.

Examples

$\ell_1$ -norm, sum-absolute-value

$\|x\|_1 = |x_1| + \cdots + |x_n|.$

$\ell_2$ -norm, Euclidean

$\|x\|_2 = (x_{1}^{2} + \cdots + x_{n}^2)^{1/2}.$

$\ell_{\infty}$ -norm, Chebyshev

$\|x\|_{\infty} = \max \{ |x_1|, \cdots, |x_n| \}.$

$\ell_p$ -norm, $p \geq 1$

$\|x\|_p = (x_{1}^{p} + \cdots + x_{n}^p)^{1/p}.$

$\|x\|_M = \sqrt( x^t M x)$ for M a symmetric positive definite matrix

Note that the above formula yields the $\ell_1$ -norm when

p = 1

and the Euclidean norm when

p = 2

.

It is easy to show that for any $x \in \mathbb{R}^n,$

$\lim_{p\rightarrow \infty} \|x\|_p = \max \{ |x_1|, \cdots, |x_n| \},$

so the $\ell_p$ -norm also fits in this family, as a limit.

Illustration

$x = (x 1, x 2)$

$\|x\|_{1} = \max_{i}(x \cdot v_i)$

$v_i = \{ \pm (1,1),\pm (1,-1) \}$

Source code for making this figure: pstricks code

$\|x\|_{\infty} = \max_{i}(x \cdot v_i)$

$v_i = \{ (\pm 1,0),(0,\pm 1) \}$

$\|x\|_{\text{oct}} = \max_{i}(x \cdot v_i)$

$v_i = \{ \pm (0,1),\pm (1,0), \pm \frac{\sqrt{2}}{2}(1,1), \pm \frac{\sqrt{2}}{2} (1,-1) \}$

$\|x\|_{\text{oct}^{\ast}} = \max_{i}(x \cdot v_i)$

$v_i = \{ \pm (\sqrt{2}-1,1),\pm (1,\sqrt{2}-1), \pm (\sqrt{2}-1,-1),\pm (-1,\sqrt{2}-1) \}$

Exercise

Show oct, oct*-norm are dual norms. One way to do this is by computing the formula directly. Another way to do this is by noting that the unit balls in the dual norms are polars of each other, and by using a formula which relates the linear inequalities which define a polyhedral set to the vertices of the polar. See Convexity Notes

Dual norms

Definition

Let $\| \cdot \|$ be a norm on $\mathbb{R}^n$ . The associated dual norm, denoted $\| \cdot \|_\ast$ , is defined as

$\| z \|_\ast = \sup\{z^{T}x \max \|x\| \leq 1\}.$

Inequality

From the definition of dual norm we have th inequality $z^{T}x \leq \|x\| \|z\|_\ast,$ which holds for all $x$ and $z$ . This inequality is tight, in the following sense: for any $x$ there is a $z$ for which the inequality holds with equality. (Similarly, for any $z$ there is an $x$ that gives equality.)

Property

The dual of the dual norm is the original norm:

$\|x\|_{\ast \ast} = \|x\|$ for all

x

.

Exercise

Prove the dual of the dual norm is the original norm.

The dual of the Euclidean norm is th Euclidean norm:

$\sup \{z^{T}x \mid \|x\|_2 \leq 1\} = \|z\|_2.$

The dual of the $\ell_{\infty}$ -norm is the $\ell_{1}$ -norm:

$\sup\{ z^{T}x \mid \|x\|_{\infty} \leq 1 \} = \sum_{i=1}^{n} |z_{i}| = \|z\|_1,$

and the dual of the $\ell_{1}$ -norm is the $\ell_{\infty}$ -norm.

More generally, the dual of the $\ell_p$ -norm is the $\ell_q$ -norm, where $q$ satisfies

$\frac{1}{p} + \frac{1}{q} = 1,$ i.e., $q = \frac{p}{p-1}.$

Exercise

Use Hölder's inequality to prove that $x \cdot y \leq \|x\|_p \|y\|_q.$

Illustration

The dual of the $\ell_{\infty}$ -norm is the $\ell_{1}$ -norm:

$\mathcal{B}_{8}$ and $\mathcal{B}_{8^{*}}$ :

Exercise

Give the formula for the dual norm.
Give an example of a norm which is its own dual.
Consider the norm .
1. Sketch the unit ball $\mathcal{B}$ in the norm. Indicate the vertices.
2. Find the dual of the norm.
3. Sketch the unit ball in the dual norm, and indicate the vertices.

Unit ball $\mathcal{B}$

Dual norm unit ball

References

S. Boyd, L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004. [1]

This page converted to pdf file: Media:norms.pdf, Media:norms.tex

Norms and dual norms - Adam Oberman Math

Norms and dual norms

Contents

Norms

Definition

Unit ball

Exercise

Examples

Illustration

Exercise

Dual norms

Definition

Inequality

Property

Exercise

Exercise

Illustration

Exercise

References