$\newcommand{\norm}[1]{\left\| #1\right\|}$ A norm is a function (usually indicated by the vertical bars, such as $\norm{\cdot}$) such that for all $w \in \mathbb{R}^n$:

• $$\norm{w} \geq 0$$

• For all $w$ and for all $a \in \mathbb{R}$, $$\norm{aw} =

  a

  \norm{w}$. Note that$

  a

  $denotes the absolute value of$a$$

• $\norm{w} = 0$ if and only if $w = 0$. Note that 0 can be the zero vector of any length.
• For all $u, w$, $\norm{u +w} \leq \norm{u} + \norm{w}$. This is called the triangle inequality.

Norms are used for measuring different notions of length or size.

Example norms

• L2 norm: $\norm{w}_2 = \sqrt{\sum_{i=1}^n{w_i^2}}$ or $\sqrt{\langle w,w\rangle}$,
  (Where $\langle a, b \rangle$ is the dot product of a and b)
• L1 norm: $\norm{w}_1 = \sum_{i=1}^n{\vert w_i \vert}$
• $L_{\infty}$ norm: $\norm{w}_{\infty} = max_i \vert w_i \vert$

Let's say $w = [4, 3, 0]$. Then:

• $$\norm{w}_2 = 5$$
• $$\norm{w}_1 = 7$$
• $$\norm{w}_{\infty} = 4$$

Dual Norm

Let $\norm{w}$ be a generic norm of vector $w$. The dual norm is defined as: \begin{equation} \norm{x}_{*} = max {\langle w,x \rangle : \norm{w} \leq 1 } \end{equation}

From this definition, we get the following result: \begin{equation} \langle w,z \rangle \leq \norm{w}\norm{z}_{*} \end{equation}

We now prove that the dual norm of the L2 norm is the L2 norm, using the Cauchy Schwarz inequality ($\langle w,z \rangle \leq \norm{w}_2\norm{z}_{2}$)

$$\begin{eqnarray} \norm{x}_{*} &=& max \{\langle w,x \rangle : \norm{w}_2 \leq 1 \} \\ &\leq& max \{ \norm{w}_2 \norm{x}_2 : \norm{w}_2 \leq 1 \} \text{ (From Cauchy Schwarz)}\\ &=& \norm{x}_2 \text{ (The maximum is when }\norm{w}_2 = 1) \end{eqnarray}$$

It is useful to know that $\norm{w}_{**} = \norm{w}$ meaning that the dual of the dual norm is the original norm.