A metric space is simply a set with some extra structure or properties, it’s a collection of points with some relationships between these points.

The metric space has two components, a set, and a distance metric (hence the name, metric space)

The distance metric must satisfy a few properties:

• The distance from a point to itself must be $0$.
• All distances must be non-negative ($\geq 0$).
• The distance from $x$ to $y$ must be the same as from $y$ to $x$.
• The triangle equality: the distance from $x$ to $y$ and then to $z$ must be greater than or equal to the distance straight from $x$ to $z$.

More formally:

A metric space consists of a set $X$ and a function $f: X \times X \to \mathbb{R}$, together denoted $(X,f)$, such that

$$ \begin{align} f(x,x) = 0, ; &\forall x \in X \ f(x,y) \geq 0, ; &\forall x,y \in X, x \neq y \ f(x,y) = f(y,x), ; &\forall x,y \in X \ f(x,y) + f(y,z) \geq f(x,z), ; &\forall x,y,z \in X \ \end{align} $$

Here are some examples:

• $f(x,y) = (x - y)^2$ where $x,y \in \mathbb{R}$
• $f(x,y) = \lvert x_1 - y_1\rvert + \lvert x_2 - y_2\rvert$ where $(x_1, x_2), (y_1, y_2) \in \mathbb{R} \times \mathbb{R}$

Discrete Metric Space

The discrete metric is defined over all possible sets as:

$$ f(x,y) = \begin{eqnarray} \left{ \begin{aligned} 0 \text{ if } x = y \ 1 \text{ if } x \neq y \ \end{aligned} \right. \end{eqnarray} $$

Subspace

$(Y,f)$ is a subspace of $(X,f)$ if $Y \subset X$ and $f$, when restricted to $Y \times Y$, still determines a metric in $Y$, i.e. $f$ still satisfies all the conditions above.

$L_p$-norm

The euclidean metric is also called the $L_2$-norm and is the most important metric.

Let $X$ be an $n$-space, either $\mathbb{R}^n$or $\mathbb{C}^n$, then the euclidean metric is

$$ f_2(\mathbf{x},\mathbf{y}) = \left( \sum_{i=1}^n \lvert x_i - y_i \rvert^2 \right)^\frac{1}{2} $$

or, more generally, for any $p$ the $L_p$-norm is:

$$ f_p(\mathbf{x},\mathbf{y}) = \left( \sum_{i=1}^n \lvert x_i - y_i \rvert^p \right)^\frac{1}{p} $$

It’s clear that these metrics satisfy the first three metric conditions, but that they satisfy the triangle inequality follows from two other inequalities, the Minkowski and Hölder.

Hölder’s Inequality

Hölder’s inequality states that for $p,q \in (1, \infty]$ with $\frac{1}{p} + \frac{1}{q} = 1$ then for all functions $f$ and $g$:

$$ ||fg||_1 \leq ||f||_p ||g||_q $$

or when $f$ and $g$ are $L_p$-norms:

$$ \sum_i |x_i y_i| \leq \left[ \sum_i |x_i|^p \right]^\frac{1}{p} \left[ \sum_i |y_i|^q \right]^\frac{1}{q} $$

{% collapse Proof%} Consider the inequality

$$ a^\frac{1}{p} b^\frac{1}{q} \leq \dfrac{a}{p} + \dfrac{b}{q}, ; a,b \geq 0 $$

this is obvious for $a = 0 $ or $b = 0$.

Now take the function $f$

$$ f(t) = t^\alpha - \alpha t + \alpha - 1 $$

where $\alpha \in (0,1) \text{ and } t \geq 0$.

Now

$$ f^\prime(t) = \alpha(t^{\alpha - 1} -1) $$

giving

$$ \begin{align} f(1) &= f^\prime(1) = 0 \ f^\prime(t) &\leq 0 ; for : t \in (0,1) \ f^\prime(t) &\geq 0 ; for : t \geq 1 \ \end{align} $$

it follows that

$$ f(t) \leq 0 $$

Now, let $t = \frac{a}{b}$ and $\alpha = \frac{1}{p}$

$$ \begin{align} f\left(\dfrac{a}{b}\right) &= \left(\dfrac{a}{b}\right)^\frac{1}{p} - \dfrac{a}{bp} + \dfrac{1}{p} -1 \ 0 &\geq f\left(\dfrac{a}{b}\right) \ 0 &\geq \left(\dfrac{a}{b}\right)^\frac{1}{p} - \dfrac{a}{bp} + \dfrac{1}{p} -1 \ a^\frac{1}{p} b^{1- \frac{1}{p}} &\leq \dfrac{a}{p} + b\left(1 - \dfrac{1}{p} \right) \ \end{align} $$

as desired.

Now substituting in the numbers $a_j, b_j$

$$ \begin{align} a_j &= \dfrac{|x_j|^p}{\sum_i|x_i|^p} \ b_j &= \dfrac{|y_j|^q}{\sum_i|y_i|^q} \ \end{align} $$

$$ \dfrac{|x_j y_j|}{\left[ \sum_ i|x_i|^p \right]^\frac{1}{p} \left[ \sum_i |y_i|^q \right]^\frac{1}{q}} \leq \dfrac{a_j}{p} + \dfrac{b_j}{q}, ; \forall j $$

When summing these inequalities for all $j$, we can use

$$ \begin{align} \sum_j \left( \dfrac{a_j}{p} + \dfrac{b_j}{q} \right) &= \dfrac{\sum_j a_j}{p} + \dfrac{\sum_j b_j}{q} \ &= \dfrac{1}{p} + \dfrac{1}{q} \ &= 1 \end{align} $$

to obtain the Hölder inequality for $L_p$-norms.

(Proof adapted from {% cite goffman1983first %} )

{% endcollapse %}

Minkowski’s Inequality

Minkowski’s inequality is similar to Hölder’s but for addition rather than multiplications.

For $p \in [1, \infty]$ then

$$ ||f+g||_p \leq ||f||_p + ||g||_p $$

or when $f$ and $g$ are $L_p$-norms:

$$ \left[ \sum_i |x_i + y_i|\right]^\frac{1}{p} \leq \left[ \sum_i |x_i|^p \right]^\frac{1}{p} + \left[ \sum_i |y_i|^p \right]^\frac{1}{p} $$

where $(x_i, y_i) \in \mathbb{C} \times \mathbb{C}$

The triangle equality for $L_p$-norms can be obtained by substituitng $x_i -z_i$ for $x_i$ and $z_i - y_i$ for $y_i$.

$L_\infty$-norm

The $L_\infty$-norm over some $n$-space can be found by taking the limit of the $L_p$-norm as $p$ approaches infinity:.

$$ \begin{align} f_\infty(\mathbf{x},\mathbf{y}) &= \lim_{p \to \infty}\left( \sum_{i=1}^n \lvert x_i - y_i \rvert^p \right)^\frac{1}{p} \ &= \max_{i \in [1, n]} |x_i - y_i| \end{align} $$

$L_p$ Spaces

An $L_p$ space, $p \in [1,\infty)$, is the set of all $\infty$-space points $x = (x_1, x_2, \ldots x_\infty)$ that satisfy

$$ \sum_i |x_i|^p \lt \infty $$

and whose metric is the $L_p$-norm.

Most of this article is taken from {% cite goffman1983first %}