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

Learn More →

Sparse Dowker nerves

Sparse Dowker nerves We propose sparse versions of filtered simplicial complexes used to compute persis- tent homology of point clouds and of networks. In particular, we extend the Sparse Cech Complex of Cavanna et al. (A geometric perspective on sparse filtrations. CoRR, arXiv:1506.03797, 2015) from point clouds in convex metric spaces to point clouds in arbitrary metric spaces. Along the way we formulate interleaving in terms of strict 2-categories, and we introduce the concept of Dowker dissimilarities that can be con- sidered as a common generalization of metric spaces and networks. Keywords Sparse nerve · Dowker theorem · Persistent homology · Cech complex · Rips complex Mathematics Subject Classification 55N05 · 55N99 · 55U10 · 55U99 1 Introduction This paper is the result of an attempt to obtain the interleaving guarantee for the sparse Cech complex of Cavanna et al. (2015) without using the Nerve Theorem. The rationale for this was to generalize the result from convex metric spaces to arbitrary metric spaces. We have not been able to show that the constructions of Sheehy (2013) or Cavanna et al. (2015) are interleaved with the Cech complex in arbitrary metric spaces. However, changing the construction slightly, we obtain a sub-complex of the Cech complex that is interleaved in a similar way. When applied to point clouds in a convex metric space this sub-complex is homotopic to the construction of Cavanna et al. (2015). The above constructions are two examples of general constructions presented in the body of our paper. B Morten Brun morten.brun@uib.no Nello Blaser nello.blaser@uib.no Department of Mathematics, University of Bergen, Bergen, Norway 123 2 M. Brun, N. Blaser The search for a more general version of the sparse Cech complex led us to study both different versions of filtered covers and extended metrics. We discovered that these concepts are instances of filtered relations given by functions of the form Λ : L × W →[0, ∞] from the product of two sets L and W to the interval [0, ∞]. Here we think of L as a set of landmark points and W as a set of witness points. Given t ∈[0, ∞), the relation Λ at filtration level t is Λ ={(l,w) ∈ L × W | Λ(l,w) < t }. Dowker (1952) observed that a relation R ⊆ L × W gives a cover (R(l)) of the l∈L set R ={w ∈ W | there exists l ∈ L with (l,w) ∈ R} with R(l) ={w ∈ W | (l,w) ∈ R}. The Dowker complex of the relation R is the Borsuk Nerve of this cover. The Dowker Homology Duality Theorem (Dowker 1952, Theorem 1) states that the Dowker com- plexes of R and the transposed relation R ={(w, l) | (l,w) ∈ R}⊆ W × L have isomorphic homology. In Chowdhury and Mémoli (2018), Chowdhury and Mémoli have sharpened the Dowker Homology Duality Theorem to a Dowker Homo- topy Duality Theorem stating that the Dowker complexes of R and R are homotopy equivalent after geometric realization. That result is a central ingredient in this paper. In honor of Dowker we name functions Λ : L × W →[0, ∞] Dowker dissimilar- ities. Forming the Dowker complexes of the relations Λ for t ∈[0, ∞) we obtain a filtered simplicial complex, the Dowker Nerve N Λ of Λ, with N Λ equal to the Dowker complex of Λ . The main result of our work is Theorem 2 on sparsification of Dowker nerves. Here we formulate it in the context of a finite set P contained in a metric space (M , d). Let p ,...,, p be a farthest point sampling of P with insertion radii λ ,...λ . 0 n 0 n That is, p ∈ P is arbitrary, λ =∞ and for each 0 < k ≤ n, the point p ∈ P 0 0 k is of maximal distance to p ,..., p , and this distance is λ .Let ε> 0 and let 0 k−1 k Λ : P × M →[0, ∞] be the Dowker dissimilarity given by the metric d, that is, Λ(p,w) = d(p,w). Then the Dowker Nerve N Λ is equal to the relative Cech complex C(P, M ) of P in M given by the Borsuk Nerve of all balls in M centred at points in P. 123 Sparse Dowker nerves 3 Let [n]={0,..., n} and let ϕ:[n]→[n] be a function with ϕ(0) = 0 and ϕ(k)< k for k > 0 and d(p , p ) + (ε + 1)λ /ε ≤ (ε + 1)λ /ε (1) k ϕ(k) k ϕ(k) for k = 1,..., n. The geometric idea behind this formula is that the ball centred at (ε+1)λ (ε+1)λ ϕ(k) p of radius is contained in the ball centred at p of radius , and k ϕ(k) ε ε (ε+1)λ ϕ(k) therefore at filtration levels greater than this ball can be omitted without changing the homotopy type of the nerve of the cover (Fig. 1). The Sparse Dowker Nerve of Λ is the filtered sub-complex N(Λ,ϕ,(ε + 1)λ/ε) of N Λ filtered by letting N(Λ,ϕ,(ε + 1)λ/ε)) consist of subsets σ ⊆ P such that there exists w ∈ M with d(p ,w) < min{t,(ε + 1)λ /ε, (ε + 1)λ /ε} k k ϕ(l) for every k, l ∈ σ . The geometric interpretation of this formula is firstly that balls around p are truncated at radius (ε + 1)λ /ε, that is, when they reach this radius they k k stop growing. Secondly, the nerve is restricted in the sense that p is not contributing to simplices of radius greater than (ε + 1)λ /ε. In the geometric description of ϕ(k) Cavanna et al. (2015), cones at p are truncated at width (ε + 1)λ /ε and their tops k k are cut off at height (ε + 1) λ /ε. Theorem 1 The Sparse Dowker Nerve N(Λ,ϕ,(ε + 1)λ/ε) is multiplicatively ˇ ˇ (1, 1 + ε)-interleaved with the relative Cech complex C(P, M ) of P in M. Explicitly, there are maps f : N Λ → N(Λ,ϕ,(ε + 1)λ/ε) so that for the t t (1+ε)t inclusion maps g : N(Λ,ϕ,(ε + 1)λ/ε) → N Λ , the maps f g and g f are t t t t t (1+ε)t t homotopic to the inclusion of the space of level t into the space of level (1 + ε)t of the filtered simplicial complexes N(Λ,ϕ,(ε + 1)λ/ε) and N Λ respectively. For M = R the Sparse Dowker Nerve is closely related to the Sparse Cech Complex of Cavanna et al. (2015). We have implemented both constructions and made them available at GitHub (Brun and Blaser 2018). We also provide a tutorial that can be accessed from the same GitHub repository. It turned out that the two constructions are of similar size. Chazal et al. (2014) witness complexes and Cech complexes are both instances of Dowker dissimilarities. The weighted Cech complex in (Buchet et al. 2016, Defini- tion 5.1) is also an instance of a Dowker complex. Also the filtered clique complex of a finite weighted undirected simple graph G = (V ,w), where w is a function w : G × G →[0, ∞] is an instance of a Dowker nerve: let P(V ) be the set of subsets of V and define diam(X ) if x ∈ X Λ : V × P(V ) →[0, ∞],(x , X ) → ∞ otherwise, where diam(X ) = max  w(x , x ). Then the Dowker Nerve of Λ is equal to the x ,x ∈X filtered clique complex of G. For disjoint sets L and W a Dowker dissimilarity Λ : L × W →[0, ∞] is the same thing as a weighted simple bipartite graph. On the other hand, a Dowker dissimilarity 123 4 M. Brun, N. Blaser (1 +ε)λ d(p , p ) k ϕ(k) p p k ϕ(k) Fig. 1 Sparse Dowker nerves. Let P ={ p ,..., p } be a finite subset of a metric space M , d obtained by farthest point sampling with insertion radii λ ,...,λ and let ϕ:[n]→[n] be a function satisfying 0 n (ε+1) the inequality (1). Around each point p ∈ X, we draw a truncated cone with width λ and height k k (ε+1) d(p , p )+ λ . The figure shows that the projection of the cone with center p onto M is contained k ϕ(k) k k in the projection of the cone with center p ϕ(k) of the form Λ : X × X →[0, ∞] is the same thing as a weighted directed graph with no multiple directed edges. Chowdhury and Mémoli (2018), call Dowker dissimilari- ties of this form weighted networks, and study their Dowker nerves thoroughly under the name Dowker complexes. In particular, they show that the persistent homology of the Dowker Nerve of a network is sensitive to the direction its edges. For example, for the networks A and B in Fig. 2, with self-loops of weight 0, the Dowker Nerve of network A is contractible while the Dowker Nerve of network B is homotopic to a circle at all filtration levels. Chowdhury and Mémoli also formulate a stability result for homology of Dowker nerves (Chowdhury and Mémoli 2018). We formulate interleaving of Dowker dissimilarities in such a way that their network distance is bounded below by our interleaving distance. Together with functoriality for interleav- ing distance and the Algebraic Stability Theorem (Chazal et al. 2009) this implies the (1 +ε)λ ϕ(k) (1 +ε)λ d(p , p ) + k ϕ(k) ε Sparse Dowker nerves 5 ⎛ ⎞ ⎛ ⎞ 1 1 ⎜ ⎟ ⎜ ⎟ ⎜ 0 0 ⎟ ⎜ 0 0 ⎟ ⎜ ⎟ ⎜ ⎟ A = ⎜ ⎟ B = ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ 02 02 ⎝ ⎠ ⎝ ⎠ Fig. 2 The Dowker Nerve of network A is contractible while the Dowker Nerve of network B is homotopic to a circle stability result of Chowdhury and Mémoli (2018). In the context of metric spaces, this Stability Theorem is contained in Chazal et al. (2014). Imposing conditions on a Dowker dissimilarity of the form Λ : X × X →[0, ∞], we arrive at concepts of independent interest. Most importantly, (X,Λ) is a metric space if and only if Λ satisfies Finiteness Λ(x , y)< ∞ for all x , y ∈ X. Triangle inequality Λ(x , z) ≤ Λ(x , y) + Λ(y, z) for x , y, x ∈ X. Identity of indiscernibles d(x , y) = 0 if and only if x = y. Symmetry d(x , y) = d(y, x ) for all x , y ∈ X. Removing some of the above conditions on Λ leads to various generalizations of metric spaces. In particular, the situation where Λ only is required to satisfy the triangle inequality has been studied by Lawvere (1957). He noticed that [0, ∞] is a closed symmetric monoidal category and that when the triangle inequality holds, then Λ gives X the structure of a category enriched over [0, ∞]. Guided by the Strong Functorial Dowker Theorem (Chowdhury and Mémoli 2018, Theorem 3) we have chosen to work with interleavings in the homotopy category instead of on the level of homology groups. We leave it for further investigation to decide if the Functorial Dowker Theorem can be extended to homotopy interleavings in the sense of Blumberg and Lesnick (2017). We extend the usual notion of interleaving between [0, ∞)-filtered objects in two ways. Firstly, we consider interleavings in 2-categories. We were led to do this because Dowker dissimilarities form a 2-category, and the proof of the Stability The- orem is streamlined by working in this generality. Secondly, following Bubenik et al. (2015), we allow interleaving with respect to order preserving functions of the form α:[0, ∞) →[0, ∞) satisfying t ≤ α(t ) for all t. In this context, additive interleav- ing corresponds to functions of the form α(t ) = t + a and multiplicative interleaving corresponds to functions of the form α(t ) = ct. After setting terminology and notation, the proof of our main result, Theorem 2,is a quite simple application of the functorial Dowker Theorem. It consists of two parts. First, we truncate the Dowker dissimilarity associated to a metric by replacing certain distances by infinity and show that the truncated Dowker dissimilarity is interleaved with the original Dowker dissimilarity. At that point we use the functorial Dowker 123 6 M. Brun, N. Blaser Theorem. Second, we give conditions that allow us to sparsify the Dowker Nerve of the truncated Dowker dissimilarity without changing the filtered homotopy type. The paper is organized as follows: Sect. 2 presents our main result, Theorem 2.We also show how Theorem 1 is a consequence of Theorem 2 and how the Sparse Cech complex (Cavanna et al. 2015) fits into this context. Section 3 shows that, under certain conditions, when some of the values Λ(l,w) in a Dowker dissimilarity are set to infin- ity, the homotopy type of the Dowker Nerve is only changed up to a certain interleaving. This is the first step in our proof of Theorem 2. In Sect. 4, we give a criterion ensuring that a certain sub-complex is homotopy equivalent to the Dowker Nerve of a Dowker dissimilarity. In Sect. 5, we present the homotopy category of simplicial complexes. In Sect. 6, we recollect basic terminology about 2-categories. The main motivation for going to this level of generality is that interleaving distance in the 2-category Dow of Dowker dissimilarities defined in Definition 32 generalizes network distance from Chowdhury and Mémoli (2018). In Sect. 7, we introduce the 2-category of sets and relations. Section 8 uses the Dowker Nerve construction to define a 2-category with relations as objects. Section 9 introduces interleavings in 2-categories. In Sect. 10, we define the 2-category of Dowker dissimilarities. In Sect. 11, we relate interleaving distance of Dowker dissimilarities to Gromov–Hausdorff distance of metric spaces. We finish with some concluding remarks in Sect. 12. 2 Sparse nerves of truncated Dowker dissimilarities In this section, we state and motivate our main results, postponing proofs to later sections. Definition 1 A Dowker dissimilarity Λ consists of two sets L and W and a function Λ : L × W →[0, ∞].Given t ∈[0, ∞),welet Λ ={(l,w) ∈ L × W | Λ(l,w) < t }. The Dowker Nerve of Λ is the filtered simplicial complex N Λ = (N Λ ) with t t ≥0 N Λ ={finite σ ⊆ L | there exists w ∈ W with Λ(l,w) < t for all l ∈ σ }. The zero set of Λ is L ={l ∈ L | there exists w ∈ W with Λ(l,w) = 0}. The triangle inequality is central in the work of Cavanna et al. (2015), and it will also play a central role for us. For Dowker dissimilarities we need extra structure in order to formulate the triangle inequality. Definition 2 A Dowker dissimilarity Λ : L × W →[0, ∞] satisfies the triangle inequality if the following holds: 1. For every w ∈ W there exists l ∈ L with Λ(l,w) = 0. 2. For all (l,w) ∈ L × W with Λ(l,w) = 0 and all (l ,w ) ∈ L × W,the triangle inequality 123 Sparse Dowker nerves 7 Λ(l ,w ) ≤ Λ(l ,w) + Λ(l,w ) holds. Note that if Λ satisfies the triangle inequality and if both Λ(l,w) = 0 and Λ(l ,w) = 0, then for every w ∈ W the triangle inequality implies that Λ(l ,w ) ≤ Λ(l ,w) + Λ(l,w ) = Λ(l,w ), and thus by symmetry Λ(l ,w ) = Λ(l,w ). Also note that if Λ is actually a metric Λ : L × L →[0, ∞], then it satisfies the triangle inequality in the above sense. Unfortunately the Sparse Dowker Nerve presented in this paper needs a Dowker dissimilarity satisfying the triangle inequality as input. There are many interesting examples of Dowker dissimilarities where it is not satisfied. For example the triangle inequality is rarely satisfied for weighted networks or Bregman divergences. Typical examples of Dowker dissimilarities satisfying the triangle inequality are quasi-metrics and pseudo-metrics. The following concept of insertion pairs is the crucial ingredient in Sect. 3 where we treat interleaving of truncated Dowker Nerves. Definition 3 An insertion pair for Λ consists of a pair ( f ,λ) of functions f : W × [0, ∞] → W and λ : W →[0, ∞] with the property that for every (l,w) ∈ L × W with Λ(l,w) = 0 and every t ≥ 0 the inequalities Λ(l, f (w, t )) ≤ t <λ( f (w, t )) are satisfied. Insertion pairs generalize farthest point samples. Let d : W × W →[0, ∞] beametric and w ,...,w be a farthest point sample with insertion times λ ,...,λ . Then the 0 n 0 n functions λ(w ) = λ and f (w, t ) = argmin {d(w, w ) | λ > t } are an insertion i i i i w ∈W pair. For Dowker dissimilarities of the form Λ : L ×[n]→[0, ∞] satisfying the triangle inequality the following definition gives an example of an insertion pair for Λ.Here and throughout this paper we will use the notation [n]={0,..., n}. Definition 4 Let Λ : L ×[n]→[0, ∞] be a Dowker dissimilarity satisfying the triangle inequality. The canonical insertion function for Λ : L ×[n]→[0, ∞] is the function λ :[n]→[0, ∞] defined as ∞ if w = 0 λ (w) = sup inf Λ(l,w ) if w> 0. w ∈[w−1] l∈L The canonical insertion pair for Λ is the pair ( f ,λ ) where the function Λ Λ f :[n]×[0, ∞] → [n] 123 8 M. Brun, N. Blaser is defined as follows: Given w ∈[n] and t ≥ 0, pick l ∈ L with Λ(l,w) = 0 and define f (w, t ) = min{w ∈[n]| Λ(l,w ) ≤ t }. The definition of f (w, t ) is independent of the choise of l and the set {w ∈[n]| Λ(l,w ) ≤ t } is non-empty because sup inf Λ(l,w ) = 0 ≤ t . w ∈[n] l∈L Also, by construction Λ(l,w) = 0 implies that Λ(l, f (w, t )) ≤ t <λ ( f (w, t )). Λ Λ Λ The following lemma summarizes this discussion. Lemma 1 Let Λ : L ×[n]→[0, ∞] be a Dowker dissimilarity satisfying the triangle inequality. Then the canonical insertion pair ( f ,λ ) is an insertion pair for Λ. Λ Λ The Sparse Cech Nerve of Cavanna et al. (2015) is constructed with a positive number ε as a parameter controlling its quality in the sense that the Sparse Cech Nerve is multiplicatively (1, 1 + ε)-interleaved with the Cech Nerve. The following definition allows us to construct Sparse Dowker Nerves that are (id,α)-interleaved with the Dowker Nerve for a large class of translation functions α:[0, ∞) →[0, ∞).Here a translation function is an order-preserving function α:[0, ∞) →[0, ∞) with the property that α(t ) ≥ t for every t ∈[0, ∞). In the following definition, we use the generalized inverse of order preserving functions (see e.g. Embrechts and Hofert 2013 for more details). Definition 5 Let α:[0, ∞] → [0, ∞] be order preserving with lim α(t ) =∞. t →∞ The generalized inverse function α :[0, ∞] → [0, ∞] is the order preserving func- tion α (s) = inf{t ∈[0, ∞] | α(t ) ≥ s}. The above definition can be summarized as follows: α (s) ≤ t ⇐⇒ s ≤ α(t ). 123 Sparse Dowker nerves 9 Definition 6 Let β :[0, ∞] → [0, ∞] be an order preserving function. The translation function associated to β is the function α:[0, ∞] → [0, ∞] defined by α(t ) = t + β(t ). The first step in the construction of a Sparse Dowker Nerve of a Dowker dissimilarity Λ, is to truncate Λ by replacing some of the values Λ(l,w) by ∞. In the Euclidean case, this means that we truncate cones by only allowing them to grow to a certain width, as illustrated in Fig. 1. With the objective of the Sparse Dowker Nerve being (α, id)-interleaved with the Dowker Nerve in the sense of Definition 28.Wedothis as follows: Definition 7 Let Λ : L ×W →[0, ∞] be a Dowker dissimilarity satisfying the triangle inequality and let ( f ,λ) be an insertion pair for Λ.Let β :[0, ∞] → [0, ∞] be an order preserving function with lim β(t ) =∞ and let α be the translation function t →∞ associated to β.The β-truncation function λ : W → W associated to λ is the function λ (w) = αβ (λ(w)). (λ,β) The (λ, β)-truncation of Λ is the Dowker dissimilarity Λ : L × W →[0, ∞] defined by Λ(l,w) if Λ(l,w) ≤ λ (w) and β(0) ≤ λ(w) (λ,β) Λ (l,w) = ∞ otherwise. Example 1 Let Λ : L ×[n]→[0, ∞] be a Dowker dissimilarity satisfying the triangle inequality. Given a ≥ 0 and ε> 0, we define β(t ) = a + εt for t ∈[0, ∞].The translation function α associated to β is the affine function α(t ) = a + (1 + ε)t, and the function αβ is given by the formula (1+ε)t −a if t ≥ a/(1 + ε) (αβ )(t ) = 0 otherwise. In Theorem 2 below we state that persistent homology of the (λ, β)-truncation of Λ is (α, id)-interleaved with the persistent homolgoy of Λ. The last step in the construction of a Sparse Dowker Nerve of a Dowker dis- similarity Λ, is to restrict the Dowker Nerve of its transposed Dowker dissimilarity T T Λ : W × L →[0, ∞] given by Λ (w, l) = Λ(l,w). By restricting we mean that w ∈ W is not contributing to simplices of radius greater than a certain threshold. The purpose of the following definition is to give such a threshold. Definition 8 Let Λ : L ×[n]→[0, ∞] be a Dowker dissimilarity and let λ:[n]→ [0, ∞] be a function with λ(w) < ∞ for w> 0 and λ(0) =∞.The parent function for Λ with respect to λ is the function ϕ:[n]→[n] 123 10 M. Brun, N. Blaser defined by ϕ(0) = 0 and ϕ(w) = argmin{λ(w ) | λ(w )>λ(w) and for all l ∈ L with Λ(l,w) < λ(w), we have Λ(l,w )<λ(w )} for w> 0in [n]. Note that if w> 0, then λ(w) < ∞ and λ(w) < λ(ϕ(w)). Also note that the parent function is not necessarily uniquely defined because there may be more than one w with λ(w ) minimal under the condition that both λ(w )>λ(w) and Λ(l,w) < λ(w) implies Λ(l,w )<λ(w ). We now give the last ingredient in the construction of the Sparse Dowker Nerve. Definition 9 Let Γ :[n]× W →[0, ∞] be a Dowker dissimilarity. Given functions ϕ:[n]→[n] and λ:[n]→[0, ∞],the sparse nerve of Γ with respect to λ and ϕ is the filtered simplicial complex N(Γ ,ϕ,λ) with N(Γ ,ϕ,λ)(t ) consisting of all σ ⊆[n] so that there exists w ∈ W with Γ(l,w) < min(t,λ(l), λ(ϕ(l ))) for all l, l ∈ σ. In abbreviated form the simplicial complex N(Γ ,ϕ,λ)(t ) is {σ ⊆[n]|∃w ∈ W : Γ(l,w) < min(t,λ(l), λ(ϕ(l ))) for all l, l ∈ σ }. We are ready to state our main result about the Sparse Dowker Nerve: Theorem 2 Let Λ : L ×[n]→[0, ∞] be a Dowker dissimilarity satisfying the triangle inequality and with Λ(l, 0)< ∞ for every l ∈ L. Let β :[0, ∞] → [0, ∞] be an order preserving function with β(t)< ∞ for t < ∞ and lim β(t ) =∞ and let t →∞ λ be the β-truncation function associated to the canonical insertion function for Λ. (λ ,β) T If we let ϕ be the parent function for Λ with respect to λ and write Γ = (Λ ) , T T then the Dowker Nerve N Λ of Λ is (α, id)-interleaved with the filtered simplicial complex N(Γ ,ϕ,λ ). Proof We show the interleaving in four steps FDT FDT P3 P2 T (λ ,β) N Λ  N Λ −→ N (Λ )  N Γ  N(Γ ,ϕ,λ ), where Proposition 2 (P2) gives the interleaving and the homotopy equivalences are given by the Strong Functorial Dowker Theorem (Chowdhury and Mémoli 2018, Theorem 3) (FDT) and Proposition 3 (P3). More precisely, the functorial Dowker Theorem (Chowdhury and Mémoli 2018, Theorem 3) implies that the filtered simplicial complexes N Λ and N Λ are homotopy equivalent. By construction in Definitions 6 and 7,if Γ(k, l)< ∞ then Γ(k, l)< λ (k). Therefore, by Proposition 3 the filtered simplicial complexes N(Γ ,ϕ,λ ) and β β N Γ are homotopy equivalent. The Strong Functorial Dowker Theorem (Chowdhury and Mémoli 2018, Theorem 3) implies that the filtered simplicial complexes N Γ and 123 Sparse Dowker nerves 11 (λ ,β) N (Λ ) are homotopy equivalent. By Lemma 1 the pair ( f ,λ ) is an insertion Λ Λ (λ ,β) pair for Λ, so by Proposition 2 the filtered simplicial complexes N Λ and N (Λ ) are (α, id)-interleaved. Remark 1 The Dowker Theorem (Dowker 1952, Theorem 1a) implies that the persis- tent homology of N Λ is isomorphic to the persistent homology of N Λ and that the (λ ,β) persistent homology of N Γ is isomorphic to the persistent homology of N (Λ ). Thus, if we are only interested in persistent homology, we do not need the Functorial Dowker Theorem. Corollary 1 Let Λ : L ×[n]→[0, ∞] be a Dowker dissimilarity satisfying the triangle inequality and with Λ(l, 0)< ∞ for every l ∈ L and let β :[0, ∞] → [0, ∞] be the function β(t ) = εt and let α:[0, ∞] → [0, ∞] be the translation function α(t ) = (ε + 1)t associated to β.For λ the β-truncation function associated to the canonical insertion function of Λ and ϕ the parent function for Λ with respect to λ , the Dowker Nerve T T N Λ of Λ is (α, id)-interleaved with the filtered simplicial complex (λ ,β) T N ((Λ ) ,ϕ,λ ). Specializing even further, we obtain a variation of the Sparse Cech complex of Cavanna et al. (2015). Recall that the Hausdorff distance of a metric space L = (L, d) and a subset P of L is d (L, P) = sup inf d(l, p). p∈P l∈L In the following result we have in mind the situation where L is a compact sub- manifold of Euclidean space R with convex hull M and P is a sample of points from ˇ ˇ ˇ L. Note that in this situation the relative Cech complexes C(L, M ) and C(L, R ) are homotopy equivalent. Corollary 2 Let (M , d) be a metric space, let L ⊆ M be a compact subset, let P be a finite subset of L and let [n] − → P be a bijection. Let Λ : M ×[n]→[0, ∞] be the function Λ(x,w) = d(x , p ), wherewewrite p = p(w). Let ε> 0 and let β :[0, ∞] → [0, ∞] be the function β(t ) = εt with associated translation function α(t ) = (ε+1)t. For λ the β-truncation function associated to the canonical insertion function of Λ and ϕ the parent function 123 12 M. Brun, N. Blaser T T for Λ with respect to λ , the Dowker Nerve N Λ of Λ is (α, id)-interleaved with the filtered simplicial complex (λ ,β) T N ((Λ ) ,ϕ,λ ). Moreover, the Dowker Nerve of N Λ is additively (0, d (L, P))-interleaved with the relative Cech complex C(L, M ) consisting of all balls in M with centers in L. ˇ ˇ ˇ Sometimes we refer to the relative Cech complex C(L, M ) as the ambient Cech com- ˇ ˇ ˇ plex and to the relative Cech complex C(L, L) as the intrinsic Cech complex of L. Proof Corollary 1 gives that N Λ is (α, id)-interleaved with (λ ,β) T N ((Λ ) ,ϕ,λ ). For the second statement, first note that N Λ is homotopy equivalent to the relative ˇ ˇ ˇ ˇ Cech complex C(P, M ). Thus it suffices to show that the Cech complexes C(P, M ) and C(L, M ) are additively (0, d (L, P))-interleaved. Since P ⊆ L, for every t ∈[0, ∞), ˇ ˇ there is an inclusion ι : C (P, M ) → C (L, M ).Let f : L → P be a function with t t t d(l, f (l)) ≤ d (L, P) for every l ∈ L. The triangle inequality implies that f induces ˇ ˇ a morphism f : C (L, M ) ⊆ C (L, M ). By construction the composites f ι t t t +d (L,P) t t and ι f are contiguous to the respective identity maps, and thus their geo- t +d (L,P) t metric realizations are homotopic Spanier (1966). Finally, we show that the Sparse Cech complex of Cavanna et al. (2015) is an instance of a Sparse Dowker Nerve. We suspect that Cavanna et al.’s construction performed to Dowker dissimilarities is homotopy equivalent to the Sparse Dowker Nerve but we have not been able to prove this. However, the following result, together with the first part of the proof of (Cavanna et al. 2015, Theorem 5) implies that the Cavanna et al.’s Sparse Cech Nerve is homotopy equivalent to the Sparse Dowker Nerve for the Dowker dissimilarities in the following proposition. d d Proposition 1 Let d be a convex metric on R and let P be a finite subset of R together with a greedy order [n] − → P. Let the function Λ : R ×[n]→[0, ∞] be given by Λ(l,w) = d(l, p ), wherewewrite p = p(w). Let ε> 0 and let β:[0, ∞] → [0, ∞] and α:[0, ∞] → [0, ∞] be the functions β(t ) = εt and α(t ) = (1 + ε)t. Let λ be the canonical insertion function for Λ and let λ = ((1 + ε) /ε)λ . Then the filtered simplicial complex (λ ,β) T N ((Λ ) , id,λ)(t ) is isomorphic to the filtered simplicial complex  C (ε ) where ε >ε C (ε ) = S (ε ) s<t 123 Sparse Dowker nerves 13 and S(ε ) ={S (ε )} is the sparse Cech complex constructed in (Cavanna et al. t ≥0 2015, Sect. 4) for the parameter ε . Proof A subset σ ⊆[n] is in (λ ,β) T N ((Λ ) ) if and only if there exists w ∈ R so that for all l ∈ σ we have d(p ,w) < t and d(p ,w) < λ (l)(1 + ε)/ε. l l Λ Moreover T (λ ,β) T σ ∈ N (((Λ ) ) , id,λ)(t ) if and only if there exists w ∈ R so that for all k, l ∈ σ we have d(p ,w) < t and d(p ,w) < λ (k)(1 + ε)/ε and d(p ,w) < λ (l)(1 + ε) /ε. k Λ k Λ s  d On the other hand, σ ∈ S (ε ) if and only if there exists s < t and w ∈ R so s<t that w ∈ b (s) for all l ∈ σ . By the definition of b (s) in Cavanna et al. (2015), Sect. l l 3, this is the case if and only if s < t and s ≤ λ (l)(1 + ε ) /ε and d(p ,w) ≤ min(s,λ (l)(1 + ε )/ε ) Λ l Λ t d for every l ∈ σ . We conclude that σ ∈ S if and only if there exists w ∈ R satisfying d(p ,w) < t and d(p ,w) ≤ λ (l)(1 + ε )/ε and d(p ,w) < λ (l)(1 + ε ) /ε . l Λ k Λ for all k, l ∈ σ . We have not performed any complexity analysis of Sparse Dowker Nerves. Instead we have made proof-of-concept implementations of both the Sparse Cech Complex of Cavanna et al. (2015) described in Proposition 1 and the Sparse Dowker Nerve described in Corollary 2. These implementations come with the same interleaving guarantees, but for practical reasons concerning the miniball algorithm we consider complexes that are slightly bigger than the ones described above. More specifically, we compute filtration values using the miniball algorithm instead of computing radius of simplices in the truncated Dowker nerve. This gives us a filtered simplicial complex that lies between the truncated Dowker nerve and the full Dowker nerve, so it has the same interleaving guarantee as the truncated Dowker nerve. We have tested these implementations on the following data: the optical patch data sets called X (300, 30) and X (15, 30) in Carlsson et al. (2008), 6040 points from the cyclo-octane conformation space as analysed in Zomorodian (2012), the Clifford data set consisting of 2000 points on a curve on a torus considered in Oudot (2015), Chapter 123 14 M. Brun, N. Blaser Table 1 Sizes of sparse Dowker nerves using Sparse Cech Complex of Cavanna et al. (2015) described in Proposition 1 (Sheehy) and the Sparse Dowker Nerve described in Corollary 2 (parent) Data Complex Dim ε Unreduced (millions) Sheehy (millions) Parent (millions) Clifford torus Intrinsic 2 2.0 2593.9 1.3 2.8 Clifford torus Ambient 2 2.0 2593.9 1.4 1.0 Cyclo-octane Intrinsic 1 2.0 20.8 1.0 1.0 Cyclo-octane Ambient 1 2.0 20.8 1.0 1.0 Double torus Intrinsic 2 2.0 2593.9 1.5 2.9 Double torus Ambient 2 2.0 2593.9 1.8 1.9 X (15, 30) Intrinsic 1 1.5 20.8 3.3 3.2 X (15, 30) Ambient 1 1.5 20.8 3.3 3.2 X (300, 30) Intrinsic 1 2.5 20.8 4.9 1.8 X (300, 30) Ambient 1 2.5 20.8 1.8 1.7 In order to run these examples, we first used a farthest point sampling to take 500 points and calculated persistent homology of the subsamples. In the table we specify the name of the dataset (data), if persistent homology was computed using intrinsic or ambient Cech complex (complex), the homology dimension (dim), and the sparsification constant (ε). Note that both sparsifications result in substantially smaller nerves than the unreduced nerve. In general the two sparsifications result in nerves of similar sizes, but that for each sparsification there are outliers which are substantially larger 5, and the double torus from Dey et al. (2016) (Table 1). Computing the Sparse Cech complexes and the Sparse Dowker Nerves on these data sets with the same interleaving constant ε the resulting simplicial complexes are almost of the same size, with the size of the Sparse Dowker Nerve slightly smaller than the size of the Sparse Cech Complex. Our implementations, the data sets mentioned above and the scripts used to run compute persistent homology are available (Brun and Blaser 2018). 3 Truncated Dowker dissimilarities In this section, we provide the interleaving guarantee for the truncated Dowker dis- similarity used in the first step of the construction of the Sparse Dowker Nerve. Lemma 2 Let Λ : L × W →[0, ∞] be a Dowker dissimilarity satisfying the triangle inequality and let ( f ,λ) be an insertion pair for Λ.If β :[0, ∞] → [0, ∞] is an order preserving function satisfying β(t)< ∞ for t < ∞ and lim β(t ) =∞ t →∞ with associated translation function α:[0, ∞] → [0, ∞], then for every t ∈[0, ∞), (λ,β) the simplicial complex N Λ is contained in the simplicial complex N Λ . α(t ) (λ,β) Proof Let t ∈[0, ∞) and σ ∈ N Λ . We need to show that σ ∈ N Λ .Pick w ∈ W αt with Λ(l,w) < t for all l ∈ σ . Since Λ satisfies the triangle inequality we can pick l ∈ L so that Λ(l ,w) = 0. Let w = f (w, β(t )). Since ( f ,λ) is an insertion pair 0 0 0 for Λ we have Λ(l ,w ) ≤ β(t)<λ(w ). 0 0 0 123 Sparse Dowker nerves 15 The triangle inequality for Λ now gives Λ(l,w ) ≤ Λ(l ,w ) + Λ(l,w). 0 0 0 Let l ∈ σ . Since Λ(l,w) < t and Λ(l ,w ) ≤ β(t ), we get that 0 0 Λ(l,w )<β(t ) + t = α(t ). The inequality β(t)<λ(w ) implies that the set A ={s | λ(w ) ≤ β(s)} is contained 0 0 ← ← in (t , ∞). By definition β (λ(w )) = inf A,soweget t ≤ β (λ(w )). Since α is 0 0 ← ← order preserving this gives α(t ) ≤ αβ (λ(w )) and thus Λ(l,w )<αβ (λ(w )). 0 0 0 (λ,β) We conclude that σ ∈ N Λ . α(t ) Proposition 2 Let Λ : L × W →[0, ∞] be a Dowker dissimilarity satisfying the triangle inequality and let ( f ,λ) be an insertion pair for Λ.If β :[0, ∞] → [0, ∞] is an order preserving function satisfying β(t)< ∞ for t < ∞ and lim β(t ) =∞ t →∞ with associated translation function α:[0, ∞] → [0, ∞], then the filtered simplicial (λ,β) complexes N Λ and N Λ are (α, id)-interleaved. Proof By Lemma 2, for every t ∈[0, ∞), the simplicial complex N Λ is contained in (λ,β) (λ,β) the simplicial complex N Λ . Since Λ(l,w) ≤ Λ (l,w) for all (l,w) ∈ L ×W , α(t ) (λ,β) the simplicial complex N Λ is contained in the simplicial complex N Λ for every t t t ∈[0, ∞). 4 Sparse Dowker nerves In this section, we provide the technical result ensuring that the Dowker Nerve of the truncated Dowker dissimilarity can be further sparsified without changing its homo- topy type. Proposition 3 Let Λ:[n]× W →[0, ∞] be a Dowker dissimilarity and let ϕ:[n]→ [n] be a parent function for Λ with respect to λ:[n]→[0, ∞].If Λ(l,w) < ∞ implies Λ(l,w) < λ(l), then for every t ∈[0, ∞) the inclusion ι : N(Λ,ϕ,λ)(t ) − → N Λ is a homotopy equivalence. Proof By permuting the elements of [n] we can, without loss of generality, assume that λ(ϕ(l)) < λ(ϕ(l )) implies l > l . Note that if ϕ(l)> 0, then λ(ϕ(l)) < λ(ϕ(ϕ(l)), and deduce that l >ϕ(l) for every l > 0. 123 16 M. Brun, N. Blaser Let t ∈[0, ∞). We will prove the assertion by induction on n. The statement obviously holds when λ(ϕ(n)) ≥ t. In particular, it holds for n = 0. Let n ≥ 1 and suppose by induction that the statement holds for n − 1. We assume that λ(ϕ(n)) < t since otherwise the statement obviously holds for n.Let Λ :[n − 1]× W →[0, ∞] be the restriction of Λ to [n − 1]× W ⊆[n]× W and let λ and ϕ the restrictions of λ and ϕ to [n − 1]. Then ϕ is the parent function for Λ with respect to λ so the induction hypothesis is satisfied for Λ ,ϕ and λ . We define f :[n]→[n − 1] by ϕ(n) if l = n f (l) = l otherwise. Given σ ∈ N Λ we claim that σ ∪ f (σ ) ∈ N Λ .If n ∈ / σ , then this claim is trivial. t t t In order to justify the claim when n ∈ σ,wepick w ∈ W with Λ(l,w) < t for every l ∈ σ . By our assumption on Λ we then also have Λ(l,w) < λ(l) for every l ∈ σ.By definition of the parent function, Λ(n,w) < λ(n) implies Λ(ϕ(n), w) < λ(ϕ(n)) < t. We conclude that σ ∪ f (σ ) ∈ N Λ . t t Our next claim is that if σ ∈ N(Λ,ϕ,λ)(t ), then σ ∪ f (σ ) ∈ N(Λ,ϕ,λ)(t ).Again, we only need to consider the case n ∈ σ . We have already shown that σ ∪ f (σ ) ∈ N Λ . t t Since n is maximal in [n] we have λ(ϕ(l)) ≥ λ(ϕ(n)) for every l ∈[n], so this claim follows since Λ(n,w) < λ(n) implies Λ(ϕ(n), w) < λ(ϕ(n)). In particular, we can now conclude that the function f :[n]→[n − 1] and defines simplicial maps f : N Λ → N Λ t t and f : N(Λ,ϕ,λ)(t ) → N (Λ ,ϕ ,λ )(t ). On the other hand, the inclusion ι:[n −1]→[n] defines simplicial maps (see Sect. 5) ι : N Λ → N Λ and ι : N (Λ ,ϕ ,λ )(t ) → N(Λ,ϕ,λ)(t ). Moreover the above claims imply that the compositions f ι N Λ − → N Λ − → N Λ t t and f ι N(Λ,ϕ,λ)(t ) − → N (Λ ,ϕ ,λ )(t ) − → N(Λ,ϕ,λ)(t ) 123 Sparse Dowker nerves 17 are contiguous to the identity maps. Since f ι is the identity this implies that geometric realizations of the inclusions N Λ − → N Λ and N (Λ ,ϕ ,λ )(t ) − → N(Λ,ϕ,λ)(t ) are homotopy equivalences. Since we have assumed by induction that the geometric realization of the inclusion N (Λ ,ϕ ,λ )(t ) − → N Λ is a homotopy equivalence, we can conclude that the geometric realization of the inclusion N(Λ,ϕ,λ)(t ) − → N Λ is a homotopy equivalence. 5 The homotopy category of simplicial complexes The rest of the paper is aimed at stability results for Dowker Nerves. First we need some prerequisites on the homotopy category. Recall that a simplicial complex K = (V , K ) consists of a vertex set V and a set K of finite subsets of V with the property that if σ is a member of K , then every subset of σ is a member of K . Given a subset V ⊆ V and a simplicial complex K = (V , K ), we write K for the simplicial complex K = (V , K ) consisting of subsets of V V V V of the form σ ∩ V for σ ∈ K.The geometric realization of a simplicial complex K = (V , K ) is the space |K | consisting of all functions f : V →[0, 1] satisfying: 1. The support {v ∈ V | f (v) = 0} of f is a member of K 2. f (v) = 1. v∈V If V is finite, then |K | is given the subspace topology of the Euclidean space R . Otherwise U ⊆|K | is open if and only if for every finite V ⊆ V,the set U ∩|K  | is open in |K  |. The order complex of a partially ordered set (X , ≤) is the simplicial complex with vertex set X consisting of totally ordered finite subsets of X, that is, subsets of the form σ ={x , x ,..., x } with x < x < ··· x . 0 1 k 0 1 k A simplicial map f : K → L of simplicial complexes K = (V , K ) and L = (W , L) consists of a function f : V → W such that f (σ ) ={ f (v) | v ∈ σ } 123 18 M. Brun, N. Blaser is in L for every σ ∈ K . Observe that a simplicial map f : K → L induces a continuous map | f |: |K|→|L| of geometric realizations and that this promotes the geometric realization to a functor |·|: Cx → Top from the category Cx of simplicial complexes and simplicial maps to the category Top of topological spaces and continuous maps. Definition 10 The homotopy category hCx of simplicial complexes has the class of simplicial complexes as objects. Given simplicial complexes K and L, the morphism set hCx(K , L) is the set of homotopy classes of continuous maps from the geometric realization of K to the geometric realization of L. Composition in hCx is given by composition of functions representing homotopy classes. We remark in passing that the homotopy category of simplicial complexes is equivalent to the weak homotopy category of topological spaces. 6 Background on 2-categories We have chosen to reason about stability in the context of 2-categories. The pay-off from this high level of abstraction is that the proofs get relatively easy. In this section, we present some terminology on 2-categories. Most of this material is taken from Leinster (1998). Recall that a 2-category C consists of 1. A class of objects A, B,... 2. For all objects A, B a category C(A, B). The objects of C(A, B) are the morphisms in C and the morphisms α : f ⇒ g of C(A, B) are the 2-cells in C. 3. For every object A of C there is an identity morphism id : A → A and an identity 2-cell id : id ⇒ id . id A A 4. For all objects A, B and C of C there is a functor C(A, B) × C(B, C ) → C(A, C ) ( f , g) → g · f , which is associative and admits the identity morphisms and identity 2-cells of C as identities. Definition 11 Given 2-categories C and D,a functor F : C → D consists of 1. A function F : ob C → ob D 2. Functors F : C(A, B) → D(FA, FB) such that F (id ) = id and Fg ◦Ff = F (g ◦ f ) for A an object of C and f : A → B A FA and g : B → C morphisms of C. Definition 12 Given two functors F , G : C → D of 2-categories, a transformation α : F → G consists of 1. A morphism α : FA → GA in D for every A ∈ ob C 2. A 2-cell α : Gf ◦ α → α ◦ Ff for every morphism f : A → B in C. f A B 123 Sparse Dowker nerves 19 This structure is subject to the axioms given by commutativity of the following two diagrams: Gg ◦ α ◦ Ff id ◦α α ◦id Gg f g Ff g· f Gg ◦ Gf ◦ α α ◦ Fg ◦ Ff A C id id id G(id ) ◦ α α ◦ F (id A). A A A Definition 13 Given two functors F , G : C → D of 2-categories, and transformations α, β : F → G,a modification M : α → β consists of a 2-cell M : α → β A A A for every object A of C such that for every morphism f : A → B of C the following diagram commutes: id ◦M Gf A Gf ◦ α Gf ◦ β A A f β M ◦id B Ff α ◦ Ff β ◦ Ff . B B Definition 14 Given 2-categories C and D,the functor 2-category [C, D] is the 2- category with functors F : C → D as objects, transformations of such functors as morphisms and with 2-cells given by modifications. Given a category C we will consider it as a 2-category with only identity 2-cells. Thus, if C is a category and D is a 2-category we have defined the functor 2-categories [C, D] and [D, C]. op Definition 15 The opposite of a 2-category C is the 2-category C with the same objects as C, with op C (A, B) = C(B, A) and with composition obtained from composition in C. 7 Relations Dowker dissimilarities can be considered as filtered relations. In order to formulate this precisely, we need some background information on relations. 123 20 M. Brun, N. Blaser Definition 16 Let X and Y be sets. A relation R : X  Y is a subset R ⊆ X × Y . Definition 17 We define a partial order on the set of relations between X and Y by set inclusion. That is, for relations R : X  Y and R : X  Y,wehave R ≤ R if and only if R is contained in the subset R of X × Y . Definition 18 Given two relations R : X  Y and S : Y  Z, their composition S ◦ R : X  Z is S ◦ R ={(x , z) ∈ X × Z |∃ y ∈ Y : (x , y) ∈ R and (y, z) ∈ S, }. Definition 19 The 2-category S of sets and relations has as objects the class of sets and as morphisms the class of relations. The 2-cells are given by the inclusion partial order on the class of relations. Composition of morphisms is composition of relations and composition of 2-cells is given by composition of inclusions. The identity morphism on the set X is the diagonal Δ ={(x , x ) | x ∈ X }. The identity 2-cell on a relation R is the identity inclusion R ≤ R. op Definition 20 The transposition functor T : S → S is defined by T (X ) = X, T (R) = R ={(y, x ) | (x , y) ∈ R} T T T T and T (i ) = i , where i : R → S takes (y, x ) to (z,w) when (w, z) = i (x , y). Definition 21 A correspondence C : X  Y is a relation such that: 1. For every x ∈ X there exists y ∈ Y so that (x , y) ∈ C and 2. For every y ∈ Y there exists x ∈ X so that (x , y) ∈ C. Lemma 3 A relation C : X  Y is a correspondence if and only if there exists a relation D : Y  X so that Δ ≤ D ◦ C and Δ ≤ C ◦ D. X Y Proof By definition of a correspondence, for every x ∈ X, there exists y ∈ Y so that (x , y) ∈ C. This means that Δ ⊆ C ◦ C, where T T C ◦ C ={(x , z) ∈ X × X |∃ y ∈ Y : (x , y) ∈ C and (y, x ) ∈ C }. T T Reversing the roles of C and C we get the inclusion Δ ⊆ C ◦ C . Conversely, if C and D are relations with Δ ⊆ C ◦ D, then for every y ∈ Y , the element (y, y) is contained in C ◦ D. This means that there exists x ∈ X so that (x , y) ∈ C, and (y, x ) ∈ D. In particular for every y ∈ Y , there exists x ∈ X so that (x , y) ∈ C. Reversing the roles of C and D we get that for every x ∈ X there exists y ∈ Y so that (x , y) ∈ C. 123 Sparse Dowker nerves 21 8 The category of relations In this section, we introduce a novel 2-category of relations. We start by recalling Dowker’s definition of the nerve of a relation (called the complex K in Dowker 1952, Sect. 1). Definition 22 Let R ⊆ X × Y be a relation. The nerve of R is the simplicial complex NR ={finite σ ⊆ X |∃y ∈ Y with (x , y) ∈ R for all x ∈ σ }. Example 2 Let X be a space, and let Y be a cover of X. In particular every element y ∈ Y is a subset of X.Let R be the relation R ⊆ X ×Y consisting of pairs (x , y) with x ∈ y. A direct inspection reveals that the nerve of R is equal to the Borsuk Nerve of the cover Y . Definition 23 The 2-category R of relations has as objects the class of relations. A morphism C : R → R in R between relations R ⊆ X × Y and R ⊆ X × Y consists of a relation C ⊆ X × X such that for every σ ∈ NR,the set (NC )(σ ) ={x ∈ X | there exists x ∈ σ with (x , x ) ∈ C } is an element (NC )(σ ) ∈ NR of the nerve of R . In particular, (NC )(σ ) is finite and non-empty. The class of 2-cells in R is the class of inclusions C ⊆ C for morphisms 1 2 C , C ⊆ X × X . Composition in R is given by composition of relations. 1 2 Note that if C : R → R is a morphism in R, then NC is an order preserving function NC : NR → NR , and thus it induces a simplicial map NC : Δ(NR) → Δ(NR ) of order complexes. Given a simplicial complex K , the simplicial complex Δ(K ) is the barycentric subdivision of K . The geometric realizations of K and Δ(K ) are home- omorphic. In particular, they represent isomorphic objects in the homotopy category of simplicial complexes. Lemma 4 Let C , C : R → R be morphisms in R. If there exists a 2-cell α : C → 0 1 0 C , then the geometric realizations of the simplicial maps NC , NC : Δ(NR) → Δ(NR ) 0 1 are homotopic. Proof Let I be the partially ordered set I ={0 → 1}. Since C ⊆ C , we can define an order preserving map 0 1 C : I × NR → NR 123 22 M. Brun, N. Blaser by C (i,σ ) = NC (σ ) for i = 0, 1. On order complexes C induces a simplicial map Δ(C ) : Δ(I × NR) → Δ(NR ). As a consequence of Milnor (1981), Theorem 1 and Milnor (1981), Theorem 2 the geometric realization of Δ(I × NR) is homeomorphic to the product of the geometric realizations of Δ(I ) and Δ(NR). The geometric realization of Δ(I ) is homeomor- phic to the closed unit interval. Thus we have constructed a homotopy between the geoemtric realizations of NC and NC . 1 2 Definition 24 The nerve functor N : R → hCx is the functor taking a relation R the order complex Δ(NR) of its nerve and taking a morphism C : R → R in R to the morphism |NC|: |Δ(NR)|→|Δ(NR )| in hCx. Let us emphasize that if α : C → C is a 2-cell in R, then |NC |=|NC | in hCx. 1 2 1 2 9 Interleavings In this section, we set the concept of interleaving into the context of 2-categories. This material is well-known in the applied topology community. We write [0, ∞) for the set of non-negative real numbers and consider it as a partially ordered set. We also consider [0, ∞) as a category with object set [0, ∞) and with a unique morphism s → t if and only if s ≤ t. Definition 25 Let C be a 2-category. The category of filtered objects in C is the func- tor 2-category [[0, ∞), C].A filtered object in C is an object C :[0, ∞) → C of [[0, ∞), C], that is, C is a functor from [0, ∞) to C.A morphism f : C → C of filtered objects in C is a transformation. We will be so interested in the category of filtered objects in the 2-category of relations that we give a name to this particular 2-category. Definition 26 A filtered relation is a functor from [0, ∞) to R. We define the 2- category of filtered relations to be the 2-category [[0, ∞), R] of functors from [0, ∞) to R. Definition 27 Let C be a 2-category and let α:[0, ∞) →[0, ∞) be a translation function, that is, an order preserving function satisfying t ≤ α(t ) for all t ∈[0, ∞). 1. The pull-back functor α :[[0, ∞), C]→[[0, ∞), C] is the functor taking a fil- tered object C :[0, ∞) → C in C to the filtered object α C = C ◦ α. 2. The unit of the functor α :[[0, ∞), C]→[[0, ∞), C] is the natural transformation α : id → α defined by α (t ) = C (t ≤ α(t )) : C (t ) → α (C )(t ). ∗C 123 Sparse Dowker nerves 23 Definition 28 Let C and C be filtered objects in a 2-category C and let α, α :[0, ∞) → [0, ∞) be functors under the identity. 1. An (α, α )-interleaving between C and C is a pair (F , F ) of morphisms F : C → ∗    ∗ α C and F : C → α C in [[0, ∞), C] such that there exist 2-cells ∗   ∗ (α ◦ α) → (α F ) ◦ F and (α ◦ α ) → (α F ) ◦ F . ∗ ∗ 2. We say that C and C are (α, α )-interleaved if there exists an (α, α )-interleaving between C and C . The following results appear in Bubenik et al. (2015), Propositions 2.2.11 and 2.2.13. Lemma 5 (Functoriality) Let C and C be filtered objects in a 2-category C,let α, α :[0, ∞) →[0, ∞) be functors under the identity and let H : C → D be a functor of 2-categories. If C and C are (α, α )-interleaved, then the filtered objects HC and HC in D are (α, α )-interleaved. Lemma 6 (Triangle inequality) Let C, C and C be filtered objects in a 2-category C. If C and C are (α, α )-interleaved and C and C are (β, β )-interleaved, then C and C are (βα, α β )-interleaved. 10 Filtered relations and Dowker dissimilarities In this section, we introduce a novel 2-category of Dowker dissimilarities as a certain sub-2-category of the category of filtered relations. Definition 29 The filtered nerve functor is the functor N :[[0, ∞), R]→[[0, ∞), hTop] from the 2-category of filtered relations to the category of homotopy filtered spaces taking X :[0, ∞) → R to the composition X N [0, ∞) − → R − → hTop. From Lemma 5 we get: Corollary 3 If R and R are (α, α )-interleaved filtered relations, then N R and N R are (α, α )-interleaved filtered simplicial complexes. Given a Dowker dissimilarity Λ : L × W →[0, ∞] and t ∈[0, ∞) we consider Λ ={(l,w) ∈ L × W | Λ(l,w) < t } as an object of the category R of relations. Given s ≤ t in [0, ∞) we let Λ = Δ ={(l, l) l ∈ L}⊆ L × L s≤t L 123 24 M. Brun, N. Blaser considered as a morphism Λ : Λ → Λ in R. s≤t s t Definition 30 The filtered relation associated to a Dowker dissimilarity Λ : L × W → [0, ∞] is the functor Λ:[0, ∞) → R taking t ∈[0, ∞) to the relation Λ and taking s ≤ t in [0, ∞) to the morphism Λ t s≤t in R. Definition 31 Let Λ : L × W →[0, ∞] and Λ : L × W →[0, ∞] be Dowker dissimilarities. A morphism C : Λ → Λ of filtered relations is a morphism of Dowker dissimilarities if there exists a relation C ⊆ L × L so that C = C : Λ → Λ for t t every t ∈[0, ∞). Definition 32 The 2-category Dow of Dowker dissimilarities is the 2-category with Dowker dissimilarities as objects and morphisms of Dowker dissimilarities as mor- phisms. Given morphisms C , C : Λ → Λ of Dowker dissimilarities, we define the 1 2 set of 2-cells α : C → C in Dow by letting Dow(C , C ) =[[0, ∞), R](C , C ). 1 2 1 2 1 2 Definition 33 Let Λ : L ×W →[0, ∞] be a Dowker dissimilarity. The Dowker Nerve N Λ of Λ is the filtered nerve of the underlying filtered relation. Note that the Dowker Nerve is filtered by inclusion of sub-complexes, that is, if s ≤ t, then N Λ : N Λ → N Λ is an inclusion of simplicial complexes. s≤t s t Definition 34 Let Λ : L × W →[0, ∞] be a Dowker dissimilarity. Given l ∈ L and t > 0, the Λ-ball of radius t centred at l is B (l, t ) ={w ∈ W | Λ(l,w) < t }. Example 3 Let (M , d) be a metric space and L and W be subsets of M. Then the restriction Λ : L × W →[0, ∞] of d to L × W is a Dowker dissimilarity. The Dowker Nerve of Λ is the composite Λ N [0, ∞) − → R − → Cx taking t ∈[0, ∞) to {finite σ ⊆ L | there exists w ∈ W with d(l,w) < t for all l ∈ σ }. If L = W = M, then the Λ-ball of radius t centred at l is the usual open ball in M of ˇ ˇ radius t centred at l and the Dowker Nerve of Λ is equal to the Cech complex C(M ). Lemma 7 Let Λ : L × W →[0, ∞] be a Dowker dissimilarity. Given t > 0, the nerve N Λ is isomorphic to the Borsuk Nerve of the cover of the set B (l, t ) l∈L 123 Sparse Dowker nerves 25 by balls B (l, s) of radius s ≤ t centred at points in L. It is well-known that, in the above situation, the geometric realization of N Λ is homotopic to the geometric realization of the Borsuk Nerve of the cover of the set B (l, t ) l∈L by balls B (l, t ) of radius t centred at points in L. See e.g. Blaser and Brun (2018), Lemma 2.3. Corollary 3 gives: Corollary 4 If Λ : L × W →[0, ∞] and Λ : L × W →[0, ∞] are (α, α )- interleaved Dowker dissimilarities, then N Λ and N Λ are (α, α )-interleaved filtered simplicial complexes. Definition 35 Let Λ : L × W →[0, ∞] be a Dowker dissimilarity. The Rips complex of Λ is the filtered simplicial complex RΛ defined by (RΛ)(t ) ={finite σ ⊆ L | every τ ⊆ σ with |τ|≤ 2is in (N Λ)(t )}. Corollary 5 If Λ : L × W →[0, ∞] and Λ : L × W →[0, ∞] are (α, α )- interleaved Dowker dissimilarities, then RΛ and RΛ are (α, α )-interleaved filtered simplicial complexes. Proof Use Corollary 4 and the fact that the Rips complex depends functorially on the one skeleton of the Dowker Nerve. 11 Stability and interleaving distance The functoriality of interleaving implies that all functorial constructions are stable with respect to interleaving. In this section we relate interleaving distance of Dowker dissimilarities to Gromov–Hausdorff distance of Edwards (1975), Gromov (1981) and to the network distance defined in Chowdhury and Mémoli (2018). Definition 36 Let C and C be filtered objects in a 2-category C. 1. Given a, a ∈[0, ∞] we say that the filtered objects C and C are additively (a, a )-interleaved if they are (α, α )-interleaved for the functions α(t ) = a + t and α (t ) = a + t. 2. The interleaving distance of C and C is d (C , C ) = inf{a ∈[0, ∞] | C and C are additively int (a, a) − interleaved}, with the convention that inf ∅=∞. Definition 37 A non-negatively weighted network is a pair (X,ω ) of a set X and a weight function ω : X × X →[0, ∞). 123 26 M. Brun, N. Blaser Definition 38 Let ω : X × X →[0, ∞) and ω  : X × X →[0, ∞) be non- X X negatively weighted networks and let C ⊆ X × X .The distortion of C is dis(C ) = sup |ω (x , y) − ω (x , y )|. (x ,x ), (y,y )∈C Recall from Definition 21 that C ⊆ X × X is a correspondence if the projections of C on both X and X are surjective. Definition 39 Let ω : X × X →[0, ∞) and ω : X × X →[0, ∞) be non- negatively weighted networks and let R be the set of correspondences C ⊆ X × X . The network distance between X and X is d (X , X ) = inf dis(C ). 2 C ∈R The Stability Theorem (Chowdhury and Mémoli 2018, Proposition 15) for networks is a consequence of functoriality of interleaving distance, the Algebraic Stability The- orem for bottleneck distance (Chazal et al. 2009, Theorem 4.4) and the following result: Proposition 4 Let ω : X × X →[0, ∞) and ω : X × X →[0, ∞) be networks, and write Λ : X × X →[0, ∞] and Λ : X × X →[0, ∞] for the corresponding Dowker dissimilarities with Λ(x , y) = ω (x , y) and Λ (x , y ) = ω  (x , y ). Then d (Λ, Λ ) ≤ 2d (X , X ). int N Proof We have to show that d (Λ, Λ ) ≤ dis(C ) for every correspondence C ⊆ int X × X .Solet C ⊆ X × X be a correspondence and let a > dis(C ). By definition of dis(C ), for all (l, l ) and (w, w ) in C we have |ω (l,w) − ω (l ,w )| < a. Defining α:[0, ∞) →[0, ∞) by α(t ) = t + a, by symmetry, it suffices to show that C defines a morphism C : Λ → α Λ . That is, we have to show that if σ ∈ Λ , then (NC )(σ ) ∈ Λ . So suppose that α(t ) w ∈ X satisfies Λ(l,w) < t for all l ∈ σ . Since C is a correspondence we can pick w ∈ X so that (w, w ) ∈ C. By definition of NC, for every l ∈ (NC )(σ ), there exists l ∈ σ so that (l, l ) ∈ C. By definition of distortion distance this gives Λ (l ,w ) = ω  (l ,w )< a + ω (l,w) = a + Λ(l,w) < a + t = α(t ). X X 123 Sparse Dowker nerves 27 We conclude that σ ∈ N Λ implies (NC )(σ ) ∈ N Λ as desired. α(t ) The Stability Theorem (Chazal et al. 2014, Theorem 5.2) for metric spaces is a conse- quence of functoriality of interleaving distance, the Algebraic Stability Theorem for bottleneck distance (Chazal et al. 2009, Theorem 4.4) and the following result: Corollary 6 Let (M , d) and (M , d ) be metric spaces, and write Λ : M × M →[0, ∞] and Λ : M × M →[0, ∞] for the corresponding Dowker dissimilarities with Λ(p, q)=d(p, q) and Λ (p , q ) = d (p , q ). Then d (Λ, Λ ) ≤ 2d (M , M ). int GH Proof By Burago et al. (2001), Theorem 7.3.25 the Gromov–Hausdorff distance of the metric spaces (M , d) and (M , d ) agrees with their network distance when we consider them as non-negatively weighted networks. That is, d (M , M ) = d (M , M ).The GH N result now follows from Proposition 4. 12 Conclusion We generalize the Sparse Cech construction of Cavanna et al. (2015)toarbitrarymetric spaces and to a large class of Dowker dissimilarities. The abstract context of Dowker dissimilarities is well-suited for sparse nerve constructions. The concepts of filtered relations and strict 2-categories enable us to easily formulate and prove basic stability results. An implementation of the Sparse Dowker Nerve most similar to the Sparse Cech complex is available at GitHub Brun and Blaser (2018) together with a user tutorial. This implementation is not practical for analysis of high dimensional data. Other recent work on sparse complexes has focused on Euclidean space (Choud- hary et al. 2018) or the use of general simplicial maps (Dey et al. 2016; Boissonnat et al. 2018). It is possible that these considerations can be combined to obtain even smaller filtered nerves. In further work, we will improve this construction and we will make Sparse Dowker Nerves for Dowker dissimilarities that do not satisfy the triangle inequality. Acknowledgements This research was supported by the Research Council of Norway through Grant 248840. The authors have no conflicts of interest. We would like to thank the referees for helpful comments improving this paper. Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 Interna- tional License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made. 123 28 M. Brun, N. Blaser References Blumberg, A.J., Lesnick, M.: Universality of the homotopy interleaving distance (2017). https://arxiv.org/ abs/1705.01690 Boissonnat, J.-D., Pritam, S., Pareek, D. Strong Collapse for Persistence (2018). ArXiv e-prints. arXiv:1809.10945 Blaser, N., Brun, M.: Divisive cover. Math. Comput. Sci. (2018). https://doi.org/10.1007/s11786-018-0352- Brun, M., Blaser, N.: Sparse-Dowker-nerves (2018). https://github.com/mbr085/Sparse-Dowker-Nerves Bubenik, P., de Silva, V., Scott, J.: Metrics for generalized persistence modules. Found. Comput. Math. 15(6), 1501–1531 (2015) Buchet, M., Chazal, F., Oudot, S.Y., Sheehy, D.: Efficient and robust persistent homology for measures. Comput. Geom.: Theory Appl. 58, 70–96 (2016) Burago, D., Burago, Y., Ivanov, S.: A Course in Metric Geometry. Graduate Studies in Mathematics, vol. 33. American Mathematical Society, Providence (2001) Carlsson, G., Ishkhanov, T., de Silva, V., Zomorodian, A.: On the local behavior of spaces of natural images. Int. J. Comput. Vis. 76(1), 1–12 (2008) Cavanna, N.J., Jahanseir, M., Sheehy, D.R.: A geometric perspective on sparse filtrations. CoRR, arXiv:1506.03797 (2015) Chazal, F., Cohen-Steiner, D., Glisse, M., Guibas, L., Oudot, S.: Proximity of persistence modules and their diagrams. In: SoCG, pp. 7–246 (2009) Chazal, F., Cohen-Steiner, D., Guibas, L.J., Mémoli, F., Oudot, S.Y.: Gromov–hausdorff stable signatures for shapes using persistence. In: Proceedings of the Symposium on Geometry Processing, SGP ’09, pp, 1393–1403. Eurographics Association, Aire-la-Ville (2009) Chazal, F., de Silva, V., Oudot, S.: Persistence stability for geometric complexes. Geom. Dedicata 173, 193–214 (2014) Choudhary, A., Kerber, M., Raghvendra, S.: Improved topological approximations by digitization. CoRR, arXiv:1812.04966 (2018) Chowdhury, S., Mémoli, F.: A functorial Dowker theorem and persistent homology of asymmetric networks (2018). ArXiv e-prints. arXiv:1608.05432 Dey, T.K., Shi, D., Wang, Y.: SimBa: an efficient tool for approximating Rips-filtration persistence via simplicial batch-collapse. In: 24th Annual European Symposium on Algorithms, vol. 57 of LIPIcs. Leibniz Int. Proc. Inform, Art. No. 35, 16 (2016) Dowker, C.H.: Homology groups of relations. Ann. Math. 2(56), 84–95 (1952) Edwards, D.A.: The structure of superspace. In: Studies in Topology. Proceeding Conference, University of North Carolina, Charlotte, N. C., 1974; dedicated to Mathematics Section Polish Academy of Sciences, pp. 121–133. Academic Press, New York (1975) Embrechts, P., Hofert, M.: A note on generalized inverses. Math. Methods Oper. Res. 77(3), 423–432 (2013) Gromov, M.: Groups of polynomial growth and expanding maps. Inst. Hautes Études Sci. Publ. Math. 53, 53–73 (1981) Lawvere, F.W.: Metric spaces, generalized logic, and closed categories. Ann. Math. (2) 65, 357–362 (1957) Leinster, T.: Basic bicategories (1998) Milnor, J.: The geometric realization of a semi-simplicial complex. Inst. Hautes Études Sci. Publ. Math. 53, 53–73 (1981) Oudot, S.Y.: Persistence Theory: From Quiver Representations to Data Analysis. Mathematical Surveys and Monographs, vol. 209. American Mathematical Society, Providence (2015) Sheehy, D.R.: Linear-size approximations to the Vietoris–Rips filtration. Discrete Comput. Geom. 49(4), 778–796 (2013) Spanier, E.H.: Algebraic Topology. Springer, New York (1966). Corrected reprint of the 1966 original Zomorodian, A.: Topological data analysis. In Advances in Applied and Computational Topology. Pro- ceedings of Symposia in Applied Mathematics, vol. 70, pp. 1–39. American Mathematical Society, Providence (2012) 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

Sparse Dowker nerves

Download PDF
28 pages

Loading next page...
 
/lp/springer-journals/sparse-dowker-nerves-N60hzZVV3y
Publisher
Springer Journals
Copyright
Copyright © 2019 by The Author(s)
Subject
Mathematics; Algebraic Topology; Computational Science and Engineering; Mathematical and Computational Biology
ISSN
2367-1726
eISSN
2367-1734
DOI
10.1007/s41468-019-00028-9
Publisher site
See Article on Publisher Site

Abstract

We propose sparse versions of filtered simplicial complexes used to compute persis- tent homology of point clouds and of networks. In particular, we extend the Sparse Cech Complex of Cavanna et al. (A geometric perspective on sparse filtrations. CoRR, arXiv:1506.03797, 2015) from point clouds in convex metric spaces to point clouds in arbitrary metric spaces. Along the way we formulate interleaving in terms of strict 2-categories, and we introduce the concept of Dowker dissimilarities that can be con- sidered as a common generalization of metric spaces and networks. Keywords Sparse nerve · Dowker theorem · Persistent homology · Cech complex · Rips complex Mathematics Subject Classification 55N05 · 55N99 · 55U10 · 55U99 1 Introduction This paper is the result of an attempt to obtain the interleaving guarantee for the sparse Cech complex of Cavanna et al. (2015) without using the Nerve Theorem. The rationale for this was to generalize the result from convex metric spaces to arbitrary metric spaces. We have not been able to show that the constructions of Sheehy (2013) or Cavanna et al. (2015) are interleaved with the Cech complex in arbitrary metric spaces. However, changing the construction slightly, we obtain a sub-complex of the Cech complex that is interleaved in a similar way. When applied to point clouds in a convex metric space this sub-complex is homotopic to the construction of Cavanna et al. (2015). The above constructions are two examples of general constructions presented in the body of our paper. B Morten Brun morten.brun@uib.no Nello Blaser nello.blaser@uib.no Department of Mathematics, University of Bergen, Bergen, Norway 123 2 M. Brun, N. Blaser The search for a more general version of the sparse Cech complex led us to study both different versions of filtered covers and extended metrics. We discovered that these concepts are instances of filtered relations given by functions of the form Λ : L × W →[0, ∞] from the product of two sets L and W to the interval [0, ∞]. Here we think of L as a set of landmark points and W as a set of witness points. Given t ∈[0, ∞), the relation Λ at filtration level t is Λ ={(l,w) ∈ L × W | Λ(l,w) < t }. Dowker (1952) observed that a relation R ⊆ L × W gives a cover (R(l)) of the l∈L set R ={w ∈ W | there exists l ∈ L with (l,w) ∈ R} with R(l) ={w ∈ W | (l,w) ∈ R}. The Dowker complex of the relation R is the Borsuk Nerve of this cover. The Dowker Homology Duality Theorem (Dowker 1952, Theorem 1) states that the Dowker com- plexes of R and the transposed relation R ={(w, l) | (l,w) ∈ R}⊆ W × L have isomorphic homology. In Chowdhury and Mémoli (2018), Chowdhury and Mémoli have sharpened the Dowker Homology Duality Theorem to a Dowker Homo- topy Duality Theorem stating that the Dowker complexes of R and R are homotopy equivalent after geometric realization. That result is a central ingredient in this paper. In honor of Dowker we name functions Λ : L × W →[0, ∞] Dowker dissimilar- ities. Forming the Dowker complexes of the relations Λ for t ∈[0, ∞) we obtain a filtered simplicial complex, the Dowker Nerve N Λ of Λ, with N Λ equal to the Dowker complex of Λ . The main result of our work is Theorem 2 on sparsification of Dowker nerves. Here we formulate it in the context of a finite set P contained in a metric space (M , d). Let p ,...,, p be a farthest point sampling of P with insertion radii λ ,...λ . 0 n 0 n That is, p ∈ P is arbitrary, λ =∞ and for each 0 < k ≤ n, the point p ∈ P 0 0 k is of maximal distance to p ,..., p , and this distance is λ .Let ε> 0 and let 0 k−1 k Λ : P × M →[0, ∞] be the Dowker dissimilarity given by the metric d, that is, Λ(p,w) = d(p,w). Then the Dowker Nerve N Λ is equal to the relative Cech complex C(P, M ) of P in M given by the Borsuk Nerve of all balls in M centred at points in P. 123 Sparse Dowker nerves 3 Let [n]={0,..., n} and let ϕ:[n]→[n] be a function with ϕ(0) = 0 and ϕ(k)< k for k > 0 and d(p , p ) + (ε + 1)λ /ε ≤ (ε + 1)λ /ε (1) k ϕ(k) k ϕ(k) for k = 1,..., n. The geometric idea behind this formula is that the ball centred at (ε+1)λ (ε+1)λ ϕ(k) p of radius is contained in the ball centred at p of radius , and k ϕ(k) ε ε (ε+1)λ ϕ(k) therefore at filtration levels greater than this ball can be omitted without changing the homotopy type of the nerve of the cover (Fig. 1). The Sparse Dowker Nerve of Λ is the filtered sub-complex N(Λ,ϕ,(ε + 1)λ/ε) of N Λ filtered by letting N(Λ,ϕ,(ε + 1)λ/ε)) consist of subsets σ ⊆ P such that there exists w ∈ M with d(p ,w) < min{t,(ε + 1)λ /ε, (ε + 1)λ /ε} k k ϕ(l) for every k, l ∈ σ . The geometric interpretation of this formula is firstly that balls around p are truncated at radius (ε + 1)λ /ε, that is, when they reach this radius they k k stop growing. Secondly, the nerve is restricted in the sense that p is not contributing to simplices of radius greater than (ε + 1)λ /ε. In the geometric description of ϕ(k) Cavanna et al. (2015), cones at p are truncated at width (ε + 1)λ /ε and their tops k k are cut off at height (ε + 1) λ /ε. Theorem 1 The Sparse Dowker Nerve N(Λ,ϕ,(ε + 1)λ/ε) is multiplicatively ˇ ˇ (1, 1 + ε)-interleaved with the relative Cech complex C(P, M ) of P in M. Explicitly, there are maps f : N Λ → N(Λ,ϕ,(ε + 1)λ/ε) so that for the t t (1+ε)t inclusion maps g : N(Λ,ϕ,(ε + 1)λ/ε) → N Λ , the maps f g and g f are t t t t t (1+ε)t t homotopic to the inclusion of the space of level t into the space of level (1 + ε)t of the filtered simplicial complexes N(Λ,ϕ,(ε + 1)λ/ε) and N Λ respectively. For M = R the Sparse Dowker Nerve is closely related to the Sparse Cech Complex of Cavanna et al. (2015). We have implemented both constructions and made them available at GitHub (Brun and Blaser 2018). We also provide a tutorial that can be accessed from the same GitHub repository. It turned out that the two constructions are of similar size. Chazal et al. (2014) witness complexes and Cech complexes are both instances of Dowker dissimilarities. The weighted Cech complex in (Buchet et al. 2016, Defini- tion 5.1) is also an instance of a Dowker complex. Also the filtered clique complex of a finite weighted undirected simple graph G = (V ,w), where w is a function w : G × G →[0, ∞] is an instance of a Dowker nerve: let P(V ) be the set of subsets of V and define diam(X ) if x ∈ X Λ : V × P(V ) →[0, ∞],(x , X ) → ∞ otherwise, where diam(X ) = max  w(x , x ). Then the Dowker Nerve of Λ is equal to the x ,x ∈X filtered clique complex of G. For disjoint sets L and W a Dowker dissimilarity Λ : L × W →[0, ∞] is the same thing as a weighted simple bipartite graph. On the other hand, a Dowker dissimilarity 123 4 M. Brun, N. Blaser (1 +ε)λ d(p , p ) k ϕ(k) p p k ϕ(k) Fig. 1 Sparse Dowker nerves. Let P ={ p ,..., p } be a finite subset of a metric space M , d obtained by farthest point sampling with insertion radii λ ,...,λ and let ϕ:[n]→[n] be a function satisfying 0 n (ε+1) the inequality (1). Around each point p ∈ X, we draw a truncated cone with width λ and height k k (ε+1) d(p , p )+ λ . The figure shows that the projection of the cone with center p onto M is contained k ϕ(k) k k in the projection of the cone with center p ϕ(k) of the form Λ : X × X →[0, ∞] is the same thing as a weighted directed graph with no multiple directed edges. Chowdhury and Mémoli (2018), call Dowker dissimilari- ties of this form weighted networks, and study their Dowker nerves thoroughly under the name Dowker complexes. In particular, they show that the persistent homology of the Dowker Nerve of a network is sensitive to the direction its edges. For example, for the networks A and B in Fig. 2, with self-loops of weight 0, the Dowker Nerve of network A is contractible while the Dowker Nerve of network B is homotopic to a circle at all filtration levels. Chowdhury and Mémoli also formulate a stability result for homology of Dowker nerves (Chowdhury and Mémoli 2018). We formulate interleaving of Dowker dissimilarities in such a way that their network distance is bounded below by our interleaving distance. Together with functoriality for interleav- ing distance and the Algebraic Stability Theorem (Chazal et al. 2009) this implies the (1 +ε)λ ϕ(k) (1 +ε)λ d(p , p ) + k ϕ(k) ε Sparse Dowker nerves 5 ⎛ ⎞ ⎛ ⎞ 1 1 ⎜ ⎟ ⎜ ⎟ ⎜ 0 0 ⎟ ⎜ 0 0 ⎟ ⎜ ⎟ ⎜ ⎟ A = ⎜ ⎟ B = ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ 02 02 ⎝ ⎠ ⎝ ⎠ Fig. 2 The Dowker Nerve of network A is contractible while the Dowker Nerve of network B is homotopic to a circle stability result of Chowdhury and Mémoli (2018). In the context of metric spaces, this Stability Theorem is contained in Chazal et al. (2014). Imposing conditions on a Dowker dissimilarity of the form Λ : X × X →[0, ∞], we arrive at concepts of independent interest. Most importantly, (X,Λ) is a metric space if and only if Λ satisfies Finiteness Λ(x , y)< ∞ for all x , y ∈ X. Triangle inequality Λ(x , z) ≤ Λ(x , y) + Λ(y, z) for x , y, x ∈ X. Identity of indiscernibles d(x , y) = 0 if and only if x = y. Symmetry d(x , y) = d(y, x ) for all x , y ∈ X. Removing some of the above conditions on Λ leads to various generalizations of metric spaces. In particular, the situation where Λ only is required to satisfy the triangle inequality has been studied by Lawvere (1957). He noticed that [0, ∞] is a closed symmetric monoidal category and that when the triangle inequality holds, then Λ gives X the structure of a category enriched over [0, ∞]. Guided by the Strong Functorial Dowker Theorem (Chowdhury and Mémoli 2018, Theorem 3) we have chosen to work with interleavings in the homotopy category instead of on the level of homology groups. We leave it for further investigation to decide if the Functorial Dowker Theorem can be extended to homotopy interleavings in the sense of Blumberg and Lesnick (2017). We extend the usual notion of interleaving between [0, ∞)-filtered objects in two ways. Firstly, we consider interleavings in 2-categories. We were led to do this because Dowker dissimilarities form a 2-category, and the proof of the Stability The- orem is streamlined by working in this generality. Secondly, following Bubenik et al. (2015), we allow interleaving with respect to order preserving functions of the form α:[0, ∞) →[0, ∞) satisfying t ≤ α(t ) for all t. In this context, additive interleav- ing corresponds to functions of the form α(t ) = t + a and multiplicative interleaving corresponds to functions of the form α(t ) = ct. After setting terminology and notation, the proof of our main result, Theorem 2,is a quite simple application of the functorial Dowker Theorem. It consists of two parts. First, we truncate the Dowker dissimilarity associated to a metric by replacing certain distances by infinity and show that the truncated Dowker dissimilarity is interleaved with the original Dowker dissimilarity. At that point we use the functorial Dowker 123 6 M. Brun, N. Blaser Theorem. Second, we give conditions that allow us to sparsify the Dowker Nerve of the truncated Dowker dissimilarity without changing the filtered homotopy type. The paper is organized as follows: Sect. 2 presents our main result, Theorem 2.We also show how Theorem 1 is a consequence of Theorem 2 and how the Sparse Cech complex (Cavanna et al. 2015) fits into this context. Section 3 shows that, under certain conditions, when some of the values Λ(l,w) in a Dowker dissimilarity are set to infin- ity, the homotopy type of the Dowker Nerve is only changed up to a certain interleaving. This is the first step in our proof of Theorem 2. In Sect. 4, we give a criterion ensuring that a certain sub-complex is homotopy equivalent to the Dowker Nerve of a Dowker dissimilarity. In Sect. 5, we present the homotopy category of simplicial complexes. In Sect. 6, we recollect basic terminology about 2-categories. The main motivation for going to this level of generality is that interleaving distance in the 2-category Dow of Dowker dissimilarities defined in Definition 32 generalizes network distance from Chowdhury and Mémoli (2018). In Sect. 7, we introduce the 2-category of sets and relations. Section 8 uses the Dowker Nerve construction to define a 2-category with relations as objects. Section 9 introduces interleavings in 2-categories. In Sect. 10, we define the 2-category of Dowker dissimilarities. In Sect. 11, we relate interleaving distance of Dowker dissimilarities to Gromov–Hausdorff distance of metric spaces. We finish with some concluding remarks in Sect. 12. 2 Sparse nerves of truncated Dowker dissimilarities In this section, we state and motivate our main results, postponing proofs to later sections. Definition 1 A Dowker dissimilarity Λ consists of two sets L and W and a function Λ : L × W →[0, ∞].Given t ∈[0, ∞),welet Λ ={(l,w) ∈ L × W | Λ(l,w) < t }. The Dowker Nerve of Λ is the filtered simplicial complex N Λ = (N Λ ) with t t ≥0 N Λ ={finite σ ⊆ L | there exists w ∈ W with Λ(l,w) < t for all l ∈ σ }. The zero set of Λ is L ={l ∈ L | there exists w ∈ W with Λ(l,w) = 0}. The triangle inequality is central in the work of Cavanna et al. (2015), and it will also play a central role for us. For Dowker dissimilarities we need extra structure in order to formulate the triangle inequality. Definition 2 A Dowker dissimilarity Λ : L × W →[0, ∞] satisfies the triangle inequality if the following holds: 1. For every w ∈ W there exists l ∈ L with Λ(l,w) = 0. 2. For all (l,w) ∈ L × W with Λ(l,w) = 0 and all (l ,w ) ∈ L × W,the triangle inequality 123 Sparse Dowker nerves 7 Λ(l ,w ) ≤ Λ(l ,w) + Λ(l,w ) holds. Note that if Λ satisfies the triangle inequality and if both Λ(l,w) = 0 and Λ(l ,w) = 0, then for every w ∈ W the triangle inequality implies that Λ(l ,w ) ≤ Λ(l ,w) + Λ(l,w ) = Λ(l,w ), and thus by symmetry Λ(l ,w ) = Λ(l,w ). Also note that if Λ is actually a metric Λ : L × L →[0, ∞], then it satisfies the triangle inequality in the above sense. Unfortunately the Sparse Dowker Nerve presented in this paper needs a Dowker dissimilarity satisfying the triangle inequality as input. There are many interesting examples of Dowker dissimilarities where it is not satisfied. For example the triangle inequality is rarely satisfied for weighted networks or Bregman divergences. Typical examples of Dowker dissimilarities satisfying the triangle inequality are quasi-metrics and pseudo-metrics. The following concept of insertion pairs is the crucial ingredient in Sect. 3 where we treat interleaving of truncated Dowker Nerves. Definition 3 An insertion pair for Λ consists of a pair ( f ,λ) of functions f : W × [0, ∞] → W and λ : W →[0, ∞] with the property that for every (l,w) ∈ L × W with Λ(l,w) = 0 and every t ≥ 0 the inequalities Λ(l, f (w, t )) ≤ t <λ( f (w, t )) are satisfied. Insertion pairs generalize farthest point samples. Let d : W × W →[0, ∞] beametric and w ,...,w be a farthest point sample with insertion times λ ,...,λ . Then the 0 n 0 n functions λ(w ) = λ and f (w, t ) = argmin {d(w, w ) | λ > t } are an insertion i i i i w ∈W pair. For Dowker dissimilarities of the form Λ : L ×[n]→[0, ∞] satisfying the triangle inequality the following definition gives an example of an insertion pair for Λ.Here and throughout this paper we will use the notation [n]={0,..., n}. Definition 4 Let Λ : L ×[n]→[0, ∞] be a Dowker dissimilarity satisfying the triangle inequality. The canonical insertion function for Λ : L ×[n]→[0, ∞] is the function λ :[n]→[0, ∞] defined as ∞ if w = 0 λ (w) = sup inf Λ(l,w ) if w> 0. w ∈[w−1] l∈L The canonical insertion pair for Λ is the pair ( f ,λ ) where the function Λ Λ f :[n]×[0, ∞] → [n] 123 8 M. Brun, N. Blaser is defined as follows: Given w ∈[n] and t ≥ 0, pick l ∈ L with Λ(l,w) = 0 and define f (w, t ) = min{w ∈[n]| Λ(l,w ) ≤ t }. The definition of f (w, t ) is independent of the choise of l and the set {w ∈[n]| Λ(l,w ) ≤ t } is non-empty because sup inf Λ(l,w ) = 0 ≤ t . w ∈[n] l∈L Also, by construction Λ(l,w) = 0 implies that Λ(l, f (w, t )) ≤ t <λ ( f (w, t )). Λ Λ Λ The following lemma summarizes this discussion. Lemma 1 Let Λ : L ×[n]→[0, ∞] be a Dowker dissimilarity satisfying the triangle inequality. Then the canonical insertion pair ( f ,λ ) is an insertion pair for Λ. Λ Λ The Sparse Cech Nerve of Cavanna et al. (2015) is constructed with a positive number ε as a parameter controlling its quality in the sense that the Sparse Cech Nerve is multiplicatively (1, 1 + ε)-interleaved with the Cech Nerve. The following definition allows us to construct Sparse Dowker Nerves that are (id,α)-interleaved with the Dowker Nerve for a large class of translation functions α:[0, ∞) →[0, ∞).Here a translation function is an order-preserving function α:[0, ∞) →[0, ∞) with the property that α(t ) ≥ t for every t ∈[0, ∞). In the following definition, we use the generalized inverse of order preserving functions (see e.g. Embrechts and Hofert 2013 for more details). Definition 5 Let α:[0, ∞] → [0, ∞] be order preserving with lim α(t ) =∞. t →∞ The generalized inverse function α :[0, ∞] → [0, ∞] is the order preserving func- tion α (s) = inf{t ∈[0, ∞] | α(t ) ≥ s}. The above definition can be summarized as follows: α (s) ≤ t ⇐⇒ s ≤ α(t ). 123 Sparse Dowker nerves 9 Definition 6 Let β :[0, ∞] → [0, ∞] be an order preserving function. The translation function associated to β is the function α:[0, ∞] → [0, ∞] defined by α(t ) = t + β(t ). The first step in the construction of a Sparse Dowker Nerve of a Dowker dissimilarity Λ, is to truncate Λ by replacing some of the values Λ(l,w) by ∞. In the Euclidean case, this means that we truncate cones by only allowing them to grow to a certain width, as illustrated in Fig. 1. With the objective of the Sparse Dowker Nerve being (α, id)-interleaved with the Dowker Nerve in the sense of Definition 28.Wedothis as follows: Definition 7 Let Λ : L ×W →[0, ∞] be a Dowker dissimilarity satisfying the triangle inequality and let ( f ,λ) be an insertion pair for Λ.Let β :[0, ∞] → [0, ∞] be an order preserving function with lim β(t ) =∞ and let α be the translation function t →∞ associated to β.The β-truncation function λ : W → W associated to λ is the function λ (w) = αβ (λ(w)). (λ,β) The (λ, β)-truncation of Λ is the Dowker dissimilarity Λ : L × W →[0, ∞] defined by Λ(l,w) if Λ(l,w) ≤ λ (w) and β(0) ≤ λ(w) (λ,β) Λ (l,w) = ∞ otherwise. Example 1 Let Λ : L ×[n]→[0, ∞] be a Dowker dissimilarity satisfying the triangle inequality. Given a ≥ 0 and ε> 0, we define β(t ) = a + εt for t ∈[0, ∞].The translation function α associated to β is the affine function α(t ) = a + (1 + ε)t, and the function αβ is given by the formula (1+ε)t −a if t ≥ a/(1 + ε) (αβ )(t ) = 0 otherwise. In Theorem 2 below we state that persistent homology of the (λ, β)-truncation of Λ is (α, id)-interleaved with the persistent homolgoy of Λ. The last step in the construction of a Sparse Dowker Nerve of a Dowker dis- similarity Λ, is to restrict the Dowker Nerve of its transposed Dowker dissimilarity T T Λ : W × L →[0, ∞] given by Λ (w, l) = Λ(l,w). By restricting we mean that w ∈ W is not contributing to simplices of radius greater than a certain threshold. The purpose of the following definition is to give such a threshold. Definition 8 Let Λ : L ×[n]→[0, ∞] be a Dowker dissimilarity and let λ:[n]→ [0, ∞] be a function with λ(w) < ∞ for w> 0 and λ(0) =∞.The parent function for Λ with respect to λ is the function ϕ:[n]→[n] 123 10 M. Brun, N. Blaser defined by ϕ(0) = 0 and ϕ(w) = argmin{λ(w ) | λ(w )>λ(w) and for all l ∈ L with Λ(l,w) < λ(w), we have Λ(l,w )<λ(w )} for w> 0in [n]. Note that if w> 0, then λ(w) < ∞ and λ(w) < λ(ϕ(w)). Also note that the parent function is not necessarily uniquely defined because there may be more than one w with λ(w ) minimal under the condition that both λ(w )>λ(w) and Λ(l,w) < λ(w) implies Λ(l,w )<λ(w ). We now give the last ingredient in the construction of the Sparse Dowker Nerve. Definition 9 Let Γ :[n]× W →[0, ∞] be a Dowker dissimilarity. Given functions ϕ:[n]→[n] and λ:[n]→[0, ∞],the sparse nerve of Γ with respect to λ and ϕ is the filtered simplicial complex N(Γ ,ϕ,λ) with N(Γ ,ϕ,λ)(t ) consisting of all σ ⊆[n] so that there exists w ∈ W with Γ(l,w) < min(t,λ(l), λ(ϕ(l ))) for all l, l ∈ σ. In abbreviated form the simplicial complex N(Γ ,ϕ,λ)(t ) is {σ ⊆[n]|∃w ∈ W : Γ(l,w) < min(t,λ(l), λ(ϕ(l ))) for all l, l ∈ σ }. We are ready to state our main result about the Sparse Dowker Nerve: Theorem 2 Let Λ : L ×[n]→[0, ∞] be a Dowker dissimilarity satisfying the triangle inequality and with Λ(l, 0)< ∞ for every l ∈ L. Let β :[0, ∞] → [0, ∞] be an order preserving function with β(t)< ∞ for t < ∞ and lim β(t ) =∞ and let t →∞ λ be the β-truncation function associated to the canonical insertion function for Λ. (λ ,β) T If we let ϕ be the parent function for Λ with respect to λ and write Γ = (Λ ) , T T then the Dowker Nerve N Λ of Λ is (α, id)-interleaved with the filtered simplicial complex N(Γ ,ϕ,λ ). Proof We show the interleaving in four steps FDT FDT P3 P2 T (λ ,β) N Λ  N Λ −→ N (Λ )  N Γ  N(Γ ,ϕ,λ ), where Proposition 2 (P2) gives the interleaving and the homotopy equivalences are given by the Strong Functorial Dowker Theorem (Chowdhury and Mémoli 2018, Theorem 3) (FDT) and Proposition 3 (P3). More precisely, the functorial Dowker Theorem (Chowdhury and Mémoli 2018, Theorem 3) implies that the filtered simplicial complexes N Λ and N Λ are homotopy equivalent. By construction in Definitions 6 and 7,if Γ(k, l)< ∞ then Γ(k, l)< λ (k). Therefore, by Proposition 3 the filtered simplicial complexes N(Γ ,ϕ,λ ) and β β N Γ are homotopy equivalent. The Strong Functorial Dowker Theorem (Chowdhury and Mémoli 2018, Theorem 3) implies that the filtered simplicial complexes N Γ and 123 Sparse Dowker nerves 11 (λ ,β) N (Λ ) are homotopy equivalent. By Lemma 1 the pair ( f ,λ ) is an insertion Λ Λ (λ ,β) pair for Λ, so by Proposition 2 the filtered simplicial complexes N Λ and N (Λ ) are (α, id)-interleaved. Remark 1 The Dowker Theorem (Dowker 1952, Theorem 1a) implies that the persis- tent homology of N Λ is isomorphic to the persistent homology of N Λ and that the (λ ,β) persistent homology of N Γ is isomorphic to the persistent homology of N (Λ ). Thus, if we are only interested in persistent homology, we do not need the Functorial Dowker Theorem. Corollary 1 Let Λ : L ×[n]→[0, ∞] be a Dowker dissimilarity satisfying the triangle inequality and with Λ(l, 0)< ∞ for every l ∈ L and let β :[0, ∞] → [0, ∞] be the function β(t ) = εt and let α:[0, ∞] → [0, ∞] be the translation function α(t ) = (ε + 1)t associated to β.For λ the β-truncation function associated to the canonical insertion function of Λ and ϕ the parent function for Λ with respect to λ , the Dowker Nerve T T N Λ of Λ is (α, id)-interleaved with the filtered simplicial complex (λ ,β) T N ((Λ ) ,ϕ,λ ). Specializing even further, we obtain a variation of the Sparse Cech complex of Cavanna et al. (2015). Recall that the Hausdorff distance of a metric space L = (L, d) and a subset P of L is d (L, P) = sup inf d(l, p). p∈P l∈L In the following result we have in mind the situation where L is a compact sub- manifold of Euclidean space R with convex hull M and P is a sample of points from ˇ ˇ ˇ L. Note that in this situation the relative Cech complexes C(L, M ) and C(L, R ) are homotopy equivalent. Corollary 2 Let (M , d) be a metric space, let L ⊆ M be a compact subset, let P be a finite subset of L and let [n] − → P be a bijection. Let Λ : M ×[n]→[0, ∞] be the function Λ(x,w) = d(x , p ), wherewewrite p = p(w). Let ε> 0 and let β :[0, ∞] → [0, ∞] be the function β(t ) = εt with associated translation function α(t ) = (ε+1)t. For λ the β-truncation function associated to the canonical insertion function of Λ and ϕ the parent function 123 12 M. Brun, N. Blaser T T for Λ with respect to λ , the Dowker Nerve N Λ of Λ is (α, id)-interleaved with the filtered simplicial complex (λ ,β) T N ((Λ ) ,ϕ,λ ). Moreover, the Dowker Nerve of N Λ is additively (0, d (L, P))-interleaved with the relative Cech complex C(L, M ) consisting of all balls in M with centers in L. ˇ ˇ ˇ Sometimes we refer to the relative Cech complex C(L, M ) as the ambient Cech com- ˇ ˇ ˇ plex and to the relative Cech complex C(L, L) as the intrinsic Cech complex of L. Proof Corollary 1 gives that N Λ is (α, id)-interleaved with (λ ,β) T N ((Λ ) ,ϕ,λ ). For the second statement, first note that N Λ is homotopy equivalent to the relative ˇ ˇ ˇ ˇ Cech complex C(P, M ). Thus it suffices to show that the Cech complexes C(P, M ) and C(L, M ) are additively (0, d (L, P))-interleaved. Since P ⊆ L, for every t ∈[0, ∞), ˇ ˇ there is an inclusion ι : C (P, M ) → C (L, M ).Let f : L → P be a function with t t t d(l, f (l)) ≤ d (L, P) for every l ∈ L. The triangle inequality implies that f induces ˇ ˇ a morphism f : C (L, M ) ⊆ C (L, M ). By construction the composites f ι t t t +d (L,P) t t and ι f are contiguous to the respective identity maps, and thus their geo- t +d (L,P) t metric realizations are homotopic Spanier (1966). Finally, we show that the Sparse Cech complex of Cavanna et al. (2015) is an instance of a Sparse Dowker Nerve. We suspect that Cavanna et al.’s construction performed to Dowker dissimilarities is homotopy equivalent to the Sparse Dowker Nerve but we have not been able to prove this. However, the following result, together with the first part of the proof of (Cavanna et al. 2015, Theorem 5) implies that the Cavanna et al.’s Sparse Cech Nerve is homotopy equivalent to the Sparse Dowker Nerve for the Dowker dissimilarities in the following proposition. d d Proposition 1 Let d be a convex metric on R and let P be a finite subset of R together with a greedy order [n] − → P. Let the function Λ : R ×[n]→[0, ∞] be given by Λ(l,w) = d(l, p ), wherewewrite p = p(w). Let ε> 0 and let β:[0, ∞] → [0, ∞] and α:[0, ∞] → [0, ∞] be the functions β(t ) = εt and α(t ) = (1 + ε)t. Let λ be the canonical insertion function for Λ and let λ = ((1 + ε) /ε)λ . Then the filtered simplicial complex (λ ,β) T N ((Λ ) , id,λ)(t ) is isomorphic to the filtered simplicial complex  C (ε ) where ε >ε C (ε ) = S (ε ) s<t 123 Sparse Dowker nerves 13 and S(ε ) ={S (ε )} is the sparse Cech complex constructed in (Cavanna et al. t ≥0 2015, Sect. 4) for the parameter ε . Proof A subset σ ⊆[n] is in (λ ,β) T N ((Λ ) ) if and only if there exists w ∈ R so that for all l ∈ σ we have d(p ,w) < t and d(p ,w) < λ (l)(1 + ε)/ε. l l Λ Moreover T (λ ,β) T σ ∈ N (((Λ ) ) , id,λ)(t ) if and only if there exists w ∈ R so that for all k, l ∈ σ we have d(p ,w) < t and d(p ,w) < λ (k)(1 + ε)/ε and d(p ,w) < λ (l)(1 + ε) /ε. k Λ k Λ s  d On the other hand, σ ∈ S (ε ) if and only if there exists s < t and w ∈ R so s<t that w ∈ b (s) for all l ∈ σ . By the definition of b (s) in Cavanna et al. (2015), Sect. l l 3, this is the case if and only if s < t and s ≤ λ (l)(1 + ε ) /ε and d(p ,w) ≤ min(s,λ (l)(1 + ε )/ε ) Λ l Λ t d for every l ∈ σ . We conclude that σ ∈ S if and only if there exists w ∈ R satisfying d(p ,w) < t and d(p ,w) ≤ λ (l)(1 + ε )/ε and d(p ,w) < λ (l)(1 + ε ) /ε . l Λ k Λ for all k, l ∈ σ . We have not performed any complexity analysis of Sparse Dowker Nerves. Instead we have made proof-of-concept implementations of both the Sparse Cech Complex of Cavanna et al. (2015) described in Proposition 1 and the Sparse Dowker Nerve described in Corollary 2. These implementations come with the same interleaving guarantees, but for practical reasons concerning the miniball algorithm we consider complexes that are slightly bigger than the ones described above. More specifically, we compute filtration values using the miniball algorithm instead of computing radius of simplices in the truncated Dowker nerve. This gives us a filtered simplicial complex that lies between the truncated Dowker nerve and the full Dowker nerve, so it has the same interleaving guarantee as the truncated Dowker nerve. We have tested these implementations on the following data: the optical patch data sets called X (300, 30) and X (15, 30) in Carlsson et al. (2008), 6040 points from the cyclo-octane conformation space as analysed in Zomorodian (2012), the Clifford data set consisting of 2000 points on a curve on a torus considered in Oudot (2015), Chapter 123 14 M. Brun, N. Blaser Table 1 Sizes of sparse Dowker nerves using Sparse Cech Complex of Cavanna et al. (2015) described in Proposition 1 (Sheehy) and the Sparse Dowker Nerve described in Corollary 2 (parent) Data Complex Dim ε Unreduced (millions) Sheehy (millions) Parent (millions) Clifford torus Intrinsic 2 2.0 2593.9 1.3 2.8 Clifford torus Ambient 2 2.0 2593.9 1.4 1.0 Cyclo-octane Intrinsic 1 2.0 20.8 1.0 1.0 Cyclo-octane Ambient 1 2.0 20.8 1.0 1.0 Double torus Intrinsic 2 2.0 2593.9 1.5 2.9 Double torus Ambient 2 2.0 2593.9 1.8 1.9 X (15, 30) Intrinsic 1 1.5 20.8 3.3 3.2 X (15, 30) Ambient 1 1.5 20.8 3.3 3.2 X (300, 30) Intrinsic 1 2.5 20.8 4.9 1.8 X (300, 30) Ambient 1 2.5 20.8 1.8 1.7 In order to run these examples, we first used a farthest point sampling to take 500 points and calculated persistent homology of the subsamples. In the table we specify the name of the dataset (data), if persistent homology was computed using intrinsic or ambient Cech complex (complex), the homology dimension (dim), and the sparsification constant (ε). Note that both sparsifications result in substantially smaller nerves than the unreduced nerve. In general the two sparsifications result in nerves of similar sizes, but that for each sparsification there are outliers which are substantially larger 5, and the double torus from Dey et al. (2016) (Table 1). Computing the Sparse Cech complexes and the Sparse Dowker Nerves on these data sets with the same interleaving constant ε the resulting simplicial complexes are almost of the same size, with the size of the Sparse Dowker Nerve slightly smaller than the size of the Sparse Cech Complex. Our implementations, the data sets mentioned above and the scripts used to run compute persistent homology are available (Brun and Blaser 2018). 3 Truncated Dowker dissimilarities In this section, we provide the interleaving guarantee for the truncated Dowker dis- similarity used in the first step of the construction of the Sparse Dowker Nerve. Lemma 2 Let Λ : L × W →[0, ∞] be a Dowker dissimilarity satisfying the triangle inequality and let ( f ,λ) be an insertion pair for Λ.If β :[0, ∞] → [0, ∞] is an order preserving function satisfying β(t)< ∞ for t < ∞ and lim β(t ) =∞ t →∞ with associated translation function α:[0, ∞] → [0, ∞], then for every t ∈[0, ∞), (λ,β) the simplicial complex N Λ is contained in the simplicial complex N Λ . α(t ) (λ,β) Proof Let t ∈[0, ∞) and σ ∈ N Λ . We need to show that σ ∈ N Λ .Pick w ∈ W αt with Λ(l,w) < t for all l ∈ σ . Since Λ satisfies the triangle inequality we can pick l ∈ L so that Λ(l ,w) = 0. Let w = f (w, β(t )). Since ( f ,λ) is an insertion pair 0 0 0 for Λ we have Λ(l ,w ) ≤ β(t)<λ(w ). 0 0 0 123 Sparse Dowker nerves 15 The triangle inequality for Λ now gives Λ(l,w ) ≤ Λ(l ,w ) + Λ(l,w). 0 0 0 Let l ∈ σ . Since Λ(l,w) < t and Λ(l ,w ) ≤ β(t ), we get that 0 0 Λ(l,w )<β(t ) + t = α(t ). The inequality β(t)<λ(w ) implies that the set A ={s | λ(w ) ≤ β(s)} is contained 0 0 ← ← in (t , ∞). By definition β (λ(w )) = inf A,soweget t ≤ β (λ(w )). Since α is 0 0 ← ← order preserving this gives α(t ) ≤ αβ (λ(w )) and thus Λ(l,w )<αβ (λ(w )). 0 0 0 (λ,β) We conclude that σ ∈ N Λ . α(t ) Proposition 2 Let Λ : L × W →[0, ∞] be a Dowker dissimilarity satisfying the triangle inequality and let ( f ,λ) be an insertion pair for Λ.If β :[0, ∞] → [0, ∞] is an order preserving function satisfying β(t)< ∞ for t < ∞ and lim β(t ) =∞ t →∞ with associated translation function α:[0, ∞] → [0, ∞], then the filtered simplicial (λ,β) complexes N Λ and N Λ are (α, id)-interleaved. Proof By Lemma 2, for every t ∈[0, ∞), the simplicial complex N Λ is contained in (λ,β) (λ,β) the simplicial complex N Λ . Since Λ(l,w) ≤ Λ (l,w) for all (l,w) ∈ L ×W , α(t ) (λ,β) the simplicial complex N Λ is contained in the simplicial complex N Λ for every t t t ∈[0, ∞). 4 Sparse Dowker nerves In this section, we provide the technical result ensuring that the Dowker Nerve of the truncated Dowker dissimilarity can be further sparsified without changing its homo- topy type. Proposition 3 Let Λ:[n]× W →[0, ∞] be a Dowker dissimilarity and let ϕ:[n]→ [n] be a parent function for Λ with respect to λ:[n]→[0, ∞].If Λ(l,w) < ∞ implies Λ(l,w) < λ(l), then for every t ∈[0, ∞) the inclusion ι : N(Λ,ϕ,λ)(t ) − → N Λ is a homotopy equivalence. Proof By permuting the elements of [n] we can, without loss of generality, assume that λ(ϕ(l)) < λ(ϕ(l )) implies l > l . Note that if ϕ(l)> 0, then λ(ϕ(l)) < λ(ϕ(ϕ(l)), and deduce that l >ϕ(l) for every l > 0. 123 16 M. Brun, N. Blaser Let t ∈[0, ∞). We will prove the assertion by induction on n. The statement obviously holds when λ(ϕ(n)) ≥ t. In particular, it holds for n = 0. Let n ≥ 1 and suppose by induction that the statement holds for n − 1. We assume that λ(ϕ(n)) < t since otherwise the statement obviously holds for n.Let Λ :[n − 1]× W →[0, ∞] be the restriction of Λ to [n − 1]× W ⊆[n]× W and let λ and ϕ the restrictions of λ and ϕ to [n − 1]. Then ϕ is the parent function for Λ with respect to λ so the induction hypothesis is satisfied for Λ ,ϕ and λ . We define f :[n]→[n − 1] by ϕ(n) if l = n f (l) = l otherwise. Given σ ∈ N Λ we claim that σ ∪ f (σ ) ∈ N Λ .If n ∈ / σ , then this claim is trivial. t t t In order to justify the claim when n ∈ σ,wepick w ∈ W with Λ(l,w) < t for every l ∈ σ . By our assumption on Λ we then also have Λ(l,w) < λ(l) for every l ∈ σ.By definition of the parent function, Λ(n,w) < λ(n) implies Λ(ϕ(n), w) < λ(ϕ(n)) < t. We conclude that σ ∪ f (σ ) ∈ N Λ . t t Our next claim is that if σ ∈ N(Λ,ϕ,λ)(t ), then σ ∪ f (σ ) ∈ N(Λ,ϕ,λ)(t ).Again, we only need to consider the case n ∈ σ . We have already shown that σ ∪ f (σ ) ∈ N Λ . t t Since n is maximal in [n] we have λ(ϕ(l)) ≥ λ(ϕ(n)) for every l ∈[n], so this claim follows since Λ(n,w) < λ(n) implies Λ(ϕ(n), w) < λ(ϕ(n)). In particular, we can now conclude that the function f :[n]→[n − 1] and defines simplicial maps f : N Λ → N Λ t t and f : N(Λ,ϕ,λ)(t ) → N (Λ ,ϕ ,λ )(t ). On the other hand, the inclusion ι:[n −1]→[n] defines simplicial maps (see Sect. 5) ι : N Λ → N Λ and ι : N (Λ ,ϕ ,λ )(t ) → N(Λ,ϕ,λ)(t ). Moreover the above claims imply that the compositions f ι N Λ − → N Λ − → N Λ t t and f ι N(Λ,ϕ,λ)(t ) − → N (Λ ,ϕ ,λ )(t ) − → N(Λ,ϕ,λ)(t ) 123 Sparse Dowker nerves 17 are contiguous to the identity maps. Since f ι is the identity this implies that geometric realizations of the inclusions N Λ − → N Λ and N (Λ ,ϕ ,λ )(t ) − → N(Λ,ϕ,λ)(t ) are homotopy equivalences. Since we have assumed by induction that the geometric realization of the inclusion N (Λ ,ϕ ,λ )(t ) − → N Λ is a homotopy equivalence, we can conclude that the geometric realization of the inclusion N(Λ,ϕ,λ)(t ) − → N Λ is a homotopy equivalence. 5 The homotopy category of simplicial complexes The rest of the paper is aimed at stability results for Dowker Nerves. First we need some prerequisites on the homotopy category. Recall that a simplicial complex K = (V , K ) consists of a vertex set V and a set K of finite subsets of V with the property that if σ is a member of K , then every subset of σ is a member of K . Given a subset V ⊆ V and a simplicial complex K = (V , K ), we write K for the simplicial complex K = (V , K ) consisting of subsets of V V V V of the form σ ∩ V for σ ∈ K.The geometric realization of a simplicial complex K = (V , K ) is the space |K | consisting of all functions f : V →[0, 1] satisfying: 1. The support {v ∈ V | f (v) = 0} of f is a member of K 2. f (v) = 1. v∈V If V is finite, then |K | is given the subspace topology of the Euclidean space R . Otherwise U ⊆|K | is open if and only if for every finite V ⊆ V,the set U ∩|K  | is open in |K  |. The order complex of a partially ordered set (X , ≤) is the simplicial complex with vertex set X consisting of totally ordered finite subsets of X, that is, subsets of the form σ ={x , x ,..., x } with x < x < ··· x . 0 1 k 0 1 k A simplicial map f : K → L of simplicial complexes K = (V , K ) and L = (W , L) consists of a function f : V → W such that f (σ ) ={ f (v) | v ∈ σ } 123 18 M. Brun, N. Blaser is in L for every σ ∈ K . Observe that a simplicial map f : K → L induces a continuous map | f |: |K|→|L| of geometric realizations and that this promotes the geometric realization to a functor |·|: Cx → Top from the category Cx of simplicial complexes and simplicial maps to the category Top of topological spaces and continuous maps. Definition 10 The homotopy category hCx of simplicial complexes has the class of simplicial complexes as objects. Given simplicial complexes K and L, the morphism set hCx(K , L) is the set of homotopy classes of continuous maps from the geometric realization of K to the geometric realization of L. Composition in hCx is given by composition of functions representing homotopy classes. We remark in passing that the homotopy category of simplicial complexes is equivalent to the weak homotopy category of topological spaces. 6 Background on 2-categories We have chosen to reason about stability in the context of 2-categories. The pay-off from this high level of abstraction is that the proofs get relatively easy. In this section, we present some terminology on 2-categories. Most of this material is taken from Leinster (1998). Recall that a 2-category C consists of 1. A class of objects A, B,... 2. For all objects A, B a category C(A, B). The objects of C(A, B) are the morphisms in C and the morphisms α : f ⇒ g of C(A, B) are the 2-cells in C. 3. For every object A of C there is an identity morphism id : A → A and an identity 2-cell id : id ⇒ id . id A A 4. For all objects A, B and C of C there is a functor C(A, B) × C(B, C ) → C(A, C ) ( f , g) → g · f , which is associative and admits the identity morphisms and identity 2-cells of C as identities. Definition 11 Given 2-categories C and D,a functor F : C → D consists of 1. A function F : ob C → ob D 2. Functors F : C(A, B) → D(FA, FB) such that F (id ) = id and Fg ◦Ff = F (g ◦ f ) for A an object of C and f : A → B A FA and g : B → C morphisms of C. Definition 12 Given two functors F , G : C → D of 2-categories, a transformation α : F → G consists of 1. A morphism α : FA → GA in D for every A ∈ ob C 2. A 2-cell α : Gf ◦ α → α ◦ Ff for every morphism f : A → B in C. f A B 123 Sparse Dowker nerves 19 This structure is subject to the axioms given by commutativity of the following two diagrams: Gg ◦ α ◦ Ff id ◦α α ◦id Gg f g Ff g· f Gg ◦ Gf ◦ α α ◦ Fg ◦ Ff A C id id id G(id ) ◦ α α ◦ F (id A). A A A Definition 13 Given two functors F , G : C → D of 2-categories, and transformations α, β : F → G,a modification M : α → β consists of a 2-cell M : α → β A A A for every object A of C such that for every morphism f : A → B of C the following diagram commutes: id ◦M Gf A Gf ◦ α Gf ◦ β A A f β M ◦id B Ff α ◦ Ff β ◦ Ff . B B Definition 14 Given 2-categories C and D,the functor 2-category [C, D] is the 2- category with functors F : C → D as objects, transformations of such functors as morphisms and with 2-cells given by modifications. Given a category C we will consider it as a 2-category with only identity 2-cells. Thus, if C is a category and D is a 2-category we have defined the functor 2-categories [C, D] and [D, C]. op Definition 15 The opposite of a 2-category C is the 2-category C with the same objects as C, with op C (A, B) = C(B, A) and with composition obtained from composition in C. 7 Relations Dowker dissimilarities can be considered as filtered relations. In order to formulate this precisely, we need some background information on relations. 123 20 M. Brun, N. Blaser Definition 16 Let X and Y be sets. A relation R : X  Y is a subset R ⊆ X × Y . Definition 17 We define a partial order on the set of relations between X and Y by set inclusion. That is, for relations R : X  Y and R : X  Y,wehave R ≤ R if and only if R is contained in the subset R of X × Y . Definition 18 Given two relations R : X  Y and S : Y  Z, their composition S ◦ R : X  Z is S ◦ R ={(x , z) ∈ X × Z |∃ y ∈ Y : (x , y) ∈ R and (y, z) ∈ S, }. Definition 19 The 2-category S of sets and relations has as objects the class of sets and as morphisms the class of relations. The 2-cells are given by the inclusion partial order on the class of relations. Composition of morphisms is composition of relations and composition of 2-cells is given by composition of inclusions. The identity morphism on the set X is the diagonal Δ ={(x , x ) | x ∈ X }. The identity 2-cell on a relation R is the identity inclusion R ≤ R. op Definition 20 The transposition functor T : S → S is defined by T (X ) = X, T (R) = R ={(y, x ) | (x , y) ∈ R} T T T T and T (i ) = i , where i : R → S takes (y, x ) to (z,w) when (w, z) = i (x , y). Definition 21 A correspondence C : X  Y is a relation such that: 1. For every x ∈ X there exists y ∈ Y so that (x , y) ∈ C and 2. For every y ∈ Y there exists x ∈ X so that (x , y) ∈ C. Lemma 3 A relation C : X  Y is a correspondence if and only if there exists a relation D : Y  X so that Δ ≤ D ◦ C and Δ ≤ C ◦ D. X Y Proof By definition of a correspondence, for every x ∈ X, there exists y ∈ Y so that (x , y) ∈ C. This means that Δ ⊆ C ◦ C, where T T C ◦ C ={(x , z) ∈ X × X |∃ y ∈ Y : (x , y) ∈ C and (y, x ) ∈ C }. T T Reversing the roles of C and C we get the inclusion Δ ⊆ C ◦ C . Conversely, if C and D are relations with Δ ⊆ C ◦ D, then for every y ∈ Y , the element (y, y) is contained in C ◦ D. This means that there exists x ∈ X so that (x , y) ∈ C, and (y, x ) ∈ D. In particular for every y ∈ Y , there exists x ∈ X so that (x , y) ∈ C. Reversing the roles of C and D we get that for every x ∈ X there exists y ∈ Y so that (x , y) ∈ C. 123 Sparse Dowker nerves 21 8 The category of relations In this section, we introduce a novel 2-category of relations. We start by recalling Dowker’s definition of the nerve of a relation (called the complex K in Dowker 1952, Sect. 1). Definition 22 Let R ⊆ X × Y be a relation. The nerve of R is the simplicial complex NR ={finite σ ⊆ X |∃y ∈ Y with (x , y) ∈ R for all x ∈ σ }. Example 2 Let X be a space, and let Y be a cover of X. In particular every element y ∈ Y is a subset of X.Let R be the relation R ⊆ X ×Y consisting of pairs (x , y) with x ∈ y. A direct inspection reveals that the nerve of R is equal to the Borsuk Nerve of the cover Y . Definition 23 The 2-category R of relations has as objects the class of relations. A morphism C : R → R in R between relations R ⊆ X × Y and R ⊆ X × Y consists of a relation C ⊆ X × X such that for every σ ∈ NR,the set (NC )(σ ) ={x ∈ X | there exists x ∈ σ with (x , x ) ∈ C } is an element (NC )(σ ) ∈ NR of the nerve of R . In particular, (NC )(σ ) is finite and non-empty. The class of 2-cells in R is the class of inclusions C ⊆ C for morphisms 1 2 C , C ⊆ X × X . Composition in R is given by composition of relations. 1 2 Note that if C : R → R is a morphism in R, then NC is an order preserving function NC : NR → NR , and thus it induces a simplicial map NC : Δ(NR) → Δ(NR ) of order complexes. Given a simplicial complex K , the simplicial complex Δ(K ) is the barycentric subdivision of K . The geometric realizations of K and Δ(K ) are home- omorphic. In particular, they represent isomorphic objects in the homotopy category of simplicial complexes. Lemma 4 Let C , C : R → R be morphisms in R. If there exists a 2-cell α : C → 0 1 0 C , then the geometric realizations of the simplicial maps NC , NC : Δ(NR) → Δ(NR ) 0 1 are homotopic. Proof Let I be the partially ordered set I ={0 → 1}. Since C ⊆ C , we can define an order preserving map 0 1 C : I × NR → NR 123 22 M. Brun, N. Blaser by C (i,σ ) = NC (σ ) for i = 0, 1. On order complexes C induces a simplicial map Δ(C ) : Δ(I × NR) → Δ(NR ). As a consequence of Milnor (1981), Theorem 1 and Milnor (1981), Theorem 2 the geometric realization of Δ(I × NR) is homeomorphic to the product of the geometric realizations of Δ(I ) and Δ(NR). The geometric realization of Δ(I ) is homeomor- phic to the closed unit interval. Thus we have constructed a homotopy between the geoemtric realizations of NC and NC . 1 2 Definition 24 The nerve functor N : R → hCx is the functor taking a relation R the order complex Δ(NR) of its nerve and taking a morphism C : R → R in R to the morphism |NC|: |Δ(NR)|→|Δ(NR )| in hCx. Let us emphasize that if α : C → C is a 2-cell in R, then |NC |=|NC | in hCx. 1 2 1 2 9 Interleavings In this section, we set the concept of interleaving into the context of 2-categories. This material is well-known in the applied topology community. We write [0, ∞) for the set of non-negative real numbers and consider it as a partially ordered set. We also consider [0, ∞) as a category with object set [0, ∞) and with a unique morphism s → t if and only if s ≤ t. Definition 25 Let C be a 2-category. The category of filtered objects in C is the func- tor 2-category [[0, ∞), C].A filtered object in C is an object C :[0, ∞) → C of [[0, ∞), C], that is, C is a functor from [0, ∞) to C.A morphism f : C → C of filtered objects in C is a transformation. We will be so interested in the category of filtered objects in the 2-category of relations that we give a name to this particular 2-category. Definition 26 A filtered relation is a functor from [0, ∞) to R. We define the 2- category of filtered relations to be the 2-category [[0, ∞), R] of functors from [0, ∞) to R. Definition 27 Let C be a 2-category and let α:[0, ∞) →[0, ∞) be a translation function, that is, an order preserving function satisfying t ≤ α(t ) for all t ∈[0, ∞). 1. The pull-back functor α :[[0, ∞), C]→[[0, ∞), C] is the functor taking a fil- tered object C :[0, ∞) → C in C to the filtered object α C = C ◦ α. 2. The unit of the functor α :[[0, ∞), C]→[[0, ∞), C] is the natural transformation α : id → α defined by α (t ) = C (t ≤ α(t )) : C (t ) → α (C )(t ). ∗C 123 Sparse Dowker nerves 23 Definition 28 Let C and C be filtered objects in a 2-category C and let α, α :[0, ∞) → [0, ∞) be functors under the identity. 1. An (α, α )-interleaving between C and C is a pair (F , F ) of morphisms F : C → ∗    ∗ α C and F : C → α C in [[0, ∞), C] such that there exist 2-cells ∗   ∗ (α ◦ α) → (α F ) ◦ F and (α ◦ α ) → (α F ) ◦ F . ∗ ∗ 2. We say that C and C are (α, α )-interleaved if there exists an (α, α )-interleaving between C and C . The following results appear in Bubenik et al. (2015), Propositions 2.2.11 and 2.2.13. Lemma 5 (Functoriality) Let C and C be filtered objects in a 2-category C,let α, α :[0, ∞) →[0, ∞) be functors under the identity and let H : C → D be a functor of 2-categories. If C and C are (α, α )-interleaved, then the filtered objects HC and HC in D are (α, α )-interleaved. Lemma 6 (Triangle inequality) Let C, C and C be filtered objects in a 2-category C. If C and C are (α, α )-interleaved and C and C are (β, β )-interleaved, then C and C are (βα, α β )-interleaved. 10 Filtered relations and Dowker dissimilarities In this section, we introduce a novel 2-category of Dowker dissimilarities as a certain sub-2-category of the category of filtered relations. Definition 29 The filtered nerve functor is the functor N :[[0, ∞), R]→[[0, ∞), hTop] from the 2-category of filtered relations to the category of homotopy filtered spaces taking X :[0, ∞) → R to the composition X N [0, ∞) − → R − → hTop. From Lemma 5 we get: Corollary 3 If R and R are (α, α )-interleaved filtered relations, then N R and N R are (α, α )-interleaved filtered simplicial complexes. Given a Dowker dissimilarity Λ : L × W →[0, ∞] and t ∈[0, ∞) we consider Λ ={(l,w) ∈ L × W | Λ(l,w) < t } as an object of the category R of relations. Given s ≤ t in [0, ∞) we let Λ = Δ ={(l, l) l ∈ L}⊆ L × L s≤t L 123 24 M. Brun, N. Blaser considered as a morphism Λ : Λ → Λ in R. s≤t s t Definition 30 The filtered relation associated to a Dowker dissimilarity Λ : L × W → [0, ∞] is the functor Λ:[0, ∞) → R taking t ∈[0, ∞) to the relation Λ and taking s ≤ t in [0, ∞) to the morphism Λ t s≤t in R. Definition 31 Let Λ : L × W →[0, ∞] and Λ : L × W →[0, ∞] be Dowker dissimilarities. A morphism C : Λ → Λ of filtered relations is a morphism of Dowker dissimilarities if there exists a relation C ⊆ L × L so that C = C : Λ → Λ for t t every t ∈[0, ∞). Definition 32 The 2-category Dow of Dowker dissimilarities is the 2-category with Dowker dissimilarities as objects and morphisms of Dowker dissimilarities as mor- phisms. Given morphisms C , C : Λ → Λ of Dowker dissimilarities, we define the 1 2 set of 2-cells α : C → C in Dow by letting Dow(C , C ) =[[0, ∞), R](C , C ). 1 2 1 2 1 2 Definition 33 Let Λ : L ×W →[0, ∞] be a Dowker dissimilarity. The Dowker Nerve N Λ of Λ is the filtered nerve of the underlying filtered relation. Note that the Dowker Nerve is filtered by inclusion of sub-complexes, that is, if s ≤ t, then N Λ : N Λ → N Λ is an inclusion of simplicial complexes. s≤t s t Definition 34 Let Λ : L × W →[0, ∞] be a Dowker dissimilarity. Given l ∈ L and t > 0, the Λ-ball of radius t centred at l is B (l, t ) ={w ∈ W | Λ(l,w) < t }. Example 3 Let (M , d) be a metric space and L and W be subsets of M. Then the restriction Λ : L × W →[0, ∞] of d to L × W is a Dowker dissimilarity. The Dowker Nerve of Λ is the composite Λ N [0, ∞) − → R − → Cx taking t ∈[0, ∞) to {finite σ ⊆ L | there exists w ∈ W with d(l,w) < t for all l ∈ σ }. If L = W = M, then the Λ-ball of radius t centred at l is the usual open ball in M of ˇ ˇ radius t centred at l and the Dowker Nerve of Λ is equal to the Cech complex C(M ). Lemma 7 Let Λ : L × W →[0, ∞] be a Dowker dissimilarity. Given t > 0, the nerve N Λ is isomorphic to the Borsuk Nerve of the cover of the set B (l, t ) l∈L 123 Sparse Dowker nerves 25 by balls B (l, s) of radius s ≤ t centred at points in L. It is well-known that, in the above situation, the geometric realization of N Λ is homotopic to the geometric realization of the Borsuk Nerve of the cover of the set B (l, t ) l∈L by balls B (l, t ) of radius t centred at points in L. See e.g. Blaser and Brun (2018), Lemma 2.3. Corollary 3 gives: Corollary 4 If Λ : L × W →[0, ∞] and Λ : L × W →[0, ∞] are (α, α )- interleaved Dowker dissimilarities, then N Λ and N Λ are (α, α )-interleaved filtered simplicial complexes. Definition 35 Let Λ : L × W →[0, ∞] be a Dowker dissimilarity. The Rips complex of Λ is the filtered simplicial complex RΛ defined by (RΛ)(t ) ={finite σ ⊆ L | every τ ⊆ σ with |τ|≤ 2is in (N Λ)(t )}. Corollary 5 If Λ : L × W →[0, ∞] and Λ : L × W →[0, ∞] are (α, α )- interleaved Dowker dissimilarities, then RΛ and RΛ are (α, α )-interleaved filtered simplicial complexes. Proof Use Corollary 4 and the fact that the Rips complex depends functorially on the one skeleton of the Dowker Nerve. 11 Stability and interleaving distance The functoriality of interleaving implies that all functorial constructions are stable with respect to interleaving. In this section we relate interleaving distance of Dowker dissimilarities to Gromov–Hausdorff distance of Edwards (1975), Gromov (1981) and to the network distance defined in Chowdhury and Mémoli (2018). Definition 36 Let C and C be filtered objects in a 2-category C. 1. Given a, a ∈[0, ∞] we say that the filtered objects C and C are additively (a, a )-interleaved if they are (α, α )-interleaved for the functions α(t ) = a + t and α (t ) = a + t. 2. The interleaving distance of C and C is d (C , C ) = inf{a ∈[0, ∞] | C and C are additively int (a, a) − interleaved}, with the convention that inf ∅=∞. Definition 37 A non-negatively weighted network is a pair (X,ω ) of a set X and a weight function ω : X × X →[0, ∞). 123 26 M. Brun, N. Blaser Definition 38 Let ω : X × X →[0, ∞) and ω  : X × X →[0, ∞) be non- X X negatively weighted networks and let C ⊆ X × X .The distortion of C is dis(C ) = sup |ω (x , y) − ω (x , y )|. (x ,x ), (y,y )∈C Recall from Definition 21 that C ⊆ X × X is a correspondence if the projections of C on both X and X are surjective. Definition 39 Let ω : X × X →[0, ∞) and ω : X × X →[0, ∞) be non- negatively weighted networks and let R be the set of correspondences C ⊆ X × X . The network distance between X and X is d (X , X ) = inf dis(C ). 2 C ∈R The Stability Theorem (Chowdhury and Mémoli 2018, Proposition 15) for networks is a consequence of functoriality of interleaving distance, the Algebraic Stability The- orem for bottleneck distance (Chazal et al. 2009, Theorem 4.4) and the following result: Proposition 4 Let ω : X × X →[0, ∞) and ω : X × X →[0, ∞) be networks, and write Λ : X × X →[0, ∞] and Λ : X × X →[0, ∞] for the corresponding Dowker dissimilarities with Λ(x , y) = ω (x , y) and Λ (x , y ) = ω  (x , y ). Then d (Λ, Λ ) ≤ 2d (X , X ). int N Proof We have to show that d (Λ, Λ ) ≤ dis(C ) for every correspondence C ⊆ int X × X .Solet C ⊆ X × X be a correspondence and let a > dis(C ). By definition of dis(C ), for all (l, l ) and (w, w ) in C we have |ω (l,w) − ω (l ,w )| < a. Defining α:[0, ∞) →[0, ∞) by α(t ) = t + a, by symmetry, it suffices to show that C defines a morphism C : Λ → α Λ . That is, we have to show that if σ ∈ Λ , then (NC )(σ ) ∈ Λ . So suppose that α(t ) w ∈ X satisfies Λ(l,w) < t for all l ∈ σ . Since C is a correspondence we can pick w ∈ X so that (w, w ) ∈ C. By definition of NC, for every l ∈ (NC )(σ ), there exists l ∈ σ so that (l, l ) ∈ C. By definition of distortion distance this gives Λ (l ,w ) = ω  (l ,w )< a + ω (l,w) = a + Λ(l,w) < a + t = α(t ). X X 123 Sparse Dowker nerves 27 We conclude that σ ∈ N Λ implies (NC )(σ ) ∈ N Λ as desired. α(t ) The Stability Theorem (Chazal et al. 2014, Theorem 5.2) for metric spaces is a conse- quence of functoriality of interleaving distance, the Algebraic Stability Theorem for bottleneck distance (Chazal et al. 2009, Theorem 4.4) and the following result: Corollary 6 Let (M , d) and (M , d ) be metric spaces, and write Λ : M × M →[0, ∞] and Λ : M × M →[0, ∞] for the corresponding Dowker dissimilarities with Λ(p, q)=d(p, q) and Λ (p , q ) = d (p , q ). Then d (Λ, Λ ) ≤ 2d (M , M ). int GH Proof By Burago et al. (2001), Theorem 7.3.25 the Gromov–Hausdorff distance of the metric spaces (M , d) and (M , d ) agrees with their network distance when we consider them as non-negatively weighted networks. That is, d (M , M ) = d (M , M ).The GH N result now follows from Proposition 4. 12 Conclusion We generalize the Sparse Cech construction of Cavanna et al. (2015)toarbitrarymetric spaces and to a large class of Dowker dissimilarities. The abstract context of Dowker dissimilarities is well-suited for sparse nerve constructions. The concepts of filtered relations and strict 2-categories enable us to easily formulate and prove basic stability results. An implementation of the Sparse Dowker Nerve most similar to the Sparse Cech complex is available at GitHub Brun and Blaser (2018) together with a user tutorial. This implementation is not practical for analysis of high dimensional data. Other recent work on sparse complexes has focused on Euclidean space (Choud- hary et al. 2018) or the use of general simplicial maps (Dey et al. 2016; Boissonnat et al. 2018). It is possible that these considerations can be combined to obtain even smaller filtered nerves. In further work, we will improve this construction and we will make Sparse Dowker Nerves for Dowker dissimilarities that do not satisfy the triangle inequality. Acknowledgements This research was supported by the Research Council of Norway through Grant 248840. The authors have no conflicts of interest. We would like to thank the referees for helpful comments improving this paper. Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 Interna- tional License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made. 123 28 M. Brun, N. Blaser References Blumberg, A.J., Lesnick, M.: Universality of the homotopy interleaving distance (2017). https://arxiv.org/ abs/1705.01690 Boissonnat, J.-D., Pritam, S., Pareek, D. Strong Collapse for Persistence (2018). ArXiv e-prints. arXiv:1809.10945 Blaser, N., Brun, M.: Divisive cover. Math. Comput. Sci. (2018). https://doi.org/10.1007/s11786-018-0352- Brun, M., Blaser, N.: Sparse-Dowker-nerves (2018). https://github.com/mbr085/Sparse-Dowker-Nerves Bubenik, P., de Silva, V., Scott, J.: Metrics for generalized persistence modules. Found. Comput. Math. 15(6), 1501–1531 (2015) Buchet, M., Chazal, F., Oudot, S.Y., Sheehy, D.: Efficient and robust persistent homology for measures. Comput. Geom.: Theory Appl. 58, 70–96 (2016) Burago, D., Burago, Y., Ivanov, S.: A Course in Metric Geometry. Graduate Studies in Mathematics, vol. 33. American Mathematical Society, Providence (2001) Carlsson, G., Ishkhanov, T., de Silva, V., Zomorodian, A.: On the local behavior of spaces of natural images. Int. J. Comput. Vis. 76(1), 1–12 (2008) Cavanna, N.J., Jahanseir, M., Sheehy, D.R.: A geometric perspective on sparse filtrations. CoRR, arXiv:1506.03797 (2015) Chazal, F., Cohen-Steiner, D., Glisse, M., Guibas, L., Oudot, S.: Proximity of persistence modules and their diagrams. In: SoCG, pp. 7–246 (2009) Chazal, F., Cohen-Steiner, D., Guibas, L.J., Mémoli, F., Oudot, S.Y.: Gromov–hausdorff stable signatures for shapes using persistence. In: Proceedings of the Symposium on Geometry Processing, SGP ’09, pp, 1393–1403. Eurographics Association, Aire-la-Ville (2009) Chazal, F., de Silva, V., Oudot, S.: Persistence stability for geometric complexes. Geom. Dedicata 173, 193–214 (2014) Choudhary, A., Kerber, M., Raghvendra, S.: Improved topological approximations by digitization. CoRR, arXiv:1812.04966 (2018) Chowdhury, S., Mémoli, F.: A functorial Dowker theorem and persistent homology of asymmetric networks (2018). ArXiv e-prints. arXiv:1608.05432 Dey, T.K., Shi, D., Wang, Y.: SimBa: an efficient tool for approximating Rips-filtration persistence via simplicial batch-collapse. In: 24th Annual European Symposium on Algorithms, vol. 57 of LIPIcs. Leibniz Int. Proc. Inform, Art. No. 35, 16 (2016) Dowker, C.H.: Homology groups of relations. Ann. Math. 2(56), 84–95 (1952) Edwards, D.A.: The structure of superspace. In: Studies in Topology. Proceeding Conference, University of North Carolina, Charlotte, N. C., 1974; dedicated to Mathematics Section Polish Academy of Sciences, pp. 121–133. Academic Press, New York (1975) Embrechts, P., Hofert, M.: A note on generalized inverses. Math. Methods Oper. Res. 77(3), 423–432 (2013) Gromov, M.: Groups of polynomial growth and expanding maps. Inst. Hautes Études Sci. Publ. Math. 53, 53–73 (1981) Lawvere, F.W.: Metric spaces, generalized logic, and closed categories. Ann. Math. (2) 65, 357–362 (1957) Leinster, T.: Basic bicategories (1998) Milnor, J.: The geometric realization of a semi-simplicial complex. Inst. Hautes Études Sci. Publ. Math. 53, 53–73 (1981) Oudot, S.Y.: Persistence Theory: From Quiver Representations to Data Analysis. Mathematical Surveys and Monographs, vol. 209. American Mathematical Society, Providence (2015) Sheehy, D.R.: Linear-size approximations to the Vietoris–Rips filtration. Discrete Comput. Geom. 49(4), 778–796 (2013) Spanier, E.H.: Algebraic Topology. Springer, New York (1966). Corrected reprint of the 1966 original Zomorodian, A.: Topological data analysis. In Advances in Applied and Computational Topology. Pro- ceedings of Symposia in Applied Mathematics, vol. 70, pp. 1–39. American Mathematical Society, Providence (2012) 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: Jun 29, 2019

References

  • Metrics for generalized persistence modules
    Bubenik, P; Silva, V; Scott, J
  • Efficient and robust persistent homology for measures
    Buchet, M; Chazal, F; Oudot, SY; Sheehy, D
  • A Course in Metric Geometry
    Burago, D; Burago, Y; Ivanov, S
  • On the local behavior of spaces of natural images
    Carlsson, G; Ishkhanov, T; Silva, V; Zomorodian, A
  • Persistence stability for geometric complexes
    Chazal, F; Silva, V; Oudot, S
  • Homology groups of relations
    Dowker, CH
  • A note on generalized inverses
    Embrechts, P; Hofert, M
  • Groups of polynomial growth and expanding maps
    Gromov, M
  • Metric spaces, generalized logic, and closed categories
    Lawvere, FW
  • The geometric realization of a semi-simplicial complex
    Milnor, J
  • Persistence Theory: From Quiver Representations to Data Analysis
    Oudot, SY
  • Linear-size approximations to the Vietoris–Rips filtration
    Sheehy, DR
  • Algebraic Topology
    Spanier, EH