Norms

Measures of vector and matrix size — L1, L2, and Frobenius norms — and their role in regularization and distance.

Diagram · Unit Balls

ℓ₁ unit ball: diamond — corners on axes. ℓ₂ unit ball: circle. ℓ∞ unit ball: square. The shape of the unit ball determines what "small" means under each norm.

Definition

A norm is a function that assigns a non-negative "length" or "size" to a vector. The most common is the Euclidean norm ( $\ell_2$ norm):

$\|\mathbf{x}\|_2 = \sqrt{x_1^2 + x_2^2 + \cdots + x_n^2}$

More generally, the $\ell_p$ norm for $p \geq 1$ :

$\|\mathbf{x}\|_p = \left(\sum_i |x_i|^p\right)^{1/p}$

Common cases:

$p=1$ : $\|\mathbf{x}\|_1 = \sum_i |x_i|$ (Manhattan / taxicab norm)
$p=2$ : $\|\mathbf{x}\|_2 = \sqrt{\sum_i x_i^2}$ (Euclidean norm)
$p=\infty$ : $\|\mathbf{x}\|_\infty = \max_i |x_i|$ (Chebyshev norm)

A norm must satisfy: (1) $\|\mathbf{x}\| \geq 0$ , with $\|\mathbf{x}\|=0 \Leftrightarrow \mathbf{x}=\mathbf{0}$ ; (2) $\|c\mathbf{x}\| = |c|\|\mathbf{x}\|$ ; (3) triangle inequality $\|\mathbf{x}+\mathbf{y}\| \leq \|\mathbf{x}\| + \|\mathbf{y}\|$ .

Key properties

Positive definiteness: $\|\mathbf{x}\| \geq 0$ , and $\|\mathbf{x}\|=0$ only for $\mathbf{x}=\mathbf{0}$
Absolute homogeneity: $\|c\mathbf{x}\| = |c|\,\|\mathbf{x}\|$ for any scalar $c$
Triangle inequality: $\|\mathbf{x}+\mathbf{y}\| \leq \|\mathbf{x}\|+\|\mathbf{y}\|$ — never longer than the sum of the parts
All $\ell_p$ norms agree on a single nonzero coordinate vector, but differ in how they combine multiple nonzero entries

Common mistakes

Treating all norms as interchangeable: while finite-dimensional norms are equivalent (within constant factors of each other), they behave very differently for optimization — Lasso ( $\ell_1$ ) and Ridge ( $\ell_2$ ) regularization give qualitatively different solutions for exactly this reason
Forgetting $p \geq 1$ is required: for $0 < p < 1$ , the formula $\left(\sum|x_i|^p\right)^{1/p}$ violates the triangle inequality and isn't a true norm

Computing norms for x = (3, -4)

$\|\mathbf{x}\|_1 = |3| + |-4| = 7$
$\|\mathbf{x}\|_2 = \sqrt{9+16} = 5$
$\|\mathbf{x}\|_\infty = \max(3,4) = 4$

The $\ell_2$ norm gives the straight-line distance; the $\ell_1$ norm gives the distance if you can only walk along grid lines.

Try it

The unit ball under a norm is the set of vectors $\{\mathbf{x}: \|\mathbf{x}\| \leq 1\}$ . Describe the shape of the unit ball for the $\ell_1$ , $\ell_2$ , and $\ell_\infty$ norms in $\mathbb{R}^2$ .

Solution

$\ell_1$ unit ball: $|x_1|+|x_2| \leq 1$ — a diamond (rotated square) with vertices at $(\pm1,0)$ and $(0,\pm1)$ .
$\ell_2$ unit ball: $x_1^2+x_2^2 \leq 1$ — a disk (circle of radius 1).
$\ell_\infty$ unit ball: $\max(|x_1|,|x_2|) \leq 1$ — a square with vertices at $(\pm1,\pm1)$ .

As $p$ increases from 1 to $\infty$ , the unit ball interpolates from diamond → circle → square.

Related concepts

Needs first

Dot Product

Orthogonality Regularization

Uses this

DBSCAN Hierarchical Clustering K-Means Clustering K-Nearest Neighbors Support Vector Machines

View in full concept graph →