In this section we define join trees and their interleaving distance due to Morozov, Beketayev, and Weber (2013). We start with an auxiliary
Definition (Epigraph). Let \(f \colon X \rightarrow \overline{{\mathbb{R}}}\) be a continuous map, it’s epigraph is \({\operatorname{epi}}f := {\{(x, y) \in X \times \overline{{\mathbb{R}}} ~|~ y \geq f(x)\}}\).
Further we define
\(\mathcal{E} f \colon {\operatorname{epi}}f \rightarrow \overline{{\mathbb{R}}}, (x, y) \mapsto y\) and
\(\kappa_f \colon X \rightarrow {\operatorname{epi}}f, x \mapsto (x, f(x))\).For \(a \geq 0\) we set \(i^{a}_f \colon {\operatorname{epi}}f \rightarrow {\operatorname{epi}}f, (x, y) \mapsto (x, y + a)\).
The epigraph and the Reeb graphs from the previous section allow for a very brief definition of join trees.
Definition (Join Trees). Let \(f \colon X \rightarrow {\mathbb{R}}\) be a continuous map, it’s join tree is \(\mathcal{R} \mathcal{E} f\).
Example. Let \(f \colon \big[-3, 3 + \frac{1}{4}\big] \rightarrow {\mathbb{R}}, x \mapsto x^3 - 3 x\) and \(g \colon \big[-3, 3 + \frac{1}{4}\big] \rightarrow {\mathbb{R}}, x \mapsto 6x\). The following image shows the graphs of \(f\) and \(g\).
The next image shows the corresponding epigraphs.
And a visualization of their join trees, i.e. the Reeb graphs of their epigraphs, is shown in the image below.
Before we get to interleavings we make some auxiliary definitions.
Definition. We set \(D^{\perp} := {\{(a, b) \in (-\infty, \infty] \times (-\infty, \infty] ~|~ a + b \geq 0\}}\).
Component-wise addition yields the structure of a monoid on \(D^{\perp}\). Next we define two weightings on \(D^{\perp}\).
Definition. We set \(\epsilon' \colon D^{\perp} \rightarrow [0, \infty], (a, b) \mapsto \frac{1}{2} (a + b)\) and \(\epsilon'' \colon D^{\perp} \rightarrow [0, \infty], (a, b) \mapsto \max \{a, b\}\).
We note that \(\epsilon'\) is additive and that \(\epsilon''\) is subadditive. Now we define interleavings of join trees. To this end let \(f \colon X \rightarrow {\mathbb{R}}\) and \(g \colon Y \rightarrow {\mathbb{R}}\) be continuous functions.
Definition (Interleavings of Join Trees). For \((a, b) \in D^{\perp}\) an \((a, b)\)-interleaving of \(\mathcal{R} \mathcal{E} f\) and \(\mathcal{R} \mathcal{E} g\) is a pair of homomorphisms \(\varphi \colon b + \mathcal{R} \mathcal{E} f \rightarrow \mathcal{R} \mathcal{E} g\) and \(\psi \colon a + \mathcal{R} \mathcal{E} g \rightarrow \mathcal{R} \mathcal{E} f\) such that the diagrams \[ \xymatrix{ a + b + \mathcal{R} \mathcal{E} f \ar@/^/[rr]^{(\mathcal{R} \circ i^{a + b})_f} \ar[dr]_{\varphi} & & \mathcal{R} \mathcal{E} f \\ & a + \mathcal{R} \mathcal{E} g \ar[ru]_{\psi} } \] and \[ \xymatrix{ a + b + \mathcal{R} \mathcal{E} g \ar@/^/[rr]^{(\mathcal{R} \circ i^{a + b})_g} \ar[dr]_{\psi} & & \mathcal{R} \mathcal{E} g \\ & b + \mathcal{R} \mathcal{E} f \ar[ru]_{\varphi} } \] commute.
For \(\varepsilon \geq 0\) an \(\varepsilon\)-interleaving of \(\mathcal{R} \mathcal{E} f\) and \(\mathcal{R} \mathcal{E} g\) is an \((\varepsilon, \varepsilon)\)-interleaving.
Example. We consider the join trees from the previous example. We set \(\varphi \colon \pi_{\mathcal{E} f} ({\operatorname{epi}}f) \rightarrow \pi_{\mathcal{E} g} ({\operatorname{epi}}g), \pi_{\mathcal{E} f} ((x, y)) \mapsto \pi_{\mathcal{E} g} ((-3, y + 2))\) and
\(\psi \colon \pi_{\mathcal{E} g} ({\operatorname{epi}}g) \rightarrow \pi_{\mathcal{E} f} ({\operatorname{epi}}f), \pi_{\mathcal{E} g} ((x, y)) \mapsto \pi_{\mathcal{E} f} ((-3, y + 2))\), then \(\varphi\) and \(\psi\) form a \((2, 2)\)-interleaving of \(\mathcal{R} \mathcal{E} f\) and \(\mathcal{R} \mathcal{E} g\).
With interleavings defined we can define the interleaving distances.
Definition (Interleaving Distances of Join Trees). Let \(\mathcal{I}\) be the set of all \(\mathbf{a} \in D^{\perp}\) such that there is an \(\mathbf{a}\)-interleaving of \(\mathcal{R} \mathcal{E} f\) and \(\mathcal{R} \mathcal{E} g\). Then we set \(M_{J} (\mathcal{R} \mathcal{E} f, \mathcal{R} \mathcal{E} g) := \inf \epsilon'' (\mathcal{I})\) and \(\mu_{J} (\mathcal{R} \mathcal{E} f, \mathcal{R} \mathcal{E} g) := \inf \epsilon' (\mathcal{I})\).
We name \(M_{J} (\mathcal{R} \mathcal{E} f, \mathcal{R} \mathcal{E} g)\) the absolute interleaving distance of \(\mathcal{R} \mathcal{E} f\) and \(\mathcal{R} \mathcal{E} g\) and \(\mu_{J} (\mathcal{R} \mathcal{E} f, \mathcal{R} \mathcal{E} g)\) the relative interleaving distance of \(\mathcal{R} \mathcal{E} f\) and \(\mathcal{R} \mathcal{E} g\).
We note that these definitions of an interleaving distance are different from the one by Morozov, Beketayev, and Weber (2013). However the subsequent corollary shows that our absolute interleaving distance is equal to the distance by Morozov, Beketayev, and Weber (2013). The reason we gave a different definition is that now we can phrase the computation of the absolute and the relative interleaving distance each as an optimization problem over the same domain.
Lemma (Monotonicity). For \((a, b) \in D^{\perp}\) let \(\varphi \colon b + \mathcal{R} \mathcal{E} f \rightarrow \mathcal{R} \mathcal{E} g\) and \(\psi \colon a + \mathcal{R} \mathcal{E} g \rightarrow \mathcal{R} \mathcal{E} f\) be an \((a, b)\)-interleaving of \(\mathcal{R} \mathcal{E} f\) and \(\mathcal{R} \mathcal{E} g\). Moreover let \(\varepsilon \geq 0\). Then \((\mathcal{R} \circ i^{\varepsilon})_g \circ \varphi\) and \(\psi\) yield an \((a, b + \varepsilon)\)-interleaving. Completely analogously \(\varphi\) and \((\mathcal{R} \circ i^{\varepsilon})_f \circ \psi\) form an \((a + \varepsilon, b)\)-interleaving.
Proof. We consider the diagram \[ \xymatrix@C=40pt{ a + b + \varepsilon + \mathcal{R} \mathcal{E} f \ar[r]|-{(\mathcal{R} \circ i^{a + b})_f} \ar[dr]_{\varphi} \ar@/^2pc/[rr]^{(\mathcal{R} \circ i^{a + b + \varepsilon})_f} & \varepsilon + \mathcal{R} \mathcal{E} f \ar[r]|-{(\mathcal{R} \circ i^{\varepsilon})_f} & \mathcal{R} \mathcal{E} f \\ & a + \varepsilon + \mathcal{R} \mathcal{E} g \ar[u]_{\psi} \ar[r]_{(\mathcal{R} \circ i^{\varepsilon})_g} & a + \mathcal{R} \mathcal{E} g . \ar[u]_{\psi} } \] Since all the inner triangles and the square commute in the above diagram, the outer triangle commutes as well. The other triangle, for \((\mathcal{R} \circ i^{\varepsilon})_g \circ \varphi\) and \(\psi\) to be an interleaving, also commutes, because we have \((\mathcal{R} \circ i^{\varepsilon})_g \circ (\mathcal{R} \circ i^{a + b})_g = (\mathcal{R} \circ i^{a + b + \varepsilon})_g\).
Corollary. The absolute interleaving distance \(M_{J} (\mathcal{R} \mathcal{E} f, \mathcal{R} \mathcal{E} g)\) is the infimum of all \(\varepsilon \geq 0\) such that there is an \(\varepsilon\)-interleaving of \(\mathcal{R} \mathcal{E} f\) and \(\mathcal{R} \mathcal{E} g\).
Proof. Let \(d\) be the infimum of all \(\varepsilon \geq 0\) such that there is an \(\varepsilon\)-interleaving of \(\mathcal{R} \mathcal{E} f\) and \(\mathcal{R} \mathcal{E} g\). Then the inequality \(d \leq M_{J} (\mathcal{R} \mathcal{E} f, \mathcal{R} \mathcal{E} g)\) is clear. For the other inequality suppose we have an \((a, b)\)-interleaving of \(\mathcal{R} \mathcal{E} f\) and \(\mathcal{R} \mathcal{E} g\). Then the previous lemma implies that we also have an \((\epsilon''(a, b))\)-interleaving of \(\mathcal{R} \mathcal{E} f\) and \(\mathcal{R} \mathcal{E} g\).
Next we underpin the naming conventions from the previous definition by proving a type of triangle inequality for each interleaving distance. To this end let \(h \colon Z \rightarrow {\mathbb{R}}\) be yet another continuous function.
Lemma. Let \((a, b), (c, d) \in D^{\perp}\). Further let \(\varphi \colon b + \mathcal{R} \mathcal{E} f \rightarrow \mathcal{R} \mathcal{E} g\) and \(\psi \colon a + \mathcal{R} \mathcal{E} g \rightarrow \mathcal{R} \mathcal{E} f\) be an \((a, b)\)-interleaving of \(\mathcal{R} \mathcal{E} f\) and \(\mathcal{R} \mathcal{E} g\) and let \(\varphi' \colon d + \mathcal{R} \mathcal{E} g \rightarrow \mathcal{R} \mathcal{E} h\) and \(\psi' \colon c + \mathcal{R} \mathcal{E} h \rightarrow \mathcal{R} \mathcal{E} g\) be a \((c, d)\)-interleaving of \(\mathcal{R} \mathcal{E} g\) and \(\mathcal{R} \mathcal{E} h\). Then \(\varphi' \circ \varphi\) and \(\psi \circ \psi'\) yield an \((a + c, b + d)\)-interleaving of \(\mathcal{R} \mathcal{E} f\) and \(\mathcal{R} \mathcal{E} h\).
Proof. We consider the diagram \[ \xymatrix@C+=40pt{ a + b + c + d + \mathcal{R} \mathcal{E} f \ar[r]|-{(\mathcal{R} \circ i^{a + b})_f} \ar[dr]_{\varphi} \ar@/^2pc/[rr]^{(\mathcal{R} \circ i^{a + b + c + d})_f} & c + d + \mathcal{R} \mathcal{E} f \ar[r]|-{(\mathcal{R} \circ i^{c + d})_f} & \mathcal{R} \mathcal{E} f \\ & a + c + d + \mathcal{R} \mathcal{E} g \ar[u]_{\psi} \ar[r]|-{(\mathcal{R} \circ i^{c + d})_g} \ar[dr]_{\varphi'} & a + \mathcal{R} \mathcal{E} g \ar[u]_{\psi} \\ & & a + c + \mathcal{R} \mathcal{E} h . \ar[u]_{\psi'} } \] The upper triangle commutes since \(i^{a + b + c + d}_f = i^{c + d}_f \circ i^{a + b}_f\) and since \(\mathcal{R}\) is a functor. The other two inner triangles and the square commute by definition and thus the outer triangle commutes as well. The proof that the other triangle, for \(\varphi' \circ \varphi\) and \(\psi \circ \psi'\) to be an interleaving, commutes, is completely analogous.
Corollary (Triangle Inequality). We have \[ M_{J} (\mathcal{R} \mathcal{E} f, \mathcal{R} \mathcal{E} h) \leq M_{J} (\mathcal{R} \mathcal{E} f, \mathcal{R} \mathcal{E} g) + M_{J} (\mathcal{R} \mathcal{E} g, \mathcal{R} \mathcal{E} h) \] and \[ \mu_{J} (\mathcal{R} \mathcal{E} f, \mathcal{R} \mathcal{E} h) \leq \mu_{J} (\mathcal{R} \mathcal{E} f, \mathcal{R} \mathcal{E} g) + \mu_{J} (\mathcal{R} \mathcal{E} g, \mathcal{R} \mathcal{E} h) . \]
Next we show that the interleaving distances provide lower bounds for the corresponding distances of functions as promised.
Proposition. Suppose we have a homeomorphism \(\varphi \colon X \rightarrow Y\), \(\varepsilon \geq 0\), and \(r \in {\mathbb{R}}\) such that \(-\varepsilon \leq r + f(p) - g(\varphi(p)) \leq \varepsilon\) for all \(p \in X\). Let \(\varphi' \colon {\operatorname{epi}}f \rightarrow {\operatorname{epi}}g, (p, u) \mapsto (\varphi(p), u + r + \varepsilon)\) and \(\psi' \colon {\operatorname{epi}}g \rightarrow {\operatorname{epi}}f, (q, v) \mapsto (\varphi^{-1}(q), v - r + \varepsilon)\). Then \(\mathcal{R} \varphi'\) and \(\mathcal{R} \psi'\) are an \((-r + \varepsilon, r + \varepsilon)\)-interleaving of \(\mathcal{R} \mathcal{E} f\) and \(\mathcal{R} \mathcal{E} g\).
Corollary. We have \(M_{J} (\mathcal{R} \mathcal{E} f, \mathcal{R} \mathcal{E} g) \leq M (f, g)\) and \(\mu_{J} (\mathcal{R} \mathcal{E} f, \mathcal{R} \mathcal{E} g) \leq \mu (f, g)\).
This corollary concludes our treatment of join trees by themselves. The next step concerning join trees would be to describe practical algorithms to compute them and to compute each of their interleaving distances, but this is outside the scope of this document. Next we consider other more elaborate approaches to finding lower bounds to the absolute and relative distance of functions. Nevertheless the main stream of arguments will always be very similar to the one in this section. We will just use more auxiliary results from domains other than topological data analysis. After we covered Reeb graphs we will even describe a more general framework that encompasses both join trees and Reeb graphs, so we could actually abandon the results from this section. At the expense of some repetition we chose not to do this because this section contains everything that follows in a nutshell.