\(\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.