Absolute Distance of Functions

We consider the following

  1. Question. Is there a homeomorphism \(\varphi \colon X \rightarrow Y\) such that \[ \xymatrix{ X \ar@/^/[rr]^{\varphi} \ar[dr]_{f} & & Y \ar[dl]^{g} \\ & {\mathbb{R}}} \] commutes?

  • Example. We view a grayscale image as a function defined on a rectangle describing the luminance of each point. The following image shows the logo of the university of Bonn in grayscale.

     

    And this image shows a warped version of the logo.

     

    If interpret the two images as functions on a rectangular shape, we can get the second image from the first by precomposition with a homeomorphism \(\varphi\) describing the warp we used. Roughly, for two images, the answer to the above question is yes, if we can obtain one image from the other through a warp.

As we obtain an image from sampling the luminance with a sensor at each pixel, the previous example corresponds to the first setup above. Let \(S \subset X\) and \(S' \subset Y\) be subspaces of metric spaces \(X\) respectively \(Y\) and let \(f\) respectively \(g\) describe the distance to \(S\) respectively \(S'\) as in the second setup above. Now suppose \(\varphi \colon X \rightarrow Y\) is an isometry with \(\varphi(S) = S'\), then the above diagram commutes. In some sense this means, that if \(S\) and \(S'\) describe the same shape, then the answer to the above questions is yes.

The above question is very narrow as we ask for equality. In most situations occurring in nature the answer is very likely to be no. But we may still try to quantify how distant an affirmative answer is. To this end we start with specifying an \(\varepsilon \geq 0\) and asking the following

  1. Question. Is there a homeomorphism \(\varphi \colon X \rightarrow Y\) such that for all \(p \in X\) the estimates \(-\varepsilon \leq f(p) - g(\varphi(p)) \leq \varepsilon\) hold?

Next we may ask, how large \(\varepsilon\) needs to be in order for the answer to be yes. This is the motivation behind the following

  • Definition. Let \(M(f, g)\) be the infimum of all \(\varepsilon \geq 0\) such that the answer to the previous question is affirmative. We name this the absolute distance of \(f\) and \(g\).

  • Remark. Though we won’t need it we have the following equation for \(M\). Let \(\mathcal{H}\) be the set of homeomorphisms from \(X\) to \(Y\), then \[M(f, g) = \inf_{\varphi \in \mathcal{H}} {\lVert f - g \circ \varphi \rVert}_{\infty} .\]

Next we observe that \(M\) satisfies the triangle inequality.

  • Lemma (Triangle Inequality). Let \(h \colon Z \rightarrow {\mathbb{R}}\) be another continuous function, then \(M(f, h) \leq M(f, g) + M(g, h)\).

Now we recall that we started with two continuous functions \(f\) and \(g\) and each might describe the luminance of an image or the distance to a certain shape and this is all good, but we should not forget that in practice we may never learn \(f\) or \(g\) and we have to cope with their approximations \(f'\) respectively \(g'\). In topological data analysis the keyword here is stability ever since Cohen-Steiner, Edelsbrunner, and Harer (2005).

  1. Lemma (Stability). Suppose we have \({\lVert f - f' \rVert}_{\infty} = \varepsilon\), then \(M(f, f') \leq \varepsilon\).

  • Proof. Setting \(\varphi = {\operatorname{id}}_X\) we get an affirmative answer to question 2.

The previous two lemmata have the following

  • Corollary. Suppose we have \({\lVert f - f' \rVert}_{\infty} \leq \varepsilon \geq {\lVert g - g' \rVert}_{\infty}\),
    then \(|M(f', g') - M(f, g)| \leq 2 \varepsilon\).

In summary \(M\) defines an extended pseudometric on the class of continuous functions and the above corollary shows that by approximating the functions \(f\) and \(g\), we can also approximate their absolute distance.