Norms and the geometry of distance

A vector space has no built-in notion of length. A norm adds one. The choice of norm shapes which solutions we prefer in an optimization problem: L2 favors small overall magnitude, L1 favors sparsity, and each choice comes with its own geometry.

The three axioms

A norm on a vector space $V$ is a function $\lVert \cdot \rVert: V \to \mathbb{R}$ satisfying[1]:

1. Positivity: $\lVert v\rVert \ge 0$, with $\lVert v\rVert = 0$ only when $v = 0$.
2. Absolute homogeneity: $\lVert \alpha v\rVert = |\alpha|\,\lVert v\rVert$ for all $\alpha \in \mathbb{R}$.
3. Triangle inequality: $\lVert u + v\rVert \le \lVert u\rVert + \lVert v\rVert$.

Axiom 1 says the only zero-length vector is the origin. Axiom 2 says scaling a vector scales its length proportionally. Axiom 3 is the geometric fact that the direct path is never longer than a detour.

The p-norms

For $v \in \mathbb{R}^n$ and $p \ge 1$, the $\ell^p$ norm is

The three cases that appear constantly in machine learning:

$\ell^2$ (Euclidean norm, $p=2$): $\lVert v\rVert_2 = \sqrt{v_1^2 + \cdots + v_n^2}$. This is the familiar length of an arrow in space. Its unit ball $\{v : \lVert v\rVert_2 \le 1\}$ is the round sphere. Minimizing $\lVert v\rVert_2$ penalizes all coordinates uniformly and typically produces many small, nonzero entries.

$\ell^1$ (Manhattan norm, $p=1$): $\lVert v\rVert_1 = |v_1| + \cdots + |v_n|$. The unit ball is a diamond (hyperoctahedron). Minimizing $\lVert v\rVert_1$ in an optimization problem tends to push most coordinates to exactly zero: the corners of the diamond are where the constraint boundary meets objective-level sets, and corners have many zero coordinates. This is the geometric root of the sparsity effect in LASSO[2].

$\ell^\infty$ (max norm, $p \to \infty$): $\lVert v\rVert_\infty = \max_i |v_i|$. The unit ball is a hypercube. It penalizes the single largest entry.

All $\ell^p$ norms for $p \ge 1$ are genuine norms. The hard part is the triangle inequality (Minkowski's inequality); the proof uses Holder's inequality, which the inner-products lesson derives in the $p=2$ case.

To see what each norm measures, compare two vectors with the same Euclidean length but opposite shapes. A spread-out $v = (1, 1, 1, 1)$ and a spiky $w = (2, 0, 0, 0)$ both have $\lVert \cdot \rVert_2 = 2$, so $\ell^2$ cannot tell them apart. The other two norms can:

• Spread $(1, 1, 1, 1)$: $\lVert v\rVert_1 = 4$, $\lVert v\rVert_\infty = 1$.
• Spiky $(2, 0, 0, 0)$: $\lVert w\rVert_1 = 2$, $\lVert w\rVert_\infty = 2$.

The same $\ell^2 = 2$ splits into $\ell^1 = 4$ for the spread vector and $\ell^1 = 2$ for the spiky one: $\ell^1$ charges every coordinate its full magnitude, so it penalizes mass-spreading and rewards concentrating it on fewer entries, which is why minimizing it drives coordinates to zero. The $\ell^\infty$ values invert the ranking ($1$ vs $2$): it sees only the largest entry, so the spiky vector, with one big coordinate, costs more. Three norms, one $\ell^2$, two different orderings of the same pair.

Equivalence of norms

On a finite-dimensional space all norms are equivalent: for any two norms $\lVert \cdot \rVert_a$ and $\lVert \cdot \rVert_b$, there exist constants $c, C > 0$ such that

For $\mathbb{R}^n$ the explicit constants between $\ell^1$, $\ell^2$, $\ell^\infty$ are:

Equivalence means that convergence and continuity are norm-independent in finite dimensions; the choice of norm matters for optimization (it shapes solutions) but not for analysis (it does not change which sequences converge).

Check it on arrays

import numpy as np

v = np.array([3.0, -4.0, 0.0, 1.0])

l1 = np.linalg.norm(v, ord=1)
l2 = np.linalg.norm(v, ord=2)
linf = np.linalg.norm(v, ord=np.inf)

print(f"L1 = {l1:.4f}")     # 8.0
print(f"L2 = {l2:.4f}")     # 5.0990...
print(f"Linf = {linf:.4f}") # 4.0

# Same L2, opposite shapes: L1 and Linf disagree on which is "bigger"
spread = np.array([1.0, 1.0, 1.0, 1.0])
spiky  = np.array([2.0, 0.0, 0.0, 0.0])
for name, u in [("spread", spread), ("spiky", spiky)]:
    print(f"{name}: L1={np.linalg.norm(u,1):.1f} "
          f"L2={np.linalg.norm(u,2):.1f} Linf={np.linalg.norm(u,np.inf):.1f}")
# spread: L1=4.0 L2=2.0 Linf=1.0 ; spiky: L1=2.0 L2=2.0 Linf=2.0

# Verify the inequalities: linf <= l2 <= l1 <= sqrt(n)*l2
n = len(v)
print(f"linf <= l2: {linf <= l2 + 1e-12}")            # True
print(f"l2 <= l1: {l2 <= l1 + 1e-12}")                # True
print(f"l1 <= sqrt(n)*l2: {l1 <= np.sqrt(n)*l2 + 1e-12}")  # True

# Sparsity intuition: L1-minimizing solution of min ||x||_1 s.t. x in an affine set
# is often sparse. Quick demo with a random underdetermined system:
rng = np.random.default_rng(42)
A = rng.normal(size=(3, 8))   # 3 equations, 8 unknowns -> many solutions
b = rng.normal(size=3)

# L2-minimum norm solution via pseudo-inverse:
x_l2 = np.linalg.lstsq(A, b, rcond=None)[0]
print(f"L2 solution nonzeros: {np.sum(np.abs(x_l2) > 1e-8)}")  # likely 3 (full)

The L2 solution typically uses all available coordinates; a proper L1 solve (requires a QP or LASSO solver not shown here) would produce a sparse vector.

Exercises

Exercise 1. For $v = (3, -4, 12)$, compute $\lVert v\rVert_1$, $\lVert v\rVert_2$, and $\lVert v\rVert_\infty$ by hand, and check that the chain $\lVert v\rVert_\infty \le \lVert v\rVert_2 \le \lVert v\rVert_1$ holds.

Exercise 2. Prove the triangle inequality fails for the "norm" $N(v) = \left(\sum_i |v_i|^{1/2}\right)^2$ (the $p = 1/2$ case), so $\ell^p$ with $p$ below 1 is not a norm. Use $u = (1, 0)$ and $v = (0, 1)$.

Exercise 3 (code). Generate 100000 random vectors in $\mathbb{R}^{10}$ and confirm the equivalence chain $\lVert v\rVert_\infty \le \lVert v\rVert_2 \le \lVert v\rVert_1 \le \sqrt{n}\,\lVert v\rVert_2$ holds for every one of them.

import numpy as np

rng = np.random.default_rng(0)
n = 10
V = rng.normal(size=(100_000, n))

l1 = np.linalg.norm(V, ord=1, axis=1)
l2 = np.linalg.norm(V, ord=2, axis=1)
linf = np.linalg.norm(V, ord=np.inf, axis=1)

tol = 1e-9
assert np.all(linf <= l2 + tol)
assert np.all(l2 <= l1 + tol)
assert np.all(l1 <= np.sqrt(n) * l2 + tol)
print("all", len(V), "vectors satisfy the equivalence chain")

With a norm in hand, the inner-products lesson adds the angle between two vectors.