Introduction to Metric Space

---

# 🎬 Introduction to Metric Space

Wai-Shing Luk

2018-09-12 📅

---

Distance Space
--------------

A distance space is an ordered pair $(M,d)$ where $M$ is a non-empty set
and $d$ is a distance on $M$ such that:

-   $d(v, w) \ge 0$ (non-negativity)
-   $d(v, w) = 0$ iff $v = w$ (identity of indiscernibles)
-   $d(v, w) = d(w, v)$ (symmetry)

In addition, requires $v \in M$ be comparable.

---

📚 Examples
--------

-   "Hamming":
  $$d(\alpha, \beta) =
  \begin{cases}
    0 & \mathrm{if}\ \alpha = \beta, \\
    1 & \mathrm{otherwise}.
  \end{cases} $$
    no additional requirement, (not interesting enough?)

-   Affine
    $$d(\alpha, \beta) = | \alpha - \beta|$$

---

C++ code
--------

```cpp
template <typename M>
size_t hamming(M a, M b) { return a == b ? 0 : 1; }

template <typename M>
double affine(M a, M b) { return abs(a - b); }
```

---

Metric Space
------------

A metric space is an ordered pair $(M,d)$ where $M$ is a non-empty set
and $d$ is a metric on $M$ such that:

-   $d(v, w) \ge 0$ (non-negativity)
-   $d(v, w) = 0$ iff $v = w$ (identity of indiscemibles)
-   $d(v, w) = d(v, w)$ (symmetry)
-   $d(u, v) + d(v, w) \ge d(u, w)$ (triangle inequality)

A metric is called *additive* if $d(u, v) + d(v, w) = d(u, w)$.

---

Metric Space in C++ Concepts
----------------------------

```cpp
  template <class M, class F = typename M::value_type>
  constexpr bool Metric_Space()
  {
    return Distance_Space<M,F>();
  }

template <class M, class F = typename M::value_type>
    requires Metric_Space<M,F>()
  void Metric_Space_test(M v, M w, M u)
  {
    assert( Distance_Space_test(v,w) );
    assert( dist(u,v) + dist(v,w) >= dist(u,w) );
  }
```

---

Extensions to ordered sequences ($m=n$)
---------------------------------------

-   Given $x = (x_1, x_2, \cdots, x_m)$ and
    $y = (y_1, y_2, \cdots, y_n)$ and a metric $d(x_i, y_i)$ for
    each elements.
-   Sequence representing: a vector, a polynomial, a string, a binary
    tree ...
-   First assume same length (i.e. $m=n$)
-   "Dot product" of each elements:
    -   $d(x,y) = \sum_{i=1}^n d(x_i, y_i)$
    -   $d(x,y) = \sum_{i=1}^n w_i \cdot d(x_i, y_i)$
    -   $d(x,y) = (\sum_{i=1}^n d(x_i, y_i)^{p})^{1/p}$
    -   $d(x,y) = (1/|b - a| )\int_{a}^b d(x(t), y(t)) d t$
-   Angle distance

---

📚 Examples
--------

-   Hamming metric, Euclidean metric ($p=2$), rectilinear metric ($p=1$)
-   Metric of random variable
    $d(x,y) = \sum_{i=1}^n p_i \cdot d(x_i, y_i)$

```cpp
template <class M, class Dist>
double dist(M v, M w, Dist d) {
   return  std::inner_product(std::begin(v), std::end(v),
   std::begin(w), 0, std::plus<int>(), d);
}
```

---

Extensions to ordered sequences ($n \neq m$)
--------------------------------------------

-   Assume $m \ge n$
-   Prefix distance: $d(x, y) = \sum_{i=1}^n d(x_i, y_i) + (m - n)$
-   Editing distance (Levenshtein metric): the minimum number of
    operations needed to transform one string into the other, where an
    operation is an insertion, deletion, or substitution.
-   For example, the distance between "kitten" and "sitting" is 3:
    -   **k**itten => **s**itten (substitution of 's' for 'k')
    -   sitt**e**n => sitt**i**n (substitution of 'i' for 'e')
    -   sittin => sittin**g** (insert 'g' at the end)

---

Extensions to unordered sequences
---------------------------------

-   Hausdorff distance
    -   $d(x,y) = \max\{d_H(x, y), d_H(y, x)\}$,
    -   $d_H(x,y) = \sup_i d_H(x_i, y)$,
    -   $d_H(x_i, y) = \inf_j d(x_i, y_j)$

---

# Q&A 🎤