Vector Norms
A Norm of a vector \(\vec{v}\) describes the magnitude or size of a vector. It is usually denoted as \(||\vec{v}||\).
There are a few common norms worth discussing.
Eucledian Norm (L2 Norm)
Let's consider a vector v = [3, 4]
we can calculate the Eucledean norm as,
\[
||\vec{v}|| = \sqrt{3^2 + 4^2} = \sqrt{9 + 16} = \sqrt{25} = 5
\]
The intuition here is that the norm calculates the hypotenouse of a right angle triangle. Or in this case the shortest path to travel from [0, 0]
to [3, 4]
.
We can formalize the process as
\[
||\vec{v}|| = \sqrt{\sum_{i=1}^{n} v_i^2}
\]
where,
\[
\vec{v} = [v_1, v_2, ..., v_n]
\]
Which will allow us to define a function for it. In code, this is quite straight forward with python's math library.
import math
def eucledian_norm(v):
return math.sqrt(sum(x**2 for x in v))
v = [3, 4]
norm = eucledian_norm(v)
print(norm)
# 5.0
Manhattan Norm (L1 Norm)
Let's consider vector v = [3, 4]
we can calculate the Manhattan norm as,
\[
||\vec{v}|| = |3| + |4| = 7
\]
Intuitively, this computes how many lines we have to traverse in the x
direction (3) and y direction (4) in order to get to move from [0, 0]
[3, 4]
. This is often called the Taxi-cab normed distance.
We can formalize the process as
\[
||\vec{v}|| = \sum_{i=1}^{n} |v_i|
\]
where,
\[
\vec{v} = [v_1, v_2, ..., v_n]
\]
def manhattan_norm(v):
return sum(abs(x) for x in v)
v = [3, 4]
norm = manhattan_norm(v)
print(norm)
# 7
Generalized Norm (L-p Norm)
We can generalize the norm for any p >= 1
as
\[
||\vec{v}|| = (\sum_{i=1}^{n} |v_i|^p) ^{\frac{1}{p}}
\]
where,
\[
\vec{v} = [v_1, v_2, ..., v_n]
\]
In code this can be expressed as
def generalized_norm(v, p):
return (sum(abs(x)**p for x in v))**(1/p)
v = [3, 4]
norm = generalized_norm(v, 2)
print(norm)
# 5.0
Max Norm (L-infinity Norm)
The Max norm, also known as the L-infinity norm, of a vector is the largest absolute value among its components.
For a vector v = [3, 4]
, the max norm is:
\[
||\vec{v}||_\infty = \max(|3|, |4|) = 4
\]
We can formalize this as:
\[
||\vec{v}||_ \infty = \max{i} |v_i|
\]
Interestingly, the max norm is the limit of the L-p norm as \(p\) approaches infinity.
\[
||\vec{v}||_ \infty = \lim{p\to\infty} \left(\sum_{i=1}^ {n} |v_i|^ p\right)^ {\frac{1}{p}}
\]
We can't practically calculate the an infinite value, however we can observe the norm for increasing values of p
. As p
gets larger, the term with the largest absolute value dominates the sum, and the result approaches the true max norm.
v = [3, 4, 5, 6, 7, 8]
print(f"p = 1: {generalized_norm(v, 1)}")
print(f"p = 2: {generalized_norm(v, 2)}")
print(f"p = 3: {generalized_norm(v, 3)}")
print(f"p = 5: {generalized_norm(v, 5)}")
print(f"p = 10: {generalized_norm(v, 10)}")
print(f"p = 100: {generalized_norm(v, 100)}")
# p = 1: 33.0
# p = 2: 14.106735979665885
# p = 3: 10.877427123742624
# p = 5: 9.080662727393266
# p = 10: 8.231127530283224
# p = 100: 8.000000127026706
Axioms
1. Positive Definiteness
The norm of a vector is always non-negative. It is equal to zero if and only if the vector itself is the zero vector.
\[
||\vec{v}|| \ge 0 \text{, and } ||\vec{v}|| = 0 \iff \vec{v} = \vec{0}
\]
The intuition here is that a vector can't have a negative length. The only vector with a length of zero is the zero vector, which has no magnitude.
We can test our function against this.
zero_v = [0, 0]
norm = generalized_norm(zero_v, 2)
print(norm)
# 0.0
2. Absolute Homogeneity
If you scale a vector by a scalar value \(\alpha\), it's norm is scaled by the absolute value of that scalar. Intuitively, it means that the hypotenouse of a triangle should scale with its sides.
\[
||\alpha \vec{v}|| = |\alpha| ||\vec{v}||
\]
We can test our function against this. To scale our vector v = [3, 4]
by a scalar, we multiply each element by the scalar value. We then compute the norm of the scaled vector and verify that it equals the original norm multiplied by the absolute value of the scalar.
v = [3, 4]
alpha = 2
v_norm = generalized_norm(v, 2)
print(v_norm)
# 5.0
alpha_v = [alpha * x for x in v]
print(alpha_v)
# [6, 8]
alpha_v_norm = generalized_norm(alpha_v, 2)
print(alpha_v_norm)
# 10.0
assert abs(alpha) * v_norm == alpha_v_norm
# True
3. Triangle Inequality
The triangle inequality states that the norm of the sum of two vectors is less than or equal to the sum of their individual norms.
\[
||\vec{v} + \vec{w}|| \le ||\vec{v}|| + ||\vec{w}||
\]
This can be visualized as the idea that the shortest distance between two points is a straight line.
To add two vectors together, we sum the items at each position. We can then take the norm of the result and compare that to the sum of the norms of each vector
v = [1, 2, 3]
w = [4, 5, 6]
# ||v + w||
v_plus_w = [v[i] + w[i] for i in range(len(v))]
# [5, 7, 9]
norm_v_plus_w = generalized_norm(v_plus_w, 2)
print(norm_v_plus_w)
# 12.449899597988733
# ||v|| + ||w||
norm_v_plus_norm_w = generalized_norm(v, 2) + generalized_norm(w, 2)
print(norm_v_plus_norm_w)
# 12.516621774166063
A fun exercise might be trying these axioms to see if they hold for higher lp
norms.