Geometry of the matching distance for $2$D filtering functions

Feature extraction and comparison are the main tasks of data analysis. In topological data analysis this translates into the problem of comparing persistence modules, which encode the homological features extracted from geometric objects. In order to be able to compare persistence modules a distance is needed. There is a wide variety of distances in the space of $1$-parameter persistence modules, such as the bottleneck and Wasserstein distances. However, such distances do not directly generalise to the multiparameter setting. Thus, different ones have been proposed over the past years, turning into a substantial catalogue, see for example [4, 5, 10]. One of those is the matching distance, which can be defined in particular for 2-parameter persistence modules. This pseudometric, introduced in [4], is a generalisation of the classical bottleneck distance for $1$-parameter persistence modules and measures the difference between the $2$-dimensional Betti numbers functions (also known as rank invariants) of persistence modules. The definition of matching distance is based on a foliation method, consisting of “slicing” the $2$-parameter persistence module into infinitely many $1$-dimensional components by means of lines of positive slope, that we refer to as filtering lines. The matching distance is then obtained by taking the supremum over all such lines of the bottleneck distances between the resulting persistence diagrams after a suitable normalisation.

According to the definition, in order to compute the matching distance between persistence modules, one should take into account infinitely many bottleneck distance computations. Many efforts have been devoted to make this computation efficient, for example, by identifying a finite number of filtering lines contributing to the actual computation [1, 3, 8] or approximation [6, 2, 9] of the distance. However, what many of these works have in common is that their starting point is a pair of $2$-parameter persistence modules. Our approach is similar in scope, but different in nature. We consider regular filtering functions on a smooth manifold with values in $\mathbb{R}^{2}$. Their sublevel-set filtrations still return $2$-parameter persistence modules, for which we can compute the $2$-dimensional persistent Betti numbers functions and, hence, the matching distance between them. Our approach allows us to observe phenomena and exploit structures that are not visible when directly considering persistence modules. For example, it is possible to exploit the differentiable structure of the filtering functions to identify points in the persistence diagrams associated to each filtering line. This structure made of arcs and half-lines is known as extended Pareto grid [5] (see also [11]). The convenience of such an approach relies on the fact that, by using this approach, the changes in homology that occur when the filtering line changes are easy to follow and control.

In this context of $2$-parameter persistence modules derived from regular filtering functions on smooth manifolds, we show that filtering lines of slope $1$ play a special role in the computation of the matching distance. Our main result shows that the matching distance between the $2$-dimensional persistent Betti numbers functions of two filtering functions is indeed realised either on values corresponding to vertical, horizontal or slope $1$ lines, or on special values associated with the two functions. The authors of [1] recently obtained an analogous result in the discrete setting. They show that the matching distance is realised either on values corresponding to diagonal lines or on what they call switch values. One main difference is that the collection of special values that we encounter, called special set, is strongly related with the differentiable structure of our input. In particular, it relies on the structure of the extended Pareto grid associated with a function and on the Position Theorem, proved in [5], which relates points of a persistence diagram to points in the extended Pareto grid.

In this paper, we aim to prove the following:

Let $M$ be a closed $C^{\infty}$-manifold with a Riemannian metric defined on it. Let $f\colon M\to\mathbb{R}$ be a smooth function. The filtered homology of the sublevel sets of $f$ is known as persistent homology. This information can be encoded as a multiset of points in $\{(x,y)\in\mathbb{R}^{2}\mid x\leq y\}$, known as the persistence diagram of $f$ and denoted by $\mathrm{Dgm}(f)$. The subset $\Delta=\{(x,y)\in\mathbb{R}^{2}\mid x=y\}$ is always considered to be in the persistence diagram of a function and, by convention, we treat it as a unique point with infinite multiplicity. See [7] for more details about $1$-parameter persistent homology for sublevel set filtrations.

Let $f=(f_{1},f_{2})\colon M\to\mathbb{R}^{2}$ and $g=(g_{1},g_{2})\colon M\to\mathbb{R}^{2}$ be smooth functions. Consider the set of pairs $(a,b)$ in $]0,1[\times\mathbb{R}$ with the uniform metric $d_{\infty}((a,b),(a^{\prime},b^{\prime}))=\max\{\lvert a-a^{\prime}\rvert,\lvert b-b^{\prime}\rvert\}$. It parameterises all the lines of $\mathbb{R}^{2}$ with positive slope in the following way: $r_{(a,b)}$ is the line containing points of the form $t(a,1-a)+(b,-b)$ with $t$ in $\mathbb{R}$. Each point $(u(t),v(t))$ of $r_{(a,b)}$ can be associated with the set $M_{t}^{a,b}=M_{(u(t),v(t))}=\allowbreak\left\{x\in M\mid f_{1}(x)\leq u(t)\text{ and }f_{2}(x)\leq v(t)\right\}$. This defines a $1$-dimensional filtration, depending on the line $r_{(a,b)}$, which can be associated with a persistence diagram. Letting $(a,b)$ vary, one obtains a collection of persistence diagrams described by the $2$D persistent Betti numbers function of $f$. As observed in [4], $M_{t}^{(a,b)}$ is also equal to $\left\{x\in M\mid f_{(a,b)}(x)\leq t\right\}$, where $f_{(a,b)}(x)=\max\left\{\frac{f_{1}(x)-b}{a},\frac{f_{2}(x)+b}{1-a}\right\}$ (see Figure 1). However, more commonly, $f_{(a,b)}$ is normalised, without changing the nature of the filtration, and $f^{*}_{(a,b)}=\min\{a,1-a\}f_{(a,b)}$ is instead considered.

Given two functions $f$ and $g$, the matching distance [4] is defined by

Here, $d_{B}\left(\mathrm{Dgm}\left(f^{*}_{(a,b)}\right),\mathrm{Dgm}\left(g^{*}_{(a,b)}\right)\right)$ is the bottleneck distance between the persistence diagrams of $f^{*}_{(a,b)}$ and $g^{*}_{(a,b)}$, i.e.,

where $\text{cost}(\sigma)=\max_{X\in\mathrm{Dgm}\left(f^{*}_{(a,b)}\right)}d\left(X,\sigma(X)\right)$, $\sigma$ runs over all bijections, called matchings, between $\mathrm{Dgm}\left(f^{*}_{(a,b)}\right)$ and $\mathrm{Dgm}\left(g^{*}_{(a,b)}\right)$ and, if $X=(x_{1},x_{2})$ and $Y=(y_{1},y_{2})$, then

where $\kappa=\min\{\max\{|x_{1}-y_{1}|,|x_{2}-y_{2}|\},\max\{\frac{x_{2}-x_{1}}{2},\frac{y_{2}-y_{1}}{2}\}\}$. A matching realising the matching distance, whenever it exists, is called an optimal matching. Note that the matching distance $D_{\text{match}}(f,g)$ can be seen both as a pseudo-metric between the persistent Betti numbers functions of $f$ and $g$, and between the filtering functions $f$ and $g$. For the sake of simplicity, we keep the notation $D_{\text{match}}(f,g)$ for both cases. For more details about this definition and the foliation method we refer to [4].

In this section we recall the relation between a differential construction associated with a smooth function $f\colon M\to\mathbb{R}^{2}$, called the extended Pareto grid, and the points of the persistence diagrams $\mathrm{Dgm}\left(f^{*}_{(a,b)}\right)$. This connection is established in the Position Theorem proved in [5].

Recall that the Jacobi set of $f$ is the collection

The Pareto critical set of $f$ is the subset of $\mathbb{J}(f)$ given by

Assume now that $f$ is not only smooth, but it also satisfies the following properties:

1. (i)

   No point $p$ exists in $M$ at which both $\nabla f_{1}$ and $\nabla f_{2}$ vanish.

2. (ii)

   $\mathbb{J}(f)$ is a $1$-manifold smoothly embedded in $M$ consisting of finitely many components, each one diffeomorphic to a circle.

3. (iii)

   $\mathbb{J}_{P}(f)$ is a $1$-dimensional closed submanifold of M, with boundary in $\mathbb{J}(f)$.

4. (iv)

   If we denote by $\mathbb{J}_{C}(f)$ the subset of $\mathbb{J}(f)$ where $\nabla f_{1}$ and $\nabla f_{2}$ are orthogonal to $\mathbb{J}(f)$, then the connected components of $\mathbb{J}_{P}(f)\setminus\mathbb{J}_{C}(f)$ are finite in number, each one being diffeomorphic to an interval. With respect to any parameterisation of each component, one of $f_{1}$ and $f_{2}$ is strictly increasing and the other is strictly decreasing. Each component can meet critical points for $f_{1}$, $f_{2}$ only at its endpoints.

Denote by $\{p_{1},\dots,p_{h}\}$ and $\{q_{1},\dots,q_{k}\}$, respectively, the critical points of $f_{1}$ and $f_{2}$. Since the function $f$ satisfies (i), then $\{p_{1},\dots,p_{h}\}\cap\{q_{1},\dots,q_{k}\}=\emptyset$. The extended Pareto grid of $f$ is defined as the union

where $v_{i}$ is the vertical half-line $\{(x,y)\in\mathbb{R}^{2}\mid x=f_{1}(p_{i}),y\geq f_{2}(p_{i})\}$ and $h_{j}$ is the horizontal half-line $\{(x,y)\in\mathbb{R}^{2}\mid x\geq f_{1}(q_{j}),y=f_{2}(q_{j})\}$. We refer to these half-lines as improper contours and to the closure of the image of the connected components of $\mathbb{J}_{P}(f)\setminus\mathbb{J}_{C}(f)$ as proper contours of $\Gamma(f)$. Figure 2 shows an example of extended Pareto grid for the projection of a sphere in $\mathbb{R}^{3}$ on the plane $y=0$. The violet horizontal half-lines originate at critical values of $f_{2}$, while the vertical ones originate at critical values of $f_{1}$. The red arcs are the images of those arcs on the sphere in which the gradients $\nabla f_{1}$ and $\nabla f_{2}$ have the same direction but opposite orientation. Observe that, because of property (ii), the number of contours in $\Gamma(f)$ is finite. Moreover, property (iv) ensures that every contour can be parameterised as a curve whose two coordinates are respectively strictly decreasing and strictly increasing. For more details about properties (i)-(iv) we refer the interested reader to [5, 11].

One may observe that the portions of contours delimited by points of intersection between different contours correspond to births and deaths of homology classes. For example, the red union of contours corresponds to the birth of a homology class in degree 0 and the green portions of contour to the birth of a homology class in degree 2. For a richer example we refer the reader to [5, Figure 8].

The Position Theorem (Theorem 2 in [5]) allows us to obtain the coordinates of the points in the persistence diagram of $f^{*}_{(a,b)}$ just by looking at the extended Pareto grid of the function and the filtering line $r_{(a,b)}$. It reads as follows:

In [5] the set of filtering functions considered is the set of normal functions. However, the reader can observe that the proof of this specific theorem is actually independent from this assumption and it is valid also in our current setting.

In this section we show that it is possible to extend each $2$D persistent Betti numbers function from the open set $]0,1[\times\mathbb{R}$, where it is defined, to the closed set $[0,1]\times\mathbb{R}$. Moreover, we prove that the matching distance between $f$ and $g$ can be realised on the compact set $[0,1]\times[-\overline{C},\overline{C}]$, with $\overline{C}=\max\{\lVert f\rVert_{\infty},\lVert g\rVert_{\infty}\}$.

By observing that, if $f=(f_{1},f_{2})$ and $h=(f_{2},f_{1})$, then $f^{*}_{(a,b)}=h^{*}_{(1-a,-b)}$, we obtain an analogous result to Proposition 4.1 for $a,a^{\prime}\geq\frac{1}{2}$.

As a consequence, the function

is locally Lipschitz. This is the content of the following result:

In Theorem 4.3 we showed that the function $f^{*}_{(\cdot,\cdot)}$ is locally Lipschitz. As such, it can be extended to the parameter values $(0,b)$ (resp. $(1,b)$) as the limit $f^{*}_{(0,b)}:=\lim_{(a^{\prime},b^{\prime})\to(0,b)}f^{*}_{(a^{\prime},b^{\prime})}$ (resp., $f^{*}_{(1,b)}:=\lim_{(a^{\prime},b^{\prime})\to(1,b)}f^{*}_{(a^{\prime},b^{\prime})}$), for every $b$ in $\mathbb{R}$. Such a function is continuous, and the stability of persistence diagrams with respect to the uniform norm implies that the limit $\lim_{(a^{\prime},b^{\prime})\to(0,b)}\mathrm{Dgm}\left(f^{*}_{(a^{\prime},b^{\prime})}\right)$ (resp. $\lim_{(a^{\prime},b^{\prime})\to(1,b)}\mathrm{Dgm}\left(f^{*}_{(a^{\prime},b^{\prime})}\right)$) also exists and is equal to $\mathrm{Dgm}\left(f^{*}_{(0,b)}\right)$ (resp. $\mathrm{Dgm}\left(f^{*}_{(1,b)}\right)$). In other words, $f^{*}_{(\cdot,\cdot)}$ can be uniquely extended to $[0,1]\times\mathbb{R}$ and this extension is also a locally Lipschitz function. Therefore, in the rest of this paper, we will be allowed to consider the functions $f^{*}_{(a,b)}$ for any $(a,b)$ in $[0,1]\times\mathbb{R}$. The limit functions $f_{(0,b)}^{*}$ and $f^{*}_{(1,b)}$ can be computed explicitly for any $b$ in $\mathbb{R}$:

Since Theorem 4.3 enables us to extend the functions $f^{*}_{(\cdot,\cdot)}$ and $g^{*}_{(\cdot,\cdot)}$ to $[0,1]\times\mathbb{R}$, the function

can be extended to $[0,1]\times\mathbb{R}$, too. Furthermore, it is continuous because of the stability of persistence diagrams and, hence, it admits a maximum in its compact domain.

Next, we show that it is not restrictive to compute the matching distance for parameters in $[0,1]\times[-\overline{C},\overline{C}]$, where $\overline{C}=\max\{\lVert f\rVert_{\infty},\lVert g\rVert_{\infty}\}$.

The above proof also shows that the continuous function $d_{B}\left(\mathrm{Dgm}\left(f^{*}_{(a,b)}\right),\mathrm{Dgm}\left(g^{*}_{(a,b)}\right)\right)$ is constant on the segments $\{(a,b)\mid 0\leq a\leq\frac{1}{2},b=-\overline{C}\}$ and $\{(a,b)\mid\frac{1}{2}\leq a\leq 1,b=\overline{C}\}$, non-increasing on the segment $\{(a,b)\mid 1\geq a\geq\frac{1}{2},b=-\overline{C}\}$ and non-decreasing on the segment $\{(a,b)\mid 0\leq a\leq\frac{1}{2},b=\overline{C}\}$. Moreover, it is $0$ on $(0,\overline{C})$ and $(1,-\overline{C})$ (see Figure 3). Furthermore, we would like to point out that Proposition 4.4 gives us a new formulation for the definition of the matching distance $D_{\mathrm{match}}$ as follows:

In this section we introduce the special set associated with a pair of functions $(f,g)$. We prove that the matching distance between two functions is realised either on values associated with vertical, horizontal or slope $1$ lines, or on this special set.

Special values are values of $]0,1[\times[-\overline{C},\overline{C}]$ in which the optimal matching may abruptly change because of the presence of more than one pair of points with the same distance between abscissas (for $a\leq\frac{1}{2}$) or same distance between ordinates (for $a\geq\frac{1}{2}$). This discontinuity behaviour gives an obstruction to proving that the matching distance is realised only on vertical, horizontal and slope 1 lines. Indeed, the key for proving Theorem 5.4 is being able to continuously move in the space of parameters and not losing track of the points realising the optimal matching. When encountering a special value this continuity may be missing.

Figure 4 shows two examples of lines associated with special values of $(f,g)$, with $f,g\colon S^{2}\to\mathbb{R}^{2}$, $f(x,y,z)=(x,z)$ and $g(x,y,z)=(2.1x+2,0.6z+1.8)$. The green and light blue lines correspond respectively to the parameter values $(0.6,0)$ and $(0.491,0.451)$. The intersection points $A_{1},A_{2}$ and $B_{1},B_{2}$, between the green line and the extended Pareto grid have equal difference between abscissas, thus $(0.6,0)$ is a special value. On the other hand, the intersection points $C_{1},C_{2}$ and $D_{1},D_{2}$, between the light blue line and the extended Pareto grid have equal difference between ordinates. In particular, $(0.491,0.451)$ approximates a special value up to a $5\times 10^{-7}$ error.