Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Geometry of the matching distance for 2D filtering functions

Geometry of the matching distance for 2D filtering functions In this paper we exploit the concept of extended Pareto grid to study the geometric properties of the matching distance for R -valued regular functions defined on a closed Riemannian manifold. In particular, we prove that in this case the matching distance is realised either at special values or at values corresponding to vertical, horizontal or slope 1 lines. Keywords Matching distance · Multiparameter persistence · Extended Pareto grid · Filtering functions Mathematics Subject Classification Primary 55N31; Secondary 57R19 1 Introduction Feature extraction and comparison are the main tasks of data analysis. In topologi- cal data analysis this translates into the problem of comparing persistence modules, which encode the homological features extracted from geometric objects. In order to Francesca Tombari tombari@kth.se Marc Ethier marcdethier@gmail.com Patrizio Frosini patrizio.frosini@unibo.it Nicola Quercioli nicola.quercioli@enea.it Université du Québec en Abitibi-Témiscamingue, Rouyn-Noranda, QC, Canada Mathematics, University of Bologna, 40126 Bologna, Italy ENEA, 40129 Bologna, Italy Mathematics, KTH, 10044 Stockholm, Sweden 123 M. Ethier et al. 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 (Cerri et al. 2013, 2019; Lesnick 2015). One of those is the matching distance, which can be defined in particular for 2- parameter persistence modules. This pseudometric, introduced in Cerri et al. (2013), is a generalisation of the classical bottleneck distance for 1-parameter persistence mod- ules 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 per- sistence 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 (Bapat et al. 2022; Bjerkevik and Kerber 2021; Kerber et al. 2019)or approximation (Cerri and Frosini 2020; Biasotti et al. 2011; Kerber and Nigmetov 2020) 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 simi- lar in scope, but different in nature. We consider regular filtering functions on a smooth manifold with values in R . Their sublevel-set filtrations still return 2-parameter persis- tence 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 con- sidering persistence modules. For example, it is possible to exploit the differentiable structure of the filtering functions to identify points in the persistence diagrams asso- ciated to each filtering line. This structure made of arcs and half-lines is known as extended Pareto grid (Cerri et al. 2019)(seealsoWan 1975). 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 Bapat et al. (2022) 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, 123 Geometry of the matching distance for 2D filtering functions proved in Cerri et al. (2019), which relates points of a persistence diagram to points in the extended Pareto grid. In this paper, we aim to prove the following: Theorem The matching distance between f and g is realised either on a value asso- ciated with a line of slope 1, a vertical or horizontal line, or on a special value of ( f , g). 2 Matching distance Let M beaclosed C -manifold with a Riemannian metric defined on it. Let f : M → 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) ∈ R | x ≤ y}, known as the persistence diagram of f and denoted by Dgm( f ). The subset  ={(x , y) ∈ R | 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 Edelsbrunner and Morozov (2013) for more details about 1-parameter persistent homology for sublevel set filtrations. 2 2 Let f = ( f , f ) : M → R and g = (g , g ) : M → R be smooth 1 2 1 2 functions. Consider the set of pairs (a, b) in ]0, 1[×R with the uniform metric d ((a, b), (a , b )) = max{|a − a |, |b − b |}. It parameterises all the lines of R with positive slope in the following way: r is the line containing points of the form (a,b) t (a, 1−a)+(b, −b) with t in R. Each point (u(t ), v(t )) of r can be associated with (a,b) a,b the set M = M = {x ∈ M | f (x ) ≤ u(t ) and f (x ) ≤ v(t )}. This defines (u(t ),v(t )) 1 2 a 1-dimensional filtration, depending on the line r , which can be associated with (a,b) a persistence diagram. Letting (a, b) vary, one obtains a collection of persistence dia- grams described by the 2D persistent Betti numbers function of f . As observed in (a,b) Cerri et al. (2013), M is also equal to x ∈ M | f (x ) ≤ t , where f (x ) = (a,b) (a,b) f (x )−b f (x )+b 1 2 max , (see Fig. 1). However, more commonly, f is normalised, (a,b) a 1−a without changing the nature of the filtration, and f = min{a, 1−a} f is instead (a,b) (a,b) considered. Given two functions f and g,the matching distance (Cerri et al. 2013) is defined by ∗ ∗ D ( f , g) = sup d Dgm f , Dgm g . match B (a,b) (a,b) (a,b)∈]0,1[×R ∗ ∗ Here, d Dgm f , Dgm g is the bottleneck distance between the (a,b) (a,b) ∗ ∗ persistence diagrams of f and g , i.e., (a,b) (a,b) ∗ ∗ d Dgm f , Dgm g = inf cost(σ ), (a,b) (a,b) 123 M. Ethier et al. Fig. 1 On the left the space of parameters ]0, 1[×R is represented. On the right we show the filtering lines corresponding to the two parameters selected and the projection of a torus on the plane. Each of the lines gives a sublevel set filtration of the torus in the direction of the line. The area down and left of the red point a ,b 1 1 ¯ ¯ (a t + b ,(1 − a )t − b ) on the line r is the sublevel set M associated to such a point (colour 1 1 1 1 (a ,b ) 1 1 ¯ figure online) where cost(σ ) = max d (X,σ (X )), σ runs over all bijections, called X ∈Dgm f (a,b) ∗ ∗ matchings, between Dgm f and Dgm g and, if X = (x , x ) and Y = 1 2 (a,b) (a,b) (y , y ), then 1 2 ⎪ κ if X = (x , x ), Y = (y , y ) ∈  , 1 2 1 2 |x − y | if X = (x , ∞), Y = (y , ∞), ⎪ 1 1 1 1 ⎨ x −x 2 1 + if X = (x , x ) ∈  , Y = , 1 2 d(X , Y ) = y −y 2 1 + if Y = (y , y ) ∈  , X = , 1 2 ⎪0if X = Y = , ∞ otherwise. x −x y −y 2 1 2 1 where κ = min{max{|x − y |, |x − y |}, max{ , }}. A matching realising 1 1 2 2 2 2 the matching distance, whenever it exists, is called an optimal matching. Note that the matching distance D ( f , g) can be seen both as a pseudo-metric between the match 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 ( f , g) for both cases. match For more details about this definition and the foliation method we refer to Cerri et al. (2013). 123 Geometry of the matching distance for 2D filtering functions 3 Extended Pareto grid In this section we recall the relation between a differential construction associated with a smooth function f : M → R , called the extended Pareto grid, and the points of the persistence diagrams Dgm f . This connection is established in the Position (a,b) Theorem proved in Cerri et al. (2019). Recall that the Jacobi set of f is the collection J( f ) ={ p ∈ M |∇ f = λ∇ f or ∇ f = λ∇ f , for some λ ∈ R}. 1 2 2 1 The Pareto critical set of f is the subset of J( f ) given by J ( f ) = { p ∈ J( f ) |∇ f = λ∇ f or ∇ f = λ∇ f , for some λ ≤ 0} . P 1 2 2 1 Assume now that f is not only smooth, but it also satisfies the following properties: (i) No point p exists in M at which both ∇ f and ∇ f vanish. 1 2 (ii) J( f ) is a 1-manifold smoothly embedded in M consisting of finitely many components, each one diffeomorphic to a circle. (iii) J ( f ) is a 1-dimensional closed submanifold of M, with boundary in J( f ). (iv) If we denote by J ( f ) the subset of J( f ) where ∇ f and ∇ f are orthogonal C 1 2 to J( f ), then the connected components of J ( f ) \ J ( f ) are finite in number, P C each one being diffeomorphic to an interval. With respect to any parameterisa- tion of each component, one of f and f is strictly increasing and the other is 1 2 strictly decreasing. Each component can meet critical points for f , f only at 1 2 its endpoints. Denote by { p ,..., p } and {q ,..., q }, respectively, the critical points of f 1 h 1 k 1 and f . Since the function f satisfies (i), then { p ,..., p }∩{q ,..., q }=∅.The 2 1 h 1 k extended Pareto grid of f is defined as the union ⎛ ⎞ ⎝ ⎠ ( f ) = f (J ( f )) ∪ v ∪ h P i j i j where v is the vertical half-line {(x , y) ∈ R | x = f (p ), y ≥ f (p )} and h is the i 1 i 2 i j horizontal half-line {(x , y) ∈ R | x ≥ f (q ), y = f (q )}. We refer to these half- 1 j 2 j lines as improper contours and to the closure of the image of the connected components of J ( f ) \ J ( f ) as proper contours of ( f ). Figure 2shows an example of extended P C Pareto grid for the projection of a sphere in R on the plane y = 0. The violet horizontal half-lines originate at critical values of f , while the vertical ones originate at critical values of f . The red arcs are the images of those arcs on the sphere in which the gradients ∇ f and ∇ f have the same direction but opposite orientation. Observe 1 2 that, because of property (ii), the number of contours in ( 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 123 M. Ethier et al. 2 3 2 2 2 Fig. 2 The extended Pareto grid of the function f (x , y, z) = (x , z) on S ={(x , y, z) ∈ R | x +y +z = 1}.On the left, the red arcs are the proper contours and the violet half-lines are the improper contours. Any point in this extended Pareto grid corresponds to a birth or death of a homological class. For example, on the right side of this figure, the red points correspond to the birth of homology classes in degree 0, while the green points correspond to the birth of homology classes in degree 2 (colour figure online) about properties (i)–(iv) we refer the interested reader to Cerri et al. (2019) and Wan (1975). 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 Cerri et al. (2019, Figure 8). The Position Theorem (Theorem 2 in Cerri et al. 2019) allows us to obtain the coordinates of the points in the persistence diagram of f just by looking at the (a,b) extended Pareto grid of the function and the filtering line r . It reads as follows: (a,b) Theorem 3.1 Let (a, b) be in ]0, 1[×R and X in Dgm( f )\{}. Then, for each (a,b) finite coordinate w of X, a point (p , p ) in r ∩ ( f ) exists such that w = 1 2 (a,b) min{a,1−a} min{a,1−a} (p − b) = (p + b). 1 2 a 1−a In Cerri et al. (2019) 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. 4 Extension of persistence diagrams In this section we show that it is possible to extend each 2D persistent Betti numbers function from the open set ]0, 1[×R, where it is defined, to the closed set [0, 1]× R. Moreover, we prove that the matching distance between f and g can be realised on the compact set [0, 1]×[−C , C ], with C = max{ f , g }. ∞ ∞ 123 Geometry of the matching distance for 2D filtering functions Proposition 4.1 Let C be a positive real number. If 0 < a, a ≤ and |b|≤ C, then, for every b , ∗ ∗ f − f  ≤ 4|a − a | ( f + C ) + 3|b − b |. 2 ∞ (a,b) (a ,b ) { } Proof Since a, a ≤ , then min a, 1 − a = a and min a , 1 − a = a . Therefore, { } recalling that |max α, β − max{γ, δ}| ≤ max{|α − γ |, |β − δ|} and observing that (1 − a)(1 − a ) ≥ , f − b f + b f − b f + b 1 2 1 2 ∗ ∗ f − f = a max , − a max , (a,b) (a ,b ) a 1 − a a 1 − a ∞ ∞ = sup max f (x ) − b, ( f (x ) + b) 1 2 1 − a x ∈M − max f (x ) − b , ( f (x ) + b ) 1 2 1 − a a a ≤ sup max |b − b |, ( f (x ) + b) − ( f (x ) + b ) 2 2 1 − a 1 − a x ∈M ⎧   ⎫ ⎪ ⎪ ⎪   ⎪ ⎪ af (x ) + ab − aa b − a f (x ) − a b + aa b ⎪ 2 2 ⎨   ⎬ = sup max |b − b |, ⎪ (1 − a)(1 − a ) ⎪ x ∈M ⎪ ⎪ ⎪ ⎪ ⎩ ⎭ |a − a | f +|ab − a b |+|b − b |aa 2 ∞ ≤ max |b − b |, (1 − a)(1 − a ) ≤ max |b − b |, 4|a − a | f + 4|ab − a b |+ 4|b − b |aa 2 ∞ ≤ max{|b − b |, 4|a − a | f + 4|ab − a b |+|b − b |} 2 ∞ = 4|a − a | f + 4|ab − a b |+|b − b | 2 ∞ ≤ 4|a − a | f + 4|a − a ||b|+ 4|b − b |a +|b − b | 2 ∞ ≤ 4|a − a | f + 4|a − a ||b|+ 3|b − b | 2 ∞ ≤ 4|a − a |( f + C ) + 3|b − b |. 2 ∞ ∗ ∗ By observing that, if f = ( f , f ) and h = ( f , f ), then f = h ,we 1 2 2 1 (a,b) (1−a,−b) obtain an analogous result to Proposition 4.1 for a, a ≥ . Proposition 4.2 Let C be a positive real number. If ≤ a, a < 1 and |b|≤ C, then, for every b , ∗ ∗ f − f ≤ 4|a − a |( f + C ) + 3|b − b |. 1 ∞ (a,b) (a ,b ) 123 M. Ethier et al. As a consequence, the function ∗ ∗ f :]0, 1[×R → C (M , R), (a, b) → f (·,·) (a,b) is locally Lipschitz. This is the content of the following result: Theorem 4.3 If |b|≤ C, then for every 0 < a, a < 1 and every b , ∗ ∗ f − f ≤ 4|a − a |( f + C ) + 3|b − b |. (a,b) (a ,b ) 1  1 Proof If a, a ≤ or a, a ≥ , the statement follows directly from Propositions 4.1 2 2 1 1 and 4.2. Without loss of generality, we can assume that a ≤ and a ≥ . Moreover, 2 2 1 1 consider , b , , b . We have that 2 2 ∗ ∗ ∗ ∗ ∗ ∗ f − f ≤ f − f + f − f (a,b) (a ,b ) (a,b) 1 1 ( ,b) ∞  ,b   ,b 2 2 ∞ ∞ ∗ ∗ + f − f (a ,b ) ( ,b ) 2 ∞ 1 1 1 ≤ 4 a − ( f + C ) + 3|b − b|+ 4 − ( f + C ) ∞ ∞ 2 2 2 + 3|b − b |+ 4 − a ( f + C ) + 3|b − b | 1 1 = 4 a − + − a ( f + C ) + 3|b − b | 2 2 = 4|a − a |( f + C ) + 3|b − b |. In Theorem 4.3 we showed that the function f is locally Lipschitz. As (·,·) such, it can be extended to the parameter values (0, b) (resp. (1, b)) as the limit ∗ ∗ ∗ ∗ f := lim f (resp., f := lim f ), for every (a ,b )→(0,b) (a ,b )→(1,b) (0,b) (a ,b ) (1,b) (a ,b ) b in R. Such a function is continuous, and the stability of persistence diagrams with respect to the uniform norm implies that the limit lim   Dgm f (a ,b )→(0,b) (a ,b ) ∗ ∗ (resp. lim   Dgm f ) also exists and is equal to Dgm f (resp. (a ,b )→(1,b) (a ,b ) (0,b) ∗ ∗ Dgm f ). In other words, f can be uniquely extended to [0, 1]× R and this (1,b) (·,·) extension is also a locally Lipschitz function. Therefore, in the rest of this paper, we will be allowed to consider the functions f for any (a, b) in [0, 1]× R. The limit (a,b) ∗ ∗ functions f and f can be computed explicitly for any b in R: (0,b) (1,b) ∗ ∗ f (x ) = lim f (x ) (0,b) (a ,b ) (a ,b )→(0,b) f (x ) − b f (x ) + b 1 2 = lim a max , a →0 a 1 − a 123 Geometry of the matching distance for 2D filtering functions = max { f (x ) − b, 0} , ∗ ∗ f (x ) = lim f (x ) (1,b) (a ,b ) (a ,b )→(1,b) f (x ) − b f (x ) + b 1 2 = lim (1 − a ) max , a →1 a 1 − a = max {0, f (x ) + b} . ∗ ∗ Since Theorem 4.3 enables us to extend the functions f and g to [0, 1]× R, (·,·) (·,·) the function ∗ ∗ (a, b) → d Dgm f , Dgm g (4.1) (a,b) (a,b) can be extended to [0, 1]×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]×[−C , C ], where C = max{ f , g }. ∞ ∞ Proposition 4.4 There exists (a ¯ , b) in [0, 1]×[−C , C ], with C = max{ f , g }, ∞ ∞ such that ∗ ∗ D ( f , g) = max d Dgm f , Dgm g match B (a,b) (a,b) (a,b)∈[0,1]×[−C ,C ] ∗ ∗ = d Dgm f , Dgm g . ¯ ¯ (a ¯ ,b) (a ¯ ,b) Proof Our strategy is to check what happens when |b|≥ C. There are four pos- 1 1 sible cases given by the combinations of a ≤ or a ≥ and b ≤−C 2 2 or b ≥ C. Consider the case a ≤ and b ≤−C.Wehave f = 2 (a,b) 1 1 1 1 a max ( f − b), ( f + b) . However, ( f − b) ≥ ( f + C ) ≥ 0 and 1 2 1 1 a 1−a a a 1 1 ∗ ( f + b) ≤ ( f − C ) ≤ 0. Thus, f = f − b and, similarly, 2 2 1 (a,b) 1−a 1−a g = g − b. The bottleneck distance between their persistence diagrams will (a,b) ∗ ∗ thus be d Dgm f , Dgm g = d (Dgm ( f − b) , Dgm (g − b)) = B B 1 1 (a,b) (a,b) ∗ ∗ d (Dgm ( f ) , Dgm (g )). Therefore, d Dgm f , Dgm g is constant B 1 1 B (a,b) (a,b) for a ≤ and b ≤−C. Hence we can limit ourselves to computing its value for a = and b =−C. 1 ∗ 1−a Consider now a ≥ and b ≤−C.Wehave f = ( f − 2 (a,b) a 1−a b) and, similarly, g = (g − b). Fixing a, we observe that in this (a,b) a ∗ ∗ 1−a case d Dgm f , Dgm g = d (Dgm( f − b), Dgm(g − b)) = B B 1 1 (a,b) (a,b) a 1−a 1 d (Dgm( f ), Dgm(g )) is constant with respect to b. Since a ≥ was chosen B 1 1 a 2 arbitrarily, and there is no dependence on b, we can choose them to be a = and b =−C and conclude. The other two cases follow the same strategy. 123 M. Ethier et al. Fig. 3 The bottleneck distance is constant on the coloured regions and half-lines, whereas it is non-increasing with respect to a on b =−C,if a ≥ ,and non-decreasing with respect to a on b = C,if a ≤ The above proof also shows that the continuous function d Dgm f , Dgm (a,b) ∗ 1 g is constant on the segments {(a, b) | 0 ≤ a ≤ , b =−C } and {(a, b) | (a,b) 2 1 1 ≤ a ≤ 1, b = C }, non-increasing on the segment {(a, b) | 1 ≥ a ≥ , b =−C } 2 2 and non-decreasing on the segment {(a, b) | 0 ≤ a ≤ , b = C }. Moreover, it is 0on (0, C ) and (1, −C ) (see Fig. 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 as follows: match ∗ ∗ D ( f , g) = max d Dgm f , Dgm g . match B (a,b) (a,b) (a,b)∈[0,1]×R 5 Special set and matching distance 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. Definition 5.1 Let Ctr( f , g) be the set of all curves that are contours of f or g.The spe- cial set of ( f , g), denoted by Sp( f , g), is the collection of all (a, b) in ]0, 1[×[−C , C ] for which two distinct pairs {α ,α }, {α ,α } of contours in Ctr( f , g) intersecting p q s t r exist, such that {α ,α } ={α ,α } and (a,b) p q s t • c |x − x |= c |x − x |, with c , c ∈{1, 2},if a ≤ , 1 P Q 2 S T 1 2 123 Geometry of the matching distance for 2D filtering functions Fig. 4 The light blue line corresponds to the pair (0.6, 0) and the green approximately to (0.491, 0.451). They are both special, since |x − x |=|x − x | and |y − y |=|y − y | (colour figure A A B B C C D D 1 2 1 2 1 2 1 2 online) • c |y − y |= c |y − y |, with c , c ∈{1, 2},if a ≥ , 1 P Q 2 S T 1 2 where P = P = r ∩ α , Q = Q = r ∩ α , S = S = r ∩ α (a,b) (a,b) p (a,b) (a,b) q (a,b) (a,b) s and T = T = r ∩ α , and x , y denote abscissas and ordinates of these points. (a,b) (a,b) t ∗ ∗ An element of the special set Sp( f , g) is called a special value of the pair ( f , g). Special values are values of ]0, 1[×[−C , C ] in which the optimal matching may abruptly change because of the presence of more than one pair of points with the same 1 1 distance between abscissas (a ≤ ) or the same distance between ordinates (a ≥ ). 2 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 4shows two examples of lines associated with special values of ( f , g), with 2 2 f , g : S → R , 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 , A and B , B , between the green line and 1 2 1 2 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 , C and D , D , between 1 2 1 2 the light blue line and the extended Pareto grid have equal difference between ordinates. −7 In particular, (0.491, 0.451) approximates a special value up to a 5 × 10 error. Proposition 5.2 Sp( f , g) is closed in ]0, 1[×[−C , C ]. 123 M. Ethier et al. Proof First, we show that Sp( f , g) ∩ ]0, ]×[−C , C ] is closed. Consider a sequence {(a , b )} in Sp( f , g) ∩ ]0, ]×[−C , C ] that converges to (a, b) in n n ]0, ]×[−C , C ]. Since such a sequence consists of special values of ( f , g), there n n n n n exist two distinct sets {α ,α } and {α ,α } in Ctr( f , g) such that c |x − x |= P Q p q s t n n n n n n c |x − x |, where P = r ∩ α , Q = r ∩ α , S = r ∩ α and S T n (a ,b ) n (a ,b ) n (a ,b ) 2 n n n n p n n q n n s n n T = r ∩ α and c , c ∈{1, 2}, for every n. Since Ctr( f , g) has finitely many n (a ,b ) n n t 1 2 contours, we can assume, up to subsequences, that the sequences {P }, {Q }, {S } and n n n n n n n {T } lie respectively in the contours α = α , α = α , α = α and α = α ,for n p q s t p q s t n n every n. For the same reason, we can assume that c = c and c = c , for every n. 1 2 1 2 Since {(a , b )} is convergent, it is also bounded. In particular, besides −C ≤ b ≤ C, n n n there is D such that 0 < D ≤ a ≤ . Then r ∩ (( f ) ∪ (g)) is n (a ,b ) n n n bounded below by the line r 1 and above by the line r . Thus, {P }, {Q }, n n (D,−C ) ( ,C ) {S } and {T } converge, respectively, to P, Q, S and T , up to restriction to subse- n n quences. Since c |x − x |= c |x − x |, their limits are also equal, so we have 1 P Q 2 S T n n n n c |x − x |= c |x − x |. Since P, Q, S and T all lie in r , (a, b) is also a special 1 2 P Q S T (a,b) value of ( f , g), concluding that Sp( f , g) ∩ ]0, ]×[−C , C ] is closed. Analogously, one can see that Sp( f , g) ∩ [ , 1[×[−C , C ] is closed. The set Sp( f , g) is then a union of two closed sets, hence it is closed itself. Let S be the set of all pairs (a ¯ , b) in [0, 1]×[−C , C ] realising the matching distance between f and g, i.e., such that ∗ ∗ D ( f , g) = d Dgm f , Dgm g . match B ¯ ¯ (a ¯ ,b) (a ¯ ,b) ∗ ∗ As observed about (4.1), d Dgm f , Dgm g is a continuous function (a,b) (a,b) on [0, 1]×[−C , C ], thus it admits a maximum in its domain and S is not empty. Moreover, S is compact because it is the preimage of a point in R via a continuous function defined on a compact set. Note that for any (a, b) in [0, 1]×[−C , C ],wehave ∗ ∗ d Dgm f , Dgm g = cost(σ ), (5.1) B (a,b) (a,b) (a,b) where σ is an optimal matching. By applying a straightforward generalisation of (a,b) th Theorem 28 in d’Amico et al. (2010) for arbitrary n persistence diagrams, one can see that such a matching always exists. Theorem 4.3 and the stability of the bottleneck distance with respect to the uniform norm imply that cost(σ ) can be seen as a (a,b) continuous function in the variable (a, b) in [0, 1]×[−C , C ]. Definition 5.3 Let σ : Dgm → Dgm be a matching between two persistence dia- 1 2 grams and let X in Dgm be such that cost(σ ) = d(X,σ (X )). The matching σ is of type (1) if /∈{X,σ (X )}, and of type (2) if  ∈{X,σ (X )}. Observe that a matching can be both of type (1) and type (2). We use this terminology in the proof of the following theorem. 123 Geometry of the matching distance for 2D filtering functions Theorem 5.4 S ∩ Sp( f , g) ∪ 0, , 1 ×[−C , C ] =∅. Proof Assume by contradiction that every (a, b) in S is not in Sp( f , g) and that a = 0, , 1. Since S is compact, it is possible to take (a, b) in S minimising the distance from the line a = . Among these, consider (a ˆ , b) and a corresponding ∗ ∗ 1 matching  σ of minimum cost between Dgm f and Dgm g .If0 < a ˆ < , ˆ ˆ 2 (a ˆ ,b) (a ˆ ,b) the Position Theorem 3.1 implies that there exist  α and β in Ctr( f , g) intersecting r , such that P = r ∩  α and Q = r ∩ β realise at least one of these ˆ ˆ ˆ (a ˆ ,b) (a ˆ ,b) (a ˆ ,b) properties: 1. P ∈ ( f ), Q ∈ (g), and D ( f , g) = cost( σ) =|x − x |; match P Q 2. P, Q ∈ ( f ) or P, Q ∈ (g), and D ( f , g) = cost( σ) = |x − x |. match 2 P Q Observe that the former matching is of type (1) and the latter of type (2). Note also that x = x , and hence P = Q. If not, then D ( f , g) = 0, implying that any match P Q (a, b) belongs to S, including , b , which is a contradiction. Consider a sequence {(a , b )} in ]0, 1[×[−C , C ] such that these (a , b ) are cho- n n n n sen to identify lines obtained by rotating r around P clockwise in such a way (a,b) that (a , b ) → (a ˆ , b), where {a } is a decreasing sequence. Furthermore, given a n n n ∗ ∗ sequence {σ } of optimal matchings between Dgm f and Dgm g we (a ,b ) (a ,b ) n n n n have that cost(σ ) → cost( σ) (see (5.1)). Since Sp( f , g) ∪ 0, , 1 ×[−C , C ] is closed, by Proposition 5.2, and (a ˆ , b) does not belong to this set, we can assume that the sequence {(a , b )} also has no points in this set. Hence, for any n in N there exists n n a pair {P , Q } in r ∩ (( f ) ∪ (g)) for which at least one of the following n n (a ,b ) n n properties holds: (A) P ∈ ( f ), Q ∈ (g) and cost(σ ) =|x − x |; n n n P Q n n (B) P , Q ∈ ( f ) or P , Q ∈ (g), and cost(σ ) = |x − x |. n n n n n P Q n n Up to subsequences, we can assume that the matchings σ are either all of type (1) or all of type (2). We now show that {P } and P belong to the same contour in Ctr( f , g), and {Q } and Q also belong to the same contour in Ctr( f , g). Analogously to the proof of Proposition 5.2 we may observe that the set r ∩ (( f ) ∪ (g)) (a ,b ) n n n is a bounded subset of ( f ) ∪ (g). Thus, {P } and {Q } are convergent up to n n subsequences in the closed set ( f ) ∪ (g), respectively, to P and Q. By assumption, there are only a finite number of contours, thus there exists at least a contour in Ctr( f , g) for each sequence, {P } and {Q }, containing infinitely many points of the n n sequence. Hence, we can assume that each sequence, up to subsequences, lies entirely on a single contour in Ctr( f , g), i.e., we can suppose that for every n in N, P is in α and Q is in β, with α and β in Ctr( f , g). Since contours are closed, P belongs to α and Q belongs to β. We observe that {P, Q}⊆ r . Furthermore, we have that (a ˆ ,b) c |x − x |= cost( σ) = lim cost(σ ) = lim c |x − x |= c |x − x | n P Q P Q n n P Q n→∞ n→∞ 123 M. Ethier et al. Fig. 5 The clockwise rotation around P increases the distance between the abscissas of the intersection points. This fact is used in the proof of Theorem 5.4 (case 1) where c , c in { , 1}.If { α, β} ={α, β}, then (a ˆ , b) is a special value, contradicting the initial assumption. Thus, { α, β}={α, β}. Without loss of generality, by possibly exchanging the roles of the contours  α and β, and of the points P and Q, we can assume that  α = α, β = β, P = P and Q = Q. Consequently, by the fact that {P } and P are contained in the same line r and the same contour  α, P = P for (a ,b ) n n n every n, since a contour and a positive slope line can meet in at most one point. Case 1 Assume that  σ and σ are both of the same type for every n. Since Q belongs n n to β in Ctr( f , g) for any n, one can easily check that |x − x |≥|x − x | (see P P Q Fig. 5 ), and hence cost(σ ) ≥ cost( σ). If the equality holds there is a contradiction with the assumption of (a ˆ , b) minimising the distance from the line a = , since 1 1 a − < a ˆ − . If the strict inequality holds, there is a contradiction with the 2 2 assumption of  σ being in S. Case 2 Assume that all σ and  σ are of different types. This means that cost(σ ) = n n c |x − x |, cost( σ) = c |x − x |, with c = c and c , c in { , 1}, and c |x − P n P Q P x |→ c |x − x |. However, since Q → Q, c |x − x |→ c |x − x |. Thus, Q   n  Q n P Q P n P Q c |x − x |= c |x − x |, which is a contradiction since D ( f , g) = 0 and, match P Q P Q hence, x = x . P Q Inverting the role of abscissas and ordinates as described by the Position The- orem 3.1 and rotating the lines counterclockwise, one can see that an analogous procedure holds for < a ˆ < 1. 123 Geometry of the matching distance for 2D filtering functions Fig. 6 Approximation of a special set 6 Conclusions In this article we took advantage of the differential structure associated with smooth functions from a Riemannian manifold M to R to characterise some geometric proper- ties of the matching distance. We proved that the filtering lines that actually contribute to the computation of the matching distance are horizontal, vertical, of slope 1, or they are associated with parameter values in the special set. This new approach to the computation of the matching distance could lead to new effective algorithms. In this direction, we would like to highlight an open question that arose during our work. We have not yet provided a characterisation of the special set. However, we conjecture that the special set consists of a collection of curves, up to a small perturbation of the filtering functions. Figure 6 shows a selections of points in the special set for the functions f , g : S → 2 2 2 2 2 R , where S ={(x , y, z) | x + y + z = 1}, f (x , y, z) = (x + 1, z − 1) and g(x , y, z) = (0.75x − 2, 0.75z + 2). One may notice clear segments, two of which, on the left, correspond to values identifying lines through intersections of contours. Such lines are in fact always associated with special values. Acknowledgements P. Frosini was partially supported by INdAM-GNSAGA. F. Tombari was supported by the Wallenberg AI, Autonomous System and Software Program (WASP) funded by Knut and Alice Wallenberg Foundation. Funding Open access funding provided by Royal Institute of Technology. Declarations Conflict of interest On behalf of all authors, the corresponding author states that there is no conflict of interest. Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted 123 M. Ethier et al. by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/. References Bapat, A., Brooks, R., Hacker, C., Landi, C., Mahler, B.I., Stephenson, E.R.: Computing the matching distance of 2-parameter persistence. arXiv:2210.12868 (2022) Biasotti, S., Cerri, A., Frosini, P., Giorgi, D.: A new algorithm for computing the 2-dimensional matching distance between size functions. Pattern Recognit. Lett. 32(14), 1735–1746 (2011). https://doi.org/ 10.1016/j.patrec.2011.07.014 Bjerkevik, H., Kerber, M.: Asymptotic improvements on the exact matching distance for 2-parameter persistence. arXiv:2111.10303 (2021) Cerri, A., Frosini, P.: A new approximation algorithm for the matching distance in multidimensional persistence. J. Comput. Math. 38(2), 291–309 (2020). https://doi.org/10.4208/jcm.1809-m2018-0043 Cerri, A., Di Fabio, B., Ferri, M., Frosini, P., Landi, C.: Betti numbers in multidimensional persistent homology are stable functions. Math. Methods Appl. Sci. 36(12), 1543–1557 (2013). https://doi.org/ 10.1002/mma.2704 Cerri, A., Ethier, M., Frosini, P.: On the geometrical properties of the coherent matching distance in 2D persistent homology. J. Appl. Comput. Topol. 3(4), 381–422 (2019). https://doi.org/10.1007/s41468- 019-00041-y d’Amico, M., Frosini, P., Landi, C.: Natural pseudo-distance and optimal matching between reduced size functions. Acta Appl. Math. 109(2), 527–554 (2010). https://doi.org/10.1007/s10440-008-9332-1 Edelsbrunner, H., Morozov, D.: Persistent homology: theory and practice. In: European Congress of Mathematics, Eur. Math. Soc., Zürich, pp. 31–50 (2013) Kerber, M., Nigmetov, A.: Efficient approximation of the matching distance for 2-parameter persistence. In: 36th International Symposium on Computational Geometry, LIPIcs. Leibniz Int. Proc. Inform., Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, vol. 164, pp. 53–16 (2020) Kerber, M., Lesnick, M., Oudot, S.: Exact computation of the matching distance on 2-parameter persistence modules. In: 35th International Symposium on Computational Geometry, LIPIcs. Leibniz Int. Proc. Inform., Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, vol. 129, 46–15 (2019) Lesnick, M.: The theory of the interleaving distance on multidimensional persistence modules. Found. Comput. Math. 15(3), 613–650 (2015). https://doi.org/10.1007/s10208-015-9255-y Wan, Y.H.: Morse theory for two functions. Topology 14(3), 217–228 (1975). https://doi.org/10.1016/0040- 9383(75)90002-6 Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png Journal of Applied and Computational Topology Springer Journals

Geometry of the matching distance for 2D filtering functions

Download PDF
16 pages

Loading next page...
 
/lp/springer-journals/geometry-of-the-matching-distance-for-2d-filtering-functions-v1M0uexx80

References (19)

Publisher
Springer Journals
Copyright
Copyright © The Author(s) 2023
ISSN
2367-1726
eISSN
2367-1734
DOI
10.1007/s41468-023-00128-7
Publisher site
See Article on Publisher Site

Abstract

In this paper we exploit the concept of extended Pareto grid to study the geometric properties of the matching distance for R -valued regular functions defined on a closed Riemannian manifold. In particular, we prove that in this case the matching distance is realised either at special values or at values corresponding to vertical, horizontal or slope 1 lines. Keywords Matching distance · Multiparameter persistence · Extended Pareto grid · Filtering functions Mathematics Subject Classification Primary 55N31; Secondary 57R19 1 Introduction Feature extraction and comparison are the main tasks of data analysis. In topologi- cal data analysis this translates into the problem of comparing persistence modules, which encode the homological features extracted from geometric objects. In order to Francesca Tombari tombari@kth.se Marc Ethier marcdethier@gmail.com Patrizio Frosini patrizio.frosini@unibo.it Nicola Quercioli nicola.quercioli@enea.it Université du Québec en Abitibi-Témiscamingue, Rouyn-Noranda, QC, Canada Mathematics, University of Bologna, 40126 Bologna, Italy ENEA, 40129 Bologna, Italy Mathematics, KTH, 10044 Stockholm, Sweden 123 M. Ethier et al. 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 (Cerri et al. 2013, 2019; Lesnick 2015). One of those is the matching distance, which can be defined in particular for 2- parameter persistence modules. This pseudometric, introduced in Cerri et al. (2013), is a generalisation of the classical bottleneck distance for 1-parameter persistence mod- ules 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 per- sistence 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 (Bapat et al. 2022; Bjerkevik and Kerber 2021; Kerber et al. 2019)or approximation (Cerri and Frosini 2020; Biasotti et al. 2011; Kerber and Nigmetov 2020) 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 simi- lar in scope, but different in nature. We consider regular filtering functions on a smooth manifold with values in R . Their sublevel-set filtrations still return 2-parameter persis- tence 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 con- sidering persistence modules. For example, it is possible to exploit the differentiable structure of the filtering functions to identify points in the persistence diagrams asso- ciated to each filtering line. This structure made of arcs and half-lines is known as extended Pareto grid (Cerri et al. 2019)(seealsoWan 1975). 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 Bapat et al. (2022) 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, 123 Geometry of the matching distance for 2D filtering functions proved in Cerri et al. (2019), which relates points of a persistence diagram to points in the extended Pareto grid. In this paper, we aim to prove the following: Theorem The matching distance between f and g is realised either on a value asso- ciated with a line of slope 1, a vertical or horizontal line, or on a special value of ( f , g). 2 Matching distance Let M beaclosed C -manifold with a Riemannian metric defined on it. Let f : M → 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) ∈ R | x ≤ y}, known as the persistence diagram of f and denoted by Dgm( f ). The subset  ={(x , y) ∈ R | 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 Edelsbrunner and Morozov (2013) for more details about 1-parameter persistent homology for sublevel set filtrations. 2 2 Let f = ( f , f ) : M → R and g = (g , g ) : M → R be smooth 1 2 1 2 functions. Consider the set of pairs (a, b) in ]0, 1[×R with the uniform metric d ((a, b), (a , b )) = max{|a − a |, |b − b |}. It parameterises all the lines of R with positive slope in the following way: r is the line containing points of the form (a,b) t (a, 1−a)+(b, −b) with t in R. Each point (u(t ), v(t )) of r can be associated with (a,b) a,b the set M = M = {x ∈ M | f (x ) ≤ u(t ) and f (x ) ≤ v(t )}. This defines (u(t ),v(t )) 1 2 a 1-dimensional filtration, depending on the line r , which can be associated with (a,b) a persistence diagram. Letting (a, b) vary, one obtains a collection of persistence dia- grams described by the 2D persistent Betti numbers function of f . As observed in (a,b) Cerri et al. (2013), M is also equal to x ∈ M | f (x ) ≤ t , where f (x ) = (a,b) (a,b) f (x )−b f (x )+b 1 2 max , (see Fig. 1). However, more commonly, f is normalised, (a,b) a 1−a without changing the nature of the filtration, and f = min{a, 1−a} f is instead (a,b) (a,b) considered. Given two functions f and g,the matching distance (Cerri et al. 2013) is defined by ∗ ∗ D ( f , g) = sup d Dgm f , Dgm g . match B (a,b) (a,b) (a,b)∈]0,1[×R ∗ ∗ Here, d Dgm f , Dgm g is the bottleneck distance between the (a,b) (a,b) ∗ ∗ persistence diagrams of f and g , i.e., (a,b) (a,b) ∗ ∗ d Dgm f , Dgm g = inf cost(σ ), (a,b) (a,b) 123 M. Ethier et al. Fig. 1 On the left the space of parameters ]0, 1[×R is represented. On the right we show the filtering lines corresponding to the two parameters selected and the projection of a torus on the plane. Each of the lines gives a sublevel set filtration of the torus in the direction of the line. The area down and left of the red point a ,b 1 1 ¯ ¯ (a t + b ,(1 − a )t − b ) on the line r is the sublevel set M associated to such a point (colour 1 1 1 1 (a ,b ) 1 1 ¯ figure online) where cost(σ ) = max d (X,σ (X )), σ runs over all bijections, called X ∈Dgm f (a,b) ∗ ∗ matchings, between Dgm f and Dgm g and, if X = (x , x ) and Y = 1 2 (a,b) (a,b) (y , y ), then 1 2 ⎪ κ if X = (x , x ), Y = (y , y ) ∈  , 1 2 1 2 |x − y | if X = (x , ∞), Y = (y , ∞), ⎪ 1 1 1 1 ⎨ x −x 2 1 + if X = (x , x ) ∈  , Y = , 1 2 d(X , Y ) = y −y 2 1 + if Y = (y , y ) ∈  , X = , 1 2 ⎪0if X = Y = , ∞ otherwise. x −x y −y 2 1 2 1 where κ = min{max{|x − y |, |x − y |}, max{ , }}. A matching realising 1 1 2 2 2 2 the matching distance, whenever it exists, is called an optimal matching. Note that the matching distance D ( f , g) can be seen both as a pseudo-metric between the match 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 ( f , g) for both cases. match For more details about this definition and the foliation method we refer to Cerri et al. (2013). 123 Geometry of the matching distance for 2D filtering functions 3 Extended Pareto grid In this section we recall the relation between a differential construction associated with a smooth function f : M → R , called the extended Pareto grid, and the points of the persistence diagrams Dgm f . This connection is established in the Position (a,b) Theorem proved in Cerri et al. (2019). Recall that the Jacobi set of f is the collection J( f ) ={ p ∈ M |∇ f = λ∇ f or ∇ f = λ∇ f , for some λ ∈ R}. 1 2 2 1 The Pareto critical set of f is the subset of J( f ) given by J ( f ) = { p ∈ J( f ) |∇ f = λ∇ f or ∇ f = λ∇ f , for some λ ≤ 0} . P 1 2 2 1 Assume now that f is not only smooth, but it also satisfies the following properties: (i) No point p exists in M at which both ∇ f and ∇ f vanish. 1 2 (ii) J( f ) is a 1-manifold smoothly embedded in M consisting of finitely many components, each one diffeomorphic to a circle. (iii) J ( f ) is a 1-dimensional closed submanifold of M, with boundary in J( f ). (iv) If we denote by J ( f ) the subset of J( f ) where ∇ f and ∇ f are orthogonal C 1 2 to J( f ), then the connected components of J ( f ) \ J ( f ) are finite in number, P C each one being diffeomorphic to an interval. With respect to any parameterisa- tion of each component, one of f and f is strictly increasing and the other is 1 2 strictly decreasing. Each component can meet critical points for f , f only at 1 2 its endpoints. Denote by { p ,..., p } and {q ,..., q }, respectively, the critical points of f 1 h 1 k 1 and f . Since the function f satisfies (i), then { p ,..., p }∩{q ,..., q }=∅.The 2 1 h 1 k extended Pareto grid of f is defined as the union ⎛ ⎞ ⎝ ⎠ ( f ) = f (J ( f )) ∪ v ∪ h P i j i j where v is the vertical half-line {(x , y) ∈ R | x = f (p ), y ≥ f (p )} and h is the i 1 i 2 i j horizontal half-line {(x , y) ∈ R | x ≥ f (q ), y = f (q )}. We refer to these half- 1 j 2 j lines as improper contours and to the closure of the image of the connected components of J ( f ) \ J ( f ) as proper contours of ( f ). Figure 2shows an example of extended P C Pareto grid for the projection of a sphere in R on the plane y = 0. The violet horizontal half-lines originate at critical values of f , while the vertical ones originate at critical values of f . The red arcs are the images of those arcs on the sphere in which the gradients ∇ f and ∇ f have the same direction but opposite orientation. Observe 1 2 that, because of property (ii), the number of contours in ( 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 123 M. Ethier et al. 2 3 2 2 2 Fig. 2 The extended Pareto grid of the function f (x , y, z) = (x , z) on S ={(x , y, z) ∈ R | x +y +z = 1}.On the left, the red arcs are the proper contours and the violet half-lines are the improper contours. Any point in this extended Pareto grid corresponds to a birth or death of a homological class. For example, on the right side of this figure, the red points correspond to the birth of homology classes in degree 0, while the green points correspond to the birth of homology classes in degree 2 (colour figure online) about properties (i)–(iv) we refer the interested reader to Cerri et al. (2019) and Wan (1975). 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 Cerri et al. (2019, Figure 8). The Position Theorem (Theorem 2 in Cerri et al. 2019) allows us to obtain the coordinates of the points in the persistence diagram of f just by looking at the (a,b) extended Pareto grid of the function and the filtering line r . It reads as follows: (a,b) Theorem 3.1 Let (a, b) be in ]0, 1[×R and X in Dgm( f )\{}. Then, for each (a,b) finite coordinate w of X, a point (p , p ) in r ∩ ( f ) exists such that w = 1 2 (a,b) min{a,1−a} min{a,1−a} (p − b) = (p + b). 1 2 a 1−a In Cerri et al. (2019) 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. 4 Extension of persistence diagrams In this section we show that it is possible to extend each 2D persistent Betti numbers function from the open set ]0, 1[×R, where it is defined, to the closed set [0, 1]× R. Moreover, we prove that the matching distance between f and g can be realised on the compact set [0, 1]×[−C , C ], with C = max{ f , g }. ∞ ∞ 123 Geometry of the matching distance for 2D filtering functions Proposition 4.1 Let C be a positive real number. If 0 < a, a ≤ and |b|≤ C, then, for every b , ∗ ∗ f − f  ≤ 4|a − a | ( f + C ) + 3|b − b |. 2 ∞ (a,b) (a ,b ) { } Proof Since a, a ≤ , then min a, 1 − a = a and min a , 1 − a = a . Therefore, { } recalling that |max α, β − max{γ, δ}| ≤ max{|α − γ |, |β − δ|} and observing that (1 − a)(1 − a ) ≥ , f − b f + b f − b f + b 1 2 1 2 ∗ ∗ f − f = a max , − a max , (a,b) (a ,b ) a 1 − a a 1 − a ∞ ∞ = sup max f (x ) − b, ( f (x ) + b) 1 2 1 − a x ∈M − max f (x ) − b , ( f (x ) + b ) 1 2 1 − a a a ≤ sup max |b − b |, ( f (x ) + b) − ( f (x ) + b ) 2 2 1 − a 1 − a x ∈M ⎧   ⎫ ⎪ ⎪ ⎪   ⎪ ⎪ af (x ) + ab − aa b − a f (x ) − a b + aa b ⎪ 2 2 ⎨   ⎬ = sup max |b − b |, ⎪ (1 − a)(1 − a ) ⎪ x ∈M ⎪ ⎪ ⎪ ⎪ ⎩ ⎭ |a − a | f +|ab − a b |+|b − b |aa 2 ∞ ≤ max |b − b |, (1 − a)(1 − a ) ≤ max |b − b |, 4|a − a | f + 4|ab − a b |+ 4|b − b |aa 2 ∞ ≤ max{|b − b |, 4|a − a | f + 4|ab − a b |+|b − b |} 2 ∞ = 4|a − a | f + 4|ab − a b |+|b − b | 2 ∞ ≤ 4|a − a | f + 4|a − a ||b|+ 4|b − b |a +|b − b | 2 ∞ ≤ 4|a − a | f + 4|a − a ||b|+ 3|b − b | 2 ∞ ≤ 4|a − a |( f + C ) + 3|b − b |. 2 ∞ ∗ ∗ By observing that, if f = ( f , f ) and h = ( f , f ), then f = h ,we 1 2 2 1 (a,b) (1−a,−b) obtain an analogous result to Proposition 4.1 for a, a ≥ . Proposition 4.2 Let C be a positive real number. If ≤ a, a < 1 and |b|≤ C, then, for every b , ∗ ∗ f − f ≤ 4|a − a |( f + C ) + 3|b − b |. 1 ∞ (a,b) (a ,b ) 123 M. Ethier et al. As a consequence, the function ∗ ∗ f :]0, 1[×R → C (M , R), (a, b) → f (·,·) (a,b) is locally Lipschitz. This is the content of the following result: Theorem 4.3 If |b|≤ C, then for every 0 < a, a < 1 and every b , ∗ ∗ f − f ≤ 4|a − a |( f + C ) + 3|b − b |. (a,b) (a ,b ) 1  1 Proof If a, a ≤ or a, a ≥ , the statement follows directly from Propositions 4.1 2 2 1 1 and 4.2. Without loss of generality, we can assume that a ≤ and a ≥ . Moreover, 2 2 1 1 consider , b , , b . We have that 2 2 ∗ ∗ ∗ ∗ ∗ ∗ f − f ≤ f − f + f − f (a,b) (a ,b ) (a,b) 1 1 ( ,b) ∞  ,b   ,b 2 2 ∞ ∞ ∗ ∗ + f − f (a ,b ) ( ,b ) 2 ∞ 1 1 1 ≤ 4 a − ( f + C ) + 3|b − b|+ 4 − ( f + C ) ∞ ∞ 2 2 2 + 3|b − b |+ 4 − a ( f + C ) + 3|b − b | 1 1 = 4 a − + − a ( f + C ) + 3|b − b | 2 2 = 4|a − a |( f + C ) + 3|b − b |. In Theorem 4.3 we showed that the function f is locally Lipschitz. As (·,·) such, it can be extended to the parameter values (0, b) (resp. (1, b)) as the limit ∗ ∗ ∗ ∗ f := lim f (resp., f := lim f ), for every (a ,b )→(0,b) (a ,b )→(1,b) (0,b) (a ,b ) (1,b) (a ,b ) b in R. Such a function is continuous, and the stability of persistence diagrams with respect to the uniform norm implies that the limit lim   Dgm f (a ,b )→(0,b) (a ,b ) ∗ ∗ (resp. lim   Dgm f ) also exists and is equal to Dgm f (resp. (a ,b )→(1,b) (a ,b ) (0,b) ∗ ∗ Dgm f ). In other words, f can be uniquely extended to [0, 1]× R and this (1,b) (·,·) extension is also a locally Lipschitz function. Therefore, in the rest of this paper, we will be allowed to consider the functions f for any (a, b) in [0, 1]× R. The limit (a,b) ∗ ∗ functions f and f can be computed explicitly for any b in R: (0,b) (1,b) ∗ ∗ f (x ) = lim f (x ) (0,b) (a ,b ) (a ,b )→(0,b) f (x ) − b f (x ) + b 1 2 = lim a max , a →0 a 1 − a 123 Geometry of the matching distance for 2D filtering functions = max { f (x ) − b, 0} , ∗ ∗ f (x ) = lim f (x ) (1,b) (a ,b ) (a ,b )→(1,b) f (x ) − b f (x ) + b 1 2 = lim (1 − a ) max , a →1 a 1 − a = max {0, f (x ) + b} . ∗ ∗ Since Theorem 4.3 enables us to extend the functions f and g to [0, 1]× R, (·,·) (·,·) the function ∗ ∗ (a, b) → d Dgm f , Dgm g (4.1) (a,b) (a,b) can be extended to [0, 1]×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]×[−C , C ], where C = max{ f , g }. ∞ ∞ Proposition 4.4 There exists (a ¯ , b) in [0, 1]×[−C , C ], with C = max{ f , g }, ∞ ∞ such that ∗ ∗ D ( f , g) = max d Dgm f , Dgm g match B (a,b) (a,b) (a,b)∈[0,1]×[−C ,C ] ∗ ∗ = d Dgm f , Dgm g . ¯ ¯ (a ¯ ,b) (a ¯ ,b) Proof Our strategy is to check what happens when |b|≥ C. There are four pos- 1 1 sible cases given by the combinations of a ≤ or a ≥ and b ≤−C 2 2 or b ≥ C. Consider the case a ≤ and b ≤−C.Wehave f = 2 (a,b) 1 1 1 1 a max ( f − b), ( f + b) . However, ( f − b) ≥ ( f + C ) ≥ 0 and 1 2 1 1 a 1−a a a 1 1 ∗ ( f + b) ≤ ( f − C ) ≤ 0. Thus, f = f − b and, similarly, 2 2 1 (a,b) 1−a 1−a g = g − b. The bottleneck distance between their persistence diagrams will (a,b) ∗ ∗ thus be d Dgm f , Dgm g = d (Dgm ( f − b) , Dgm (g − b)) = B B 1 1 (a,b) (a,b) ∗ ∗ d (Dgm ( f ) , Dgm (g )). Therefore, d Dgm f , Dgm g is constant B 1 1 B (a,b) (a,b) for a ≤ and b ≤−C. Hence we can limit ourselves to computing its value for a = and b =−C. 1 ∗ 1−a Consider now a ≥ and b ≤−C.Wehave f = ( f − 2 (a,b) a 1−a b) and, similarly, g = (g − b). Fixing a, we observe that in this (a,b) a ∗ ∗ 1−a case d Dgm f , Dgm g = d (Dgm( f − b), Dgm(g − b)) = B B 1 1 (a,b) (a,b) a 1−a 1 d (Dgm( f ), Dgm(g )) is constant with respect to b. Since a ≥ was chosen B 1 1 a 2 arbitrarily, and there is no dependence on b, we can choose them to be a = and b =−C and conclude. The other two cases follow the same strategy. 123 M. Ethier et al. Fig. 3 The bottleneck distance is constant on the coloured regions and half-lines, whereas it is non-increasing with respect to a on b =−C,if a ≥ ,and non-decreasing with respect to a on b = C,if a ≤ The above proof also shows that the continuous function d Dgm f , Dgm (a,b) ∗ 1 g is constant on the segments {(a, b) | 0 ≤ a ≤ , b =−C } and {(a, b) | (a,b) 2 1 1 ≤ a ≤ 1, b = C }, non-increasing on the segment {(a, b) | 1 ≥ a ≥ , b =−C } 2 2 and non-decreasing on the segment {(a, b) | 0 ≤ a ≤ , b = C }. Moreover, it is 0on (0, C ) and (1, −C ) (see Fig. 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 as follows: match ∗ ∗ D ( f , g) = max d Dgm f , Dgm g . match B (a,b) (a,b) (a,b)∈[0,1]×R 5 Special set and matching distance 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. Definition 5.1 Let Ctr( f , g) be the set of all curves that are contours of f or g.The spe- cial set of ( f , g), denoted by Sp( f , g), is the collection of all (a, b) in ]0, 1[×[−C , C ] for which two distinct pairs {α ,α }, {α ,α } of contours in Ctr( f , g) intersecting p q s t r exist, such that {α ,α } ={α ,α } and (a,b) p q s t • c |x − x |= c |x − x |, with c , c ∈{1, 2},if a ≤ , 1 P Q 2 S T 1 2 123 Geometry of the matching distance for 2D filtering functions Fig. 4 The light blue line corresponds to the pair (0.6, 0) and the green approximately to (0.491, 0.451). They are both special, since |x − x |=|x − x | and |y − y |=|y − y | (colour figure A A B B C C D D 1 2 1 2 1 2 1 2 online) • c |y − y |= c |y − y |, with c , c ∈{1, 2},if a ≥ , 1 P Q 2 S T 1 2 where P = P = r ∩ α , Q = Q = r ∩ α , S = S = r ∩ α (a,b) (a,b) p (a,b) (a,b) q (a,b) (a,b) s and T = T = r ∩ α , and x , y denote abscissas and ordinates of these points. (a,b) (a,b) t ∗ ∗ An element of the special set Sp( f , g) is called a special value of the pair ( f , g). Special values are values of ]0, 1[×[−C , C ] in which the optimal matching may abruptly change because of the presence of more than one pair of points with the same 1 1 distance between abscissas (a ≤ ) or the same distance between ordinates (a ≥ ). 2 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 4shows two examples of lines associated with special values of ( f , g), with 2 2 f , g : S → R , 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 , A and B , B , between the green line and 1 2 1 2 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 , C and D , D , between 1 2 1 2 the light blue line and the extended Pareto grid have equal difference between ordinates. −7 In particular, (0.491, 0.451) approximates a special value up to a 5 × 10 error. Proposition 5.2 Sp( f , g) is closed in ]0, 1[×[−C , C ]. 123 M. Ethier et al. Proof First, we show that Sp( f , g) ∩ ]0, ]×[−C , C ] is closed. Consider a sequence {(a , b )} in Sp( f , g) ∩ ]0, ]×[−C , C ] that converges to (a, b) in n n ]0, ]×[−C , C ]. Since such a sequence consists of special values of ( f , g), there n n n n n exist two distinct sets {α ,α } and {α ,α } in Ctr( f , g) such that c |x − x |= P Q p q s t n n n n n n c |x − x |, where P = r ∩ α , Q = r ∩ α , S = r ∩ α and S T n (a ,b ) n (a ,b ) n (a ,b ) 2 n n n n p n n q n n s n n T = r ∩ α and c , c ∈{1, 2}, for every n. Since Ctr( f , g) has finitely many n (a ,b ) n n t 1 2 contours, we can assume, up to subsequences, that the sequences {P }, {Q }, {S } and n n n n n n n {T } lie respectively in the contours α = α , α = α , α = α and α = α ,for n p q s t p q s t n n every n. For the same reason, we can assume that c = c and c = c , for every n. 1 2 1 2 Since {(a , b )} is convergent, it is also bounded. In particular, besides −C ≤ b ≤ C, n n n there is D such that 0 < D ≤ a ≤ . Then r ∩ (( f ) ∪ (g)) is n (a ,b ) n n n bounded below by the line r 1 and above by the line r . Thus, {P }, {Q }, n n (D,−C ) ( ,C ) {S } and {T } converge, respectively, to P, Q, S and T , up to restriction to subse- n n quences. Since c |x − x |= c |x − x |, their limits are also equal, so we have 1 P Q 2 S T n n n n c |x − x |= c |x − x |. Since P, Q, S and T all lie in r , (a, b) is also a special 1 2 P Q S T (a,b) value of ( f , g), concluding that Sp( f , g) ∩ ]0, ]×[−C , C ] is closed. Analogously, one can see that Sp( f , g) ∩ [ , 1[×[−C , C ] is closed. The set Sp( f , g) is then a union of two closed sets, hence it is closed itself. Let S be the set of all pairs (a ¯ , b) in [0, 1]×[−C , C ] realising the matching distance between f and g, i.e., such that ∗ ∗ D ( f , g) = d Dgm f , Dgm g . match B ¯ ¯ (a ¯ ,b) (a ¯ ,b) ∗ ∗ As observed about (4.1), d Dgm f , Dgm g is a continuous function (a,b) (a,b) on [0, 1]×[−C , C ], thus it admits a maximum in its domain and S is not empty. Moreover, S is compact because it is the preimage of a point in R via a continuous function defined on a compact set. Note that for any (a, b) in [0, 1]×[−C , C ],wehave ∗ ∗ d Dgm f , Dgm g = cost(σ ), (5.1) B (a,b) (a,b) (a,b) where σ is an optimal matching. By applying a straightforward generalisation of (a,b) th Theorem 28 in d’Amico et al. (2010) for arbitrary n persistence diagrams, one can see that such a matching always exists. Theorem 4.3 and the stability of the bottleneck distance with respect to the uniform norm imply that cost(σ ) can be seen as a (a,b) continuous function in the variable (a, b) in [0, 1]×[−C , C ]. Definition 5.3 Let σ : Dgm → Dgm be a matching between two persistence dia- 1 2 grams and let X in Dgm be such that cost(σ ) = d(X,σ (X )). The matching σ is of type (1) if /∈{X,σ (X )}, and of type (2) if  ∈{X,σ (X )}. Observe that a matching can be both of type (1) and type (2). We use this terminology in the proof of the following theorem. 123 Geometry of the matching distance for 2D filtering functions Theorem 5.4 S ∩ Sp( f , g) ∪ 0, , 1 ×[−C , C ] =∅. Proof Assume by contradiction that every (a, b) in S is not in Sp( f , g) and that a = 0, , 1. Since S is compact, it is possible to take (a, b) in S minimising the distance from the line a = . Among these, consider (a ˆ , b) and a corresponding ∗ ∗ 1 matching  σ of minimum cost between Dgm f and Dgm g .If0 < a ˆ < , ˆ ˆ 2 (a ˆ ,b) (a ˆ ,b) the Position Theorem 3.1 implies that there exist  α and β in Ctr( f , g) intersecting r , such that P = r ∩  α and Q = r ∩ β realise at least one of these ˆ ˆ ˆ (a ˆ ,b) (a ˆ ,b) (a ˆ ,b) properties: 1. P ∈ ( f ), Q ∈ (g), and D ( f , g) = cost( σ) =|x − x |; match P Q 2. P, Q ∈ ( f ) or P, Q ∈ (g), and D ( f , g) = cost( σ) = |x − x |. match 2 P Q Observe that the former matching is of type (1) and the latter of type (2). Note also that x = x , and hence P = Q. If not, then D ( f , g) = 0, implying that any match P Q (a, b) belongs to S, including , b , which is a contradiction. Consider a sequence {(a , b )} in ]0, 1[×[−C , C ] such that these (a , b ) are cho- n n n n sen to identify lines obtained by rotating r around P clockwise in such a way (a,b) that (a , b ) → (a ˆ , b), where {a } is a decreasing sequence. Furthermore, given a n n n ∗ ∗ sequence {σ } of optimal matchings between Dgm f and Dgm g we (a ,b ) (a ,b ) n n n n have that cost(σ ) → cost( σ) (see (5.1)). Since Sp( f , g) ∪ 0, , 1 ×[−C , C ] is closed, by Proposition 5.2, and (a ˆ , b) does not belong to this set, we can assume that the sequence {(a , b )} also has no points in this set. Hence, for any n in N there exists n n a pair {P , Q } in r ∩ (( f ) ∪ (g)) for which at least one of the following n n (a ,b ) n n properties holds: (A) P ∈ ( f ), Q ∈ (g) and cost(σ ) =|x − x |; n n n P Q n n (B) P , Q ∈ ( f ) or P , Q ∈ (g), and cost(σ ) = |x − x |. n n n n n P Q n n Up to subsequences, we can assume that the matchings σ are either all of type (1) or all of type (2). We now show that {P } and P belong to the same contour in Ctr( f , g), and {Q } and Q also belong to the same contour in Ctr( f , g). Analogously to the proof of Proposition 5.2 we may observe that the set r ∩ (( f ) ∪ (g)) (a ,b ) n n n is a bounded subset of ( f ) ∪ (g). Thus, {P } and {Q } are convergent up to n n subsequences in the closed set ( f ) ∪ (g), respectively, to P and Q. By assumption, there are only a finite number of contours, thus there exists at least a contour in Ctr( f , g) for each sequence, {P } and {Q }, containing infinitely many points of the n n sequence. Hence, we can assume that each sequence, up to subsequences, lies entirely on a single contour in Ctr( f , g), i.e., we can suppose that for every n in N, P is in α and Q is in β, with α and β in Ctr( f , g). Since contours are closed, P belongs to α and Q belongs to β. We observe that {P, Q}⊆ r . Furthermore, we have that (a ˆ ,b) c |x − x |= cost( σ) = lim cost(σ ) = lim c |x − x |= c |x − x | n P Q P Q n n P Q n→∞ n→∞ 123 M. Ethier et al. Fig. 5 The clockwise rotation around P increases the distance between the abscissas of the intersection points. This fact is used in the proof of Theorem 5.4 (case 1) where c , c in { , 1}.If { α, β} ={α, β}, then (a ˆ , b) is a special value, contradicting the initial assumption. Thus, { α, β}={α, β}. Without loss of generality, by possibly exchanging the roles of the contours  α and β, and of the points P and Q, we can assume that  α = α, β = β, P = P and Q = Q. Consequently, by the fact that {P } and P are contained in the same line r and the same contour  α, P = P for (a ,b ) n n n every n, since a contour and a positive slope line can meet in at most one point. Case 1 Assume that  σ and σ are both of the same type for every n. Since Q belongs n n to β in Ctr( f , g) for any n, one can easily check that |x − x |≥|x − x | (see P P Q Fig. 5 ), and hence cost(σ ) ≥ cost( σ). If the equality holds there is a contradiction with the assumption of (a ˆ , b) minimising the distance from the line a = , since 1 1 a − < a ˆ − . If the strict inequality holds, there is a contradiction with the 2 2 assumption of  σ being in S. Case 2 Assume that all σ and  σ are of different types. This means that cost(σ ) = n n c |x − x |, cost( σ) = c |x − x |, with c = c and c , c in { , 1}, and c |x − P n P Q P x |→ c |x − x |. However, since Q → Q, c |x − x |→ c |x − x |. Thus, Q   n  Q n P Q P n P Q c |x − x |= c |x − x |, which is a contradiction since D ( f , g) = 0 and, match P Q P Q hence, x = x . P Q Inverting the role of abscissas and ordinates as described by the Position The- orem 3.1 and rotating the lines counterclockwise, one can see that an analogous procedure holds for < a ˆ < 1. 123 Geometry of the matching distance for 2D filtering functions Fig. 6 Approximation of a special set 6 Conclusions In this article we took advantage of the differential structure associated with smooth functions from a Riemannian manifold M to R to characterise some geometric proper- ties of the matching distance. We proved that the filtering lines that actually contribute to the computation of the matching distance are horizontal, vertical, of slope 1, or they are associated with parameter values in the special set. This new approach to the computation of the matching distance could lead to new effective algorithms. In this direction, we would like to highlight an open question that arose during our work. We have not yet provided a characterisation of the special set. However, we conjecture that the special set consists of a collection of curves, up to a small perturbation of the filtering functions. Figure 6 shows a selections of points in the special set for the functions f , g : S → 2 2 2 2 2 R , where S ={(x , y, z) | x + y + z = 1}, f (x , y, z) = (x + 1, z − 1) and g(x , y, z) = (0.75x − 2, 0.75z + 2). One may notice clear segments, two of which, on the left, correspond to values identifying lines through intersections of contours. Such lines are in fact always associated with special values. Acknowledgements P. Frosini was partially supported by INdAM-GNSAGA. F. Tombari was supported by the Wallenberg AI, Autonomous System and Software Program (WASP) funded by Knut and Alice Wallenberg Foundation. Funding Open access funding provided by Royal Institute of Technology. Declarations Conflict of interest On behalf of all authors, the corresponding author states that there is no conflict of interest. Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted 123 M. Ethier et al. by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/. References Bapat, A., Brooks, R., Hacker, C., Landi, C., Mahler, B.I., Stephenson, E.R.: Computing the matching distance of 2-parameter persistence. arXiv:2210.12868 (2022) Biasotti, S., Cerri, A., Frosini, P., Giorgi, D.: A new algorithm for computing the 2-dimensional matching distance between size functions. Pattern Recognit. Lett. 32(14), 1735–1746 (2011). https://doi.org/ 10.1016/j.patrec.2011.07.014 Bjerkevik, H., Kerber, M.: Asymptotic improvements on the exact matching distance for 2-parameter persistence. arXiv:2111.10303 (2021) Cerri, A., Frosini, P.: A new approximation algorithm for the matching distance in multidimensional persistence. J. Comput. Math. 38(2), 291–309 (2020). https://doi.org/10.4208/jcm.1809-m2018-0043 Cerri, A., Di Fabio, B., Ferri, M., Frosini, P., Landi, C.: Betti numbers in multidimensional persistent homology are stable functions. Math. Methods Appl. Sci. 36(12), 1543–1557 (2013). https://doi.org/ 10.1002/mma.2704 Cerri, A., Ethier, M., Frosini, P.: On the geometrical properties of the coherent matching distance in 2D persistent homology. J. Appl. Comput. Topol. 3(4), 381–422 (2019). https://doi.org/10.1007/s41468- 019-00041-y d’Amico, M., Frosini, P., Landi, C.: Natural pseudo-distance and optimal matching between reduced size functions. Acta Appl. Math. 109(2), 527–554 (2010). https://doi.org/10.1007/s10440-008-9332-1 Edelsbrunner, H., Morozov, D.: Persistent homology: theory and practice. In: European Congress of Mathematics, Eur. Math. Soc., Zürich, pp. 31–50 (2013) Kerber, M., Nigmetov, A.: Efficient approximation of the matching distance for 2-parameter persistence. In: 36th International Symposium on Computational Geometry, LIPIcs. Leibniz Int. Proc. Inform., Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, vol. 164, pp. 53–16 (2020) Kerber, M., Lesnick, M., Oudot, S.: Exact computation of the matching distance on 2-parameter persistence modules. In: 35th International Symposium on Computational Geometry, LIPIcs. Leibniz Int. Proc. Inform., Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, vol. 129, 46–15 (2019) Lesnick, M.: The theory of the interleaving distance on multidimensional persistence modules. Found. Comput. Math. 15(3), 613–650 (2015). https://doi.org/10.1007/s10208-015-9255-y Wan, Y.H.: Morse theory for two functions. Topology 14(3), 217–228 (1975). https://doi.org/10.1016/0040- 9383(75)90002-6 Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Journal

Journal of Applied and Computational Topology – Springer Journals

Published: Dec 1, 2023

Keywords: Matching distance; Multiparameter persistence; Extended Pareto grid; Filtering functions; Primary 55N31; Secondary 57R19

There are no references for this article.