Norms

Why we need “length” beyond pictures

In 2D or 3D, “length” feels obvious: draw an arrow from the origin to a point and measure how long it is. But in computer science and machine learning you constantly work in higher-dimensional spaces:

• •a document as a vector of word counts (10,000+ dimensions)
• •an image as a vector of pixel intensities
• •a user profile as a vector of features

In those settings, you still need a rigorous way to answer:

• •How big is a vector v?
• •How far is x from y?
• •Which point is “closest” to a centroid?

A norm is the mathematical object that turns these questions into consistent computations.

Definition (with intuition)

A norm is a function that maps a vector to a nonnegative real number:

‖·‖ : ℝⁿ → ℝ

It must satisfy three properties for all vectors u, v and all scalars α:

1) Positive-definiteness

• •‖v‖ ≥ 0
• •‖v‖ = 0 ⇔ v = 0

Intuition: length can’t be negative; the only vector with zero length is the zero vector.

2) Absolute homogeneity

‖αv‖ = |α| ‖v‖

Intuition: scaling an arrow by 3 makes it 3× longer; scaling by −3 flips direction but length is still 3×.

3) Triangle inequality

‖u + v‖ ≤ ‖u‖ + ‖v‖

Intuition: taking two steps (first u, then v) can’t be shorter than the straight-line shortcut by more than the total step lengths.

Norms vs dot products (and why you need both)

You said you already know the dot product. Great—because in ℝⁿ the Euclidean norm is closely tied to it:

‖v‖₂ = √(v · v)

But norms are more general than dot products: you can have norms that don’t come from dot products (like ‖·‖₁ and ‖·‖∞). That flexibility is useful: different norms encode different ideas of what it means to be “close,” “large,” or “small.”

From norms to distances

A norm automatically defines a distance (a metric) between two vectors:

d(x, y) = ‖x − y‖

So if you choose a norm, you also choose a geometry for your space.

Common p-norms (preview)

The most used family is the p-norms:

‖v‖ₚ = (∑ᵢ |vᵢ|ᵖ)¹ᐟᵖ, for p ≥ 1

Special cases you’ll use constantly:

• •p = 1 → ‖v‖₁ = ∑ᵢ |vᵢ|
• •p = 2 → ‖v‖₂ = √(∑ᵢ vᵢ²)
• •p → ∞ → ‖v‖∞ = maxᵢ |vᵢ|

Each is a valid norm, satisfies the three properties, and leads to a different notion of “ball” and “nearest.”

Why these three show up everywhere

When you implement algorithms, you want norms that are:

• •easy to compute
• •meaningful in applications
• •stable in high dimensions

‖·‖₁, ‖·‖₂, and ‖·‖∞ are the standard trio because they emphasize different aspects of a vector:

• •‖v‖₁: total magnitude across coordinates (robust, encourages sparsity)
• •‖v‖₂: geometric length (rotation-invariant, tied to dot product)
• •‖v‖∞: worst-case coordinate (useful for constraints and error bounds)

Formulas (and what they “measure”)

Let v = (v₁, v₂, …, vₙ).

L1 norm

‖v‖₁ = ∑ᵢ |vᵢ|

Interpretation: add up the absolute contributions of every coordinate.

L2 (Euclidean) norm

‖v‖₂ = √(∑ᵢ vᵢ²) = √(v · v)

Interpretation: the usual straight-line length.

L∞ norm

‖v‖∞ = maxᵢ |vᵢ|

Interpretation: how large the largest-magnitude coordinate is.

A quick comparison table

Unit balls: same rule, different geometry

A great way to feel norms is to look at their unit balls in 2D: the set of vectors whose norm ≤ 1.

• •‖v‖₂ ≤ 1: a circle
• •‖v‖₁ ≤ 1: a diamond (rotated square)
• •‖v‖∞ ≤ 1: an axis-aligned square

This matters because “closest point” problems (like clustering) depend on the shape of these balls.

Scaling behavior (absolute homogeneity in action)

If α is a scalar and v is a vector, all norms must satisfy:

‖αv‖ = |α| ‖v‖

For p-norms, you can see it directly:

‖αv‖ₚ

= (∑ᵢ |α vᵢ|ᵖ)¹ᐟᵖ

= (∑ᵢ (|α| |vᵢ|)ᵖ)¹ᐟᵖ

= (∑ᵢ |α|ᵖ |vᵢ|ᵖ)¹ᐟᵖ

= (|α|ᵖ ∑ᵢ |vᵢ|ᵖ)¹ᐟᵖ

= |α| (∑ᵢ |vᵢ|ᵖ)¹ᐟᵖ

= |α| ‖v‖ₚ

So p-norms automatically obey one of the key norm axioms.

Why axioms matter (not just definitions)

When you rely on a norm inside an algorithm, you’re often using its properties implicitly:

• •proving a distance is valid
• •bounding an error
• •showing an optimization problem behaves nicely

The three norm axioms are the “license” that lets you do these steps safely.

1) Positive-definiteness: “length is never negative”

For p-norms (p ≥ 1), every term |vᵢ|ᵖ is ≥ 0, so the sum is ≥ 0, so the p-th root is ≥ 0.

Also, ‖v‖ₚ = 0 implies:

(∑ᵢ |vᵢ|ᵖ)¹ᐟᵖ = 0

⇒ ∑ᵢ |vᵢ|ᵖ = 0

A sum of nonnegative numbers is 0 only if each term is 0:

∀i, |vᵢ|ᵖ = 0 ⇒ |vᵢ| = 0 ⇒ vᵢ = 0

So v = 0.

2) Absolute homogeneity: “scaling scales length”

You already saw the derivation in the previous section. This property is what makes norms behave like a geometric length. It also prevents weird measures like “length(2v) = length(v) + 7.”

3) Triangle inequality: the most powerful rule

Triangle inequality is often the hardest to prove, but the easiest to use.

It says:

‖u + v‖ ≤ ‖u‖ + ‖v‖

A very common corollary is a bound on differences (sometimes called a reverse triangle inequality variant):

|‖u‖ − ‖v‖| ≤ ‖u − v‖

This tells you: if two vectors are close, their lengths are close.

Here’s the derivation using triangle inequality twice.

Start with:

u = (u − v) + v

Apply triangle inequality:

‖u‖ = ‖(u − v) + v‖ ≤ ‖u − v‖ + ‖v‖

Rearrange:

‖u‖ − ‖v‖ ≤ ‖u − v‖ (1)

Swap u and v:

‖v‖ − ‖u‖ ≤ ‖v − u‖ = ‖u − v‖ (2)

Combine (1) and (2):

|‖u‖ − ‖v‖| ≤ ‖u − v‖

This inequality is a frequent tool when analyzing iterative algorithms.

Norm equivalence intuition (why different norms still relate)

In finite-dimensional spaces like ℝⁿ, all norms are “equivalent” in the sense that they bound each other up to constants. Practically: if one norm is small, the others can’t be arbitrarily huge.

For the three norms we care about, these inequalities are especially useful:

1) ‖v‖∞ ≤ ‖v‖₂ ≤ ‖v‖₁

Reasoning (intuition):

• •the max component can’t exceed the root-sum-squares
• •root-sum-squares can’t exceed the sum of magnitudes

2) And with dimension n, you can also bound the other direction:

‖v‖₁ ≤ √n ‖v‖₂

‖v‖₂ ≤ √n ‖v‖∞

These tell you a key high-dimensional fact: the gap between norms can grow with √n. So in large n, your choice of norm can meaningfully change distances and nearest neighbors.

A note about p < 1

You might see “‖v‖ₚ” written for p < 1 in some ML contexts (e.g., sparsity). But for p < 1, triangle inequality fails, so it’s not a true norm. People still use it as a penalty, but you lose some guarantees.

Why clustering cares about norms

Clustering groups points by proximity. But “proximity” is defined by a distance, and a distance is often built from a norm:

• •L2 distance: d₂(x, y) = ‖x − y‖₂
• •L1 distance: d₁(x, y) = ‖x − y‖₁
• •L∞ distance: d∞(x, y) = ‖x − y‖∞

Change the norm → change the geometry → change which points are nearest → change the clustering.

K-means and why it “likes” L2

Classic k-means is typically presented with squared Euclidean distance:

minimize ∑ (over points x) ‖x − μ(cluster(x))‖₂²

Why L2²? Because it pairs perfectly with means.

If you take a single cluster and want the best center c to minimize:

J(c) = ∑ᵢ ‖xᵢ − c‖₂²

the minimizer is the componentwise mean. That makes the update step simple and fast.

(If you instead used L1 distance, the best “center” is a median per coordinate, leading to k-medians. So the norm choice changes the algorithm’s natural center.)

L1 distance: robustness and “city block” geometry

With L1, distances add coordinate-wise. This can be more robust to outliers in some settings and can better match data where moving along axes is natural (think grid/city streets).

Geometrically, L1 balls are diamonds in 2D. That tends to create cluster boundaries aligned differently than L2.

L∞ distance: worst-case deviation

L∞ treats the distance between x and y as the largest coordinate difference:

‖x − y‖∞ = maxᵢ |xᵢ − yᵢ|

This is useful when you care about maximum error in any feature (e.g., tolerances). In clustering, it makes points “close” if they’re close in every coordinate (no big deviation allowed).

Practical guidance: choosing a norm

Norms, scaling, and feature normalization

Norm-based distances are sensitive to units. If one coordinate is measured in dollars and another in millimeters, the large-scale coordinate can dominate any norm.

A common fix is to normalize features (e.g., z-score standardization). This is not a norm concept by itself, but norms make the need obvious: the distance ‖x − y‖ depends on coordinate scales.

Connecting back to dot product

Because ‖v‖₂ = √(v · v), anything that uses dot products often implicitly uses L2 norms. Examples:

• •cosine similarity uses x · y / (‖x‖₂ ‖y‖₂)
• •projections and orthogonality rely on L2 geometry

So norms complete the story: dot products measure alignment; norms measure magnitude; together they describe angle and distance.