Metrics
an Introduction |
Prof. David Bernstein
|
Computer Science Department |
bernstdh@jmu.edu |
A vector space (also called a linear space) \(P\) over \(\mathbb{R}\) is a non-empty set with the following operations:
Addition: \(\bs{p} + \bs{q} \in P \text{ for each } \bs{p},\bs{q} \in P\)
Multiplication by a Scalar: \(\lambda \bs{p} \in P \text{ for each } \bs{p} \in P, \lambda \in \mathbb{R}\)
which satisfy the following properties:
The elements of \(P\) are called vectors.
Given a non-empty set of points, \(P\), a metric is a function, \(d\) that assigns a real number to each pair of points (i.e., \(d:P \times P \rightarrow \mathbb{R}\)), satisfying the following properties:
Given a vector space \(P\) over \(\mathbb{R}\), a norm for \(P\) is a function on \(P\) which assigns to each element a real number (i.e., \(||\cdot||:P \rightarrow \mathbb{R}\)) satisfying the following properties:
Given a vector space, \(P\), and norm, \(||\cdot||\), the function \(d:P \times P \rightarrow \mathbb{R}\) defined by:
is a metric for \(P\) and is called the metric generated by the norm.
The absolute value function, \(|\cdot|\) is a norm for the set of real numbers, \(\mathbb{R}\).
This norm generates the "usual" metric for \(\mathbb{R}\):
The Euclidean norm is defined on the set of ordered pairs in \(\mathbb{R}^2\) as:
This definition can be extended to the set of ordered \(n\)-tuples in \(\mathbb{R}^n\) as:
For any \(\bs{p},\bs{q} \in \mathbb{R}^n\)
Proof. For any positive real numbers, \(a,b\), \((a-b)^2 = a^2 - 2ab + b^2 \geq 0\). Hence, \(2ab \leq a^2 + b^2\). Therefore, given non-zero \(\bs{p}\) and \(\bs{q}\), for each \(k\) setting:
\(a = \frac{|p_k|}{\sqrt{\sum_{k=1}^{n}|p_k|^2}}\)
\(b = \frac{|q_k|}{\sqrt{\sum_{k=1}^{n}|q_k|^2}}\)
and summing the resulting inequalities leads to:
\( \frac{\sum_{k=1}^{n}|p_k q_k|} {\sqrt{\sum_{k=1}^{n}|p_k|^2}\sqrt{\sum_{k=1}^{n}|q_k|^2}} \leq 1 \)
The first three properties of a norm are trivial to demonstrate. The triangle inequality can be demonstrated as follows.
\(||\bs{p}+\bs{q}||_2^2 = \left( \sum_{k=1}^{n} |p_k + q_k|^2 \right)\)
\(\leq \sum_{k=1}^{n} |p_k|^2 + 2 \sum_{k=1}^{n} |p_k q_k| + \sum_{k=1}^{n} |q_k|^2\)
So, by the Cauchy-Schwartz inequality:
\(\leq \sum_{k=1}^{n} |p_k|^2 + 2 \sum_{k=1}^{n} |p_k|^2 \sum_{k=1}^{n} |q_k|^2 \sum_{k=1}^{n} |q_k|^2\)
which equals \(\left(||\bs{p}||_2 + ||\bs{q}||)2 \right)^2\).
For Different Norms
Distance Between Two Points