Norms

Definition

A norm is a function mapping vectors to non-negative values, measuring the “size” or distance from the origin. A function $f$ is a norm if it satisfies:

• $f(\mathbf{x})=0\Rightarrow \mathbf{x}=0$
• $f(\mathbf{x}+\mathbf{y})\le f(\mathbf{x})+f(\mathbf{y})$ (triangle inequality)
• $\forall \alpha \in \mathbb{R},f(\alpha \mathbf{x})=|\alpha |f(\mathbf{x})$

Intuition

Different norms measure “size” with different geometries. The $L^2$ norm measures straight-line distance; the $L^1$ norm measures Manhattan (city-block) distance and is robust to outliers; the $L^{\infty }$ norm is controlled by the single largest component. Choosing the right norm shapes the geometry of optimisation — $L^1$ encourages sparsity, $L^2$ encourages smoothness.

Formal Description

The $L^p$ norm is defined as

$$\Vert \mathbf{x}{\Vert }_p={\left(\sum _i|x_i{|}^p\right)}^{1/p}.$$

$L^2$ norm (Euclidean norm). $\Vert \mathbf{x}{\Vert }_2=\Vert \mathbf{x}\Vert$. The squared $L^2$ norm $\Vert \mathbf{x}{\Vert }_2^2$ is often preferred computationally since its derivatives depend only on individual elements.

$L^1$ norm. Grows at the same rate everywhere; useful when distinguishing exact zeros from small nonzero values:

$$\Vert \mathbf{x}{\Vert }_1=\sum _i|x_i|.$$

$L^{\infty }$ norm (max norm). Equals the absolute value of the largest element:

$$\Vert \mathbf{x}{\Vert }_{\infty }=\underset{i}{\max }|x_i|.$$

Frobenius norm (for matrices):

$$\Vert \mathbf{A}{\Vert }_F=\sqrt{\sum _{i,j}{A}_{i,j}^2}.$$

The dot product can be expressed in terms of the $L^2$ norm and the angle $\theta$ between vectors:

$${\mathbf{x}}^{\top }\mathbf{y}=\Vert \mathbf{x}{\Vert }_2\Vert \mathbf{y}{\Vert }_2\cos \theta .$$

The $L^0$ “norm” (count of nonzero entries) is not a true norm, as scaling a vector does not change its nonzero count.

Applications

• $L^2$ regularisation (ridge / weight decay) penalises large weights and yields smooth solutions.
• $L^1$ regularisation (LASSO) induces sparsity and automatic feature selection.
• $L^{\infty }$ norm arises in minimax problems and robustness guarantees.

Trade-offs

$L^2$ is differentiable everywhere and computationally convenient; $L^1$ is non-differentiable at zero, requiring subgradient or proximal methods. $L^p$ norms with $p<1$ promote stronger sparsity but are non-convex, making optimisation much harder.

Links

• Vector Space
• Orthogonal Projections