Access the full text.

Sign up today, get DeepDyve free for 14 days.

Journal of Applied and Computational Topology
, Volume 4 (4) – Dec 28, 2020

/lp/springer-journals/contractibility-of-a-persistence-map-preimage-JssSpE5Sgz

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

This work is motivated by the following question in data-driven study of dynamical systems: given a dynamical system that is observed via time series of persistence diagrams that encode topological features of snapshots of solutions, what conclusions can be drawn about solutions of the original dynamical system? We address this challenge in the context of an N dimensional system of ordinary differential equation N N deﬁned in R . To each point in R (e.g. an initial condition) we associate a persistence diagram. The main result of this paper is that under this association the preimage of every persistence diagram is contractible. As an application we provide conditions under which multiple time series of persistence diagrams can be used to conclude the existence of a ﬁxed point of the differential equation that generates the time series. Keywords Topological data analysis · Persistent homology · Dynamical systems · Fixed point theorem Mathematics Subject Classiﬁcation 37C25 · 55N31 · 06B35 · 55-08 · 06F30 1 Introduction Topological data analysis (TDA), especially in the form of persistent homology, is rapidly developing into a widely used tool for the analysis of high dimensional data associated with nonlinear structures (Edelsbrunner and Harer 2010; Zomorodian and B Jacek Cyranka jcyranka@gmail.com Konstantin Mischaikow mischaik@math.rutgers.edu Charles Weibel weibel@math.rutgers.edu Department of Mathematics, Rutgers, The State University of New Jersey, 110 Frelinghusen Rd., Piscataway, NJ 08854-8019, USA Institute of Informatics, University of Warsaw, Banacha 2, 02-097 Warsaw, Poland 123 510 J. Cyranka et al. Carlsson 2005; Oudot 2015). That topological tools can play a role in this subject should not be unexpected, given the central role of nonlinear functional analysis in the study of geometry, analysis, and differential equations, for example. What is perhaps surprising is that, to the best of our knowledge, there have been no systematic attempts to rigorously analyze the dynamics of differential equations using persistent homology. Persistent homology is often used as a means of data reduction. A typical example takes the form of a complicated scalar function deﬁned over a ﬁxed domain, where the geometry of the sub-(super)-level sets is encoded via homology. Of particular interest to us are settings in which the scalar function arises as a solution to a partial differential equation (PDE); we are interested in tracking the evolution of the function, but exper- imental data only provides information on the level of digital images of the process. Furthermore, capturing the dynamics of a PDE often requires a long time series of rather large digital images. Thus, rather than storing the full images, one can hope to work with a time series of persistence diagrams. Our aim is to draw conclusions about the dynamics of the original PDE from the time series of the persistence diagrams. This is an extremely ambitious goal and far beyond our capabilities at the moment. A much simpler question is the following: if there is an attracting region in the space of persistence diagrams, under what conditions can we conclude that there is a ﬁxed point for the PDE? This paper represents a ﬁrst step towards answering the simpler question. The- orem 4.3 shows that given an ordinary differential equation (ODE) with a global compact attractor A ⊂ R and a neighborhood in the space of persistence diagrams that is mapped into itself under the dynamics, then there exists a ﬁxed point for the ODE. In applications one could consider the ODE as arising from a ﬁnite difference approximation of the PDE. The challenge is that to obtain results one must understand the topology of data , the space of data having a ﬁxed persistence diagram P, a topic for which there are only limited results. That the structure of data is complicated follows directly from the fact that persistent homology can provide tremendous data reduction, but in a highly nonlinear fashion. With this in mind, the primary goal of this paper is to show that for a reasonable class of problems the space data is a ﬁnite set of contractible, simplicial sets. The importance of this result is that it opens the possibility of applying standard algebraic topological tools, e.g., Lefschetz ﬁxed point theorem, Conley index, to dynamics that is observed through the lens of persistent homology. To state our goal precisely requires the introduction of notation. Throughout this paper S denotes the 1-dimensional simplicial complex composed out of N vertices [i ] (i = 1,..., N ) and N − 1 edges [i , i + 1] (i = 1,..., N − 1). It is a simplicial decomposition of closed bounded interval in R. We study ﬁltrations of S deﬁned as follows. N N Deﬁnition 1.1 Let z = (z ,..., z ) ∈ R . Deﬁne f : R × S → R by 1 N N z if σ =[ j ], f (z,σ ) := max z , z if σ =[ j , j + 1]. j j +1 For r ∈ R,weset S (z, r ) := {σ ∈ S : f (z,σ ) ≤ r } . N N 123 Contractibility of a persistence map preimage 511 Deﬁnition 1.2 Given z = (z ,..., z ) ∈ R , we can reorder the coordinates of z 1 N such that z ≤ z ≤ ··· ≤ z . j j j 1 2 N 1 F The sublevel-set ﬁltration of S at z, which we write as S (z), is given by S (z, z ) ⊆ S (z, z ) ⊆ ··· ⊆ S (z, z ). N j N j N j 1 2 N Because S (z) is a ﬁnite ﬁltration of simplicial complexes, completely determined by z, we can use classical results from (Edelsbrunner and Harer 2010; Zomorodian and Carlsson 2005) to compute the persistence diagram of S (z). We treat this as a map Dgm : R → Per, where Per denotes the space of all persistence diagrams. Thus the space data of all N −1 z ∈ R having persistence diagram P is just Dgm (P). We remark that there are a variety of topologies that can be put on Per such that Dgm becomes a continuous map (Chazal et al. 2016; Cohen-Steiner et al. 2007). Since S is one-dimensional and contractible, we are only concerned with the persistent homology H , i.e., the persistence diagrams associated with connected com- ponents. Therefore for the rest of the paper we restrict our study to consist of the family Per of persistence diagrams of level zero. Here is the main result of this paper. Theorem 1.3 For every persistence diagram P, the space data ⊂ R is composed of a ﬁnite number of mutually disjoint components. Each component is contractible, and is homeomorphic to a ﬁnite union of convex, potentially unbounded polytopes. The proof of Theorem 1.3 is not particularly difﬁcult, but it is technical. We ﬁrst describe the connected components of data ; see Lemma 2.4. In Sect. 2.2,weintro- duce the poset Str of cellular strings, which are be used to decompose each component as a ﬁnite union of convex polytopes in Sect. 2.3. In Sect. 3, we show that the realization of Str is contractible. To emphasize that Theorem 1.3 is not a trivial result, we use Fig. 1 to demonstrate that data is not a convex subet of R . In particular, consider the vectors v = (v ,...,v ) and w = (w ,...,w ) on the left of Fig. 1. It is left to the reader to 1 4 1 4 check that Dgm(v) = Dgm(w) and that this persistence diagram is given by the pair of black dots (see right of Fig. 1). Note that the vectors in R , indicated (on the left) in blue stars and red squares, lie on a straight line from v to w. However, the persistence diagrams indicated (on the right) in blue and red clearly differ from Dgm(v). Thus, the red and blue vectors do not lie in data . Dgm(v) In Sect. 4 we apply Theorem 1.3 to prove the existence of ﬁxed points with given persistence diagrams for a dissipative ordinary differential equation. Analogous results can be obtain for superlevel set ﬁltrations (see Sect. 5). 123 512 J. Cyranka et al. Fig. 1 Non-convexity of the preimage data under the persistence map Dgm. In the left ﬁgure the two vectors, v = (v ,...,v ) and w = (w ,...,w ), lie in the preimage of the persistence diagram P, 1 4 1 4 composed out of two black points visible on the right ﬁgure. Applying Dgm to convex linear combinations of v and w results in a path in the persistence plane illustrated on the right (the convex path is marked in grey, and two sample vectors on the path are marked using red squares and blue stars) (color ﬁgure online) 2 Invariants for a ﬁxed persistence diagram Fix a persistence diagram P. To describe the structure of the space data ,weintro- duce two levels of invariants: the critical value sequences, representing the connected components of data , and (for each of these), a partially ordered set Str indexing a polytope decomposition of the component. 2.1 Components Fix a persistence diagram P. To describe the (ﬁnitely many) connected components of data , it is useful to introduce notation that records the order in which the relevant local maxima and minima occur. We say that z = (z ,..., z ) ∈ R is a typical point if its coordinates are distinct. 1 N If z is a typical point and 1 < n < N , we say that z is a local minimum (of z)if z > z < z , and a local maximum if z < z > z ;itisa local extremum n−1 n n+1 n−1 n n+1 if it is a local minimum or maximum. We say that z and z are boundary extrema; 1 N z is a local minimum (resp., maximum) if z < z (resp., z > z ). 1 1 2 1 2 Deﬁnition 2.1 The critical value sequence of a typical point z = (z ,..., z ) is 1 N cv(z) = z ,..., z ∈ R , n n 1 K where the z are the local extrema of z, excluding boundary extrema that are local maxima, and n < n < ··· < n . 1 2 K Example 2.2 Let z = (1.5, −0.9, 1.1, 2.1, 1.4) ∈ R . The local minimum is z and the local maximum is z . The boundary extrema are z and z . Since z is also a local 4 1 5 1 maximum we do not include it in the critical value sequence. Thus h = cv(z) = (−0.9, 2.1, 1.4). 123 Contractibility of a persistence map preimage 513 The following notion emphasizes the structure of the critical value sequences. Deﬁnition 2.3 A 010 critical value sequence of (odd) length K is a vector cv = (z ,..., z ) ∈ R with the property that 1 K z < z > z < ··· < z > z . n n n n n 1 2 3 K −1 K A 101 critical value sequence is deﬁned similarly, with the inequalities reversed. Since we are using sublevel set ﬁltrations to compute the persistence diagram we focus on 010 critical value sequences. Lemma 2.4 below shows that the local extrema of z are determined up to order by its persistence diagram, and hence that there are only ﬁnitely many critical value sequences for any ﬁxed persistence diagram. Recall that a persistence diagram is a ﬁnite collection of persistence points b d b d p = (p , p ) , where p and p denote birth and death values, respectively. Since i i i i S is connected, the persistence diagram of a typical point z has a unique persistence b d b d point p = (p , p ) such that p = min z and p =∞; without loss of i n=1,...,N n i i i i generality, we may relabel p as p . i 1 Lemma 2.4 Let z ∈ R be a typical point with persistence diagram b d p = (p , p ) | m = 1,..., M . m m Then, z has K = 2M − 1 local extrema; the local minima of z are precisely p m=1 and the interior local maxima of z are precisely p . m=2 We leave the proof of Lemma 2.4 to the reader, remarking that it still holds when z ∈ R is not a typical point, except that the persistence diagram may be a multiset (there may be multiple copies of a single persistence point). Given a point z with persistence diagram P,let C (z) denote the component of data containing z. The following lemma shows that data is the disjoint union of the ﬁnitely many disjoint components C (z), indexed by the critical value sequences. The proof follows from the observation that the order of the local extrema cannot be changed while preserving the persistence diagram. Lemma 2.5 If z and z are typical points in R then C (z) = C (z ) if and only if cv(z) = cv(z ). Moreover, C (z) is the closure of the set of typical points in C (z). This proves the ﬁrst assertion in Theorem 1.3. Remark 2.6 The components C (z) group vectors into equivalence classes that can be characterized using the notion of chiral merge tree as deﬁned in Curry (2018). Corollary 5.5 of Curry (2018) shows that the number of chiral merge trees realizing N −1 diagram P is equal to 2 μ (I ), where B is the barcode realization of P, i.e. B j j =2 set of intervals I =[b , d ] having the birth and death values of the j-th persistence j j j point as its endpoints, and μ (I ) is the number of intervals in B that contain I . B j j 123 514 J. Cyranka et al. 2.2 Cellular strings In this section, we deﬁne the poset Str(N , M ) of cellular strings associated to M points arising from a vector in R . Thus we ﬁx N and M, where N ≥ 2M − 1. Consider a string of symbols s = s ··· s of length N , where each symbol s is 1 N n either 0, 1, or X (we refer to 0 and 1 as bits). Any such string can be represented as s = γ ··· γ where each block γ is a substring made up of a single symbol (that is, 1 J j γ is 0 ··· 0, 1 ··· 1, or X ··· X), and consecutive blocks have different symbols. We refer to s = γ ··· γ as the canonical representation of s. 1 J Deﬁnition 2.7 Fix M < N . A 010 cellular string is a symbol string s of length N such that, for the canonical representation s = γ ··· γ : 1 J (i) the symbols that make up γ and γ are different; j j +1 (ii) γ and γ consist of the symbols 0 or X; 1 J (iii) if γ consists of the symbol X, then the symbol of γ is different from the j j −1 symbol of γ ; j +1 (iv) there are exactly M values of j for which γ consists of the symbol 0. The set Str(N , M ) of cellular strings is a poset, where s < s if the string s is obtained from s by replacing some of the bits 0 and 1 in s by X. The dimension of a cellular string s,dim(s), is the number of symbols X in s.It follows from (iv) that M of the blocks γ have the form 0 ··· 0, and M − 1havethe form 1 ··· 1. Thus, K = 2M − 1 of the blocks are bitstrings. If these bitstrings are γ ,...,γ , then the symbol for γ is 0 if k is odd and 1 if k is even. Since each j j j 1 K k block has at least one symbol, it follows that any cellular string has dimension at most L = N − K . (r ) We write Str (N , M ) for the sub-poset of all cellular strings whose ﬁrst r − 1 (1) (L+1) symbols are X. Note that Str(N , M ) = Str (N , M ) and Str (N , M ) = {X ··· X010 ··· 10}. Proposition 2.8 An element of Str(N , M ) is maximal if and only if it is an L- dimensional cellular string, where L = (N − K ). Proof Let s = γ ...γ ∈ Str(N , M ). By deﬁnition, dim(s) ≤ L. Conversely, sup- 1 J pose that the symbol X appears in s has less than L times. Then some bitstring γ has length ≥ 2. Let s be the cellular string obtained by replacing the ﬁrst symbol of γ by X. Then s < s ,so s is not maximal. Since both N and M are ﬁxed in our analysis, we simplify the notation and write Str for Str(N , M ). Figure 2 illustrates the poset Str when M = 2, K = 3 and N = 5; (2) the right column is Str . Lemma 2.9 Every string s is the greatest lower bound of the set of L-dimensional strings s with s < s. It follows that Str has the least upper bound property: if two strings have a lower bound, they have a greatest lower bound. A 101 cellular string is deﬁned similarly, interchanging 0 and 1. 123 Contractibility of a persistence map preimage 515 Fig. 2 The string poset Str for M = 2and N = 5. Two-dimensional, one-dimensional, and zero-dimensional strings are surrounded by rectangles, ellipses, and nothing, respectively. The arrows indicate the partial order. (2) The rightmost column is the sub-poset Str Proof We proceed by downward induction on the dimension d of s , the case d = L being clear. Consider the canonical representation, s = γ ··· γ .If d < L, then some 1 J bitstring γ has length ≥ 2. Consider the strings s = γ ··· γ Xγγ ¯ ··· γ and j 1 1 j −1 j +1 J s = γ ··· γ γ¯ X γ ··· γ where γ¯ is a bitstring consisting of the same symbol 2 1 j −1 j +1 J as γ but of length one less than γ . Since this is the form of any cellular string s j j satisfying s < s and dim s = dim s + 1, the result follows. Let s be an L-dimensional cellular string. Successively replacing an X adjacent to a bit (0 or 1) by that bit yields a chain of strings s = s > s > ··· > s > s .It L L−1 1 0 follows that every maximal chain in the poset has length L. Example 2.10 Consider a string s(n) = σ 0X ··· X1σ with a block of n consecutive 1 2 X’s (where σ and σ are ﬁxed substrings). Let Str/s(n) denote the sub-poset of Str 1 2 consisting of all strings s ≤ s(n) which begin in σ 0 and end in 1σ . Then Str/s(n) 1 2 is isomorphic to the poset I of integer intervals [i , j ] with 1 ≤ i ≤ j ≤ n + 1. (The string corresponding to [i , j ] is σ 0 ··· 0X ··· X1 ··· 1σ ; 1 2 st it has i 0’s and the ﬁrst 1 is in the ( j + 1) spot.) If s is a cellular string with k blocks of successive X’s (of lengths n ,..., n ), 1 k the sub-poset Str/s of strings s < s in Str is isomorphic to the product of posets Str/s(n ),..., Str/s(n ), i.e., to the poset 1 k I × ··· × I . n n 1 k 123 516 J. Cyranka et al. 2.3 The polytopes We now turn to identifying the polytopes of Theorem 1.3. Fix a 010 critical value sequence cv = z ,..., z as in Deﬁnition 2.3. To each d-dimensional cellular n n 1 K string s we assign a d-dimensional polytope T (s) in R ; T (s) will be a product of simplices. Let s = γ γ ··· γ be the canonical representation of a string s, as in Deﬁnition 2.7. 1 2 J Let n denote the length of the substring γ ,so N = n . j j j th • If γ is either 0 ··· 0or 1 ··· 1, and γ is the k block from the left involving 0 or j j 1, we set T (γ ) = {z } = (z ,..., z ). j k k k • If γ is a block X ··· X, then T (γ ) = (x ,..., x ) ∈ R :∞≥ x ≥ ··· ≥ x ≥ z . 1 1 n 1 n 1 j 1 • If γ is a block X ··· X, then T (γ ) = (x ,..., x ) ∈ R : z ≤ x ≤ ··· ≤ x ≤∞ . J 1 n k 1 n j 1 th • If γ is a block X ··· X (for 1 < j < J ), and γ is the k block from the left j j −1 involving 0 or 1, then T (γ ) = (x ,..., x ) ∈ R where j 1 n z ≤ x ≤ ··· ≤ x ≤ z if k is odd; k 1 n k+1 z ≥ x ≥ ··· ≥ x ≥ z if k is even. k 1 n k+1 • We deﬁne T (s) ⊂ R to be the concatenation: T (s) = T (γ γ ··· γ ) = T (γ ). 1 2 J j j =1 −1 Let P be a persistence diagram and z ∈ dgm (P). The component C (z) of data is the union of the T(s), where s ∈ Str and T (s) is deﬁned using the critical value sequence cv(z). This is clear from Deﬁnition 2.1. Since the critical value sequence is always assumed to be ﬁxed, we will suppress it in the notation. Example 2.11 Consider the case K = 3 and N = 5. If s = 01XX0, then (γ ,...,γ ) = (0, 1, XX , 0). So, (n , n , n , n ) = (1, 1, 2, 1) and hence 1 4 1 2 3 4 T (01XX0) = {z } × {z } × {(x , x ) : z ≥ x ≥ x ≥ z } × {z } 1 2 1 2 2 1 2 3 3 0 0 2 0 × × × . 123 Contractibility of a persistence map preimage 517 If s = X01X0, then (γ ,...,γ ,γ ) = (x , 0, 1, x , 0). So, (n , n , n , n , n ) = 1 4 5 1 2 3 4 5 (1, 1, 1, 1, 1) and hence { } { } { } T (X01X0) =[z , ∞) × z × z ×[z , z ]× z = [0, ∞) 1 1 2 3 2 3 0 0 1 0 × × × × 0 0 Similarly, T (X0100) =[z , ∞) × {z } × {z } × {z } × {z } = [0, ∞) × × × 1 1 2 3 3 0 0 × . Observe that X0100 < X01X0 and T (X0100) ⊂ T (X01X0). Let Poly denote the poset of polytopes in R under inclusion. By deﬁnition, T maps strings in Str to polytopes in Poly. Lemma 2.12 T : Str→ Poly is an injective poset morphism, and preserves greatest lower bounds. Proof Suppose that s < s and 1 + dim s = dim s.If s = γ ··· γ is the canonical 1 J form, then some γ has the form a ··· a (where a is 0 or 1), and s has the form s = γ ··· γ¯ X ··· γ or s = γ ··· X γ¯ γ , 1 1 j J 2 1 j J where γ¯ = a ··· a has one fewer bit that γ . It is clear from the deﬁnition of T that j j T (s ) = T (s ), and T (s ) is the intersection of T (s ) and T (s ), as desired. 1 2 1 2 2.4 Geometric realization of posets Let C be a poset (partially ordered set). For any c ∈ C, we write C /c for the sub-poset c : c ≤ c ; C is the union of the C /c.If c and c have a greatest lower bound c , 1 2 12 then (C /c ) ∩ (C /c ) = C /c . 1 2 12 By deﬁnition, the geometric realization BC of any poset C is a simplicial complex whose k-dimensional simplices are indexed by the chains c < c < ··· c of length 0 1 k k in C. It is the union of the realizations B(C /c) of the sub-posets C /c;if c and c 1 2 have a greatest lower bound c , then B(C /c ) and B(C /c ) intersect in B(C /c ). 12 1 2 12 See Weibel (2013, IV.3.1) for more details. Here are some basic facts; see Weibel (2013, IV.3) for a discussion. A poset morphism f : C → C determines a continuous map BC → BC , and a natural transformation η : f f between morphisms gives a homotopy Bη : BC → BC between f and f . In addition, realization commutes with products: B(C × C ) 1 2 (BC ) × (BC ). Applying these considerations to the poset Str, we see that its real- 1 2 ization BStr is the union of the polytopes B(Str/s), and if s is the greatest lower bound of s and s then B(Str/s ) ∩ B(Str/s ) is B(Str/s ). 1 2 1 2 12 Let s be a cellular string. We saw in Example 2.10 that the poset Str/s is isomorphic to the product I × ··· × I of the posets I of integer intervals in [1, n + 1], n n n j 1 k j corresponding to the blocks of n succesive X ’s in s. It is well known that B(I ) is j n homeomorphic to the n-simplex . Thus n n ∼ ∼ 1 k B(Str/s) = B(I ) = × ··· × . 123 518 J. Cyranka et al. By construction, T (s) = T (γ ) also has this form. Hence we have a natural home- omorphism ∼ ∼ ∼ B(Str/s) = B(Str/s(n )) = B(I ) = T (γ ) = T (s). j n j Theorem 2.13 BStr is homeomorphic to C (z). Proof By construction, C (z) = T (s), and BStr = B(Str/s). It sufﬁces to observe that for each s ,..., s the restriction of the BStr/s = T (s ) induces a homeomor- 1 n i i phism between the intersection of the B(Str/s ) and the intersection T (s ). This holds i i because the two sides are identiﬁed with B(Str/s ) and T (s ), where s is the greatest lower bound of the s . 3 Contractibility We now deﬁne a poset morphism F : Str → Str, and modify it to deﬁne poset () () morphisms F : Str → Str for > 1. Deﬁnition 3.1 Let s be an L-dimensional cellular string. We deﬁne F (s) to be the string obtained from s by transposing the ﬁrst (i.e., leftmost) X with the bit immediately preceding it. If X is the initial symbol, we set F (s) = s. If s is a lower-dimensional cellular string, we deﬁne F (s) as follows. If s has an initial X with no 00 or 11 preceding it, we do as before: transpose X with the bit immediately preceding it, or do nothing if X is the initial symbol. If s begins with a block of n + 1 zeroes, say s = 00 ··· 0σ , we replace the initial 0 by X,so F (s) = X0 ··· 0σ . Otherwise, the string must have the form s = σ abbσ , where 1 2 1 2 a, b are bits, a = b, σ is an (alternating) bitstring not ending in a, and σ is the 1 2 remainder of the string. We set F (s ) = σ aabσ . 1 1 2 () () The deﬁnition of F : Str → Str mimics that of F . Speciﬁcally, if s = βσ , where β = X ··· X is a block of length − 1 then F (s) = β F (σ ). Example 3.2 In Fig. 2,the map F sends strings surrounded by rectangles (resp., ellipses) from one column to strings surrounded by rectangles (resp., ellipses) in the second column to the right, while leaving the last column ﬁxed. Thus F (01100) = 00100 and F (00100) = X0100. (2) Since Str is the rightmost column, the map F acts on this column, mapping strings surrounded by rectangles (resp., ellipses) to those two rows down. Thus F (XX010) = XX010, F (X0010) = XX010, and F (XX010) = XX010. 2 2 2 Lemma 3.3 F :Str→ Str is a poset morphism, and is the identity on the sub-poset (2) Str . K (2) Furthermore, F (Str) = Str . 123 Contractibility of a persistence map preimage 519 Proof We proceed by downward induction on d = dim(s) to show that if s < s then F (s ) ≤ F (s).If s contains an x with no 00 or 11 preceeding it, the same is true for 1 1 s and the inequality is evident. Next, suppose that s = σ abb ··· bσ , where σ a is an alternating bitstring. If 1 2 1 s = σ abb ··· bσ for some σ ≤ σ then 1 2 2 2 F (s ) = σ aab ··· bσ < F (s) = σ aab ··· bσ . 1 2 1 For s = σ aXb ··· and s = σ ab ··· bX σ ,wealsohave F (s )< F (s ) and 1 1 2 1 2 1 F (s )< F (s ). Otherwise, either s < s or s < s; in these cases, F (s ) ≤ F (s) or 2 1 2 1 1 1 F (s ) ≤ F (s), by induction, and hence F (s )< F (s). 1 2 1 Finally, if s = 00 ··· 0σ then either s = X0 ··· 0σ ≤ s or else s = 00 ··· 0X σ ≤ 1 2 s. By induction, F (s ) ≤ F (s) or F (s ) ≤ F (s), so it sufﬁces to observe that 1 1 1 1 2 1 F (s ) ≤ F (s ), F (s ). 1 1 1 1 2 Remark 3.4 The proof of Lemma 3.3 also shows that each F is a poset morphism. (2) We can ﬁlter the poset Str by sub-posets Fil , where Fil = Str , Fil = Str and i 0 K (2) Fil is the full poset on the set of strings s with F (s) ⊂ Str .InFig. 2, for example, Fil (resp., Fil ) is the rightmost 3 columns (resp., 5 columns). Since F maps Fil 1 2 1 i to Fil , the geometric realization of BF restricts to a continuous map from BFil i −1 1 i to BFil . We will prove: i −1 Proposition 3.5 The inclusions B Fil ⊆ BFil are homotopy equivalences. Hence i −1 i (2) BStr ⊆ BStr is a homotopy equivalence. Proof For i > 0, we deﬁne poset morphisms F : Fil → Fil ⊆ Fil to be the 1,i i i −1 i identity on Fil and F otherwise. The geometric realization of F is a continuous i −1 1 1,i map BFil → BFil ⊆ BFil which is the identity on BFil . i i −1 i i −1 We will prove that, on geometric realization, BF is homotopic to the identity on 1,i BFil . We deﬁne a poset morphism h : Fil → Fil as follows. If s ∈ Fil then i i i −1 h(s) = s;if s ∈ / Fil , deﬁne h(s) to be the greatest lower bound of s and F (s). i −1 1 Thus Bh is a continuous map from BFil to itself. For s ∈ Fil , the inequalities i i s ≥ h(s) ≤ F (s) yield natural transformations id ⇐h F . and hence homotopies 1,i i 1 between the maps id (the identity map on BFil ), Bh and BF . i i 1,i (+1) () Corollary 3.6 Each BStr ⊂ BStr is a homotopy equivalence. In particular, (L+1) the inclusion of the point BStr in BStr is a homotopy equivalence, i.e., BStr is contractible. Remark 3.7 We can describe the map T (s) → T (F (s)) induced by F . For example, 1 1 suppose that s = σ γ γ σ , where σ = γ ··· γ is an alternating bitstring of 1 j −1 j 2 1 1 j −1 length ≥ 2 and γ is a block X ··· X. Then T (γ ) ={z } and T (γ ) ⊂ R j j −1 j −1 j is deﬁned by inequalities, either z ≤ x ··· or z ≥ x ··· , depending on the j −1 1 j −1 1 parity of j.The map F sends T (γ ) × T (γ ) to the subset 1 j −1 j T (X ) ×{z }× T (γ ), j −1 123 520 J. Cyranka et al. where T (X ) is deﬁned by z ≤ x ≤ z and T (γ ) is deﬁned by the equations j −2 1 j −1 z ≤ x ··· or z ≥ x ··· . In effect, the map sends x to z . j −1 2 j −2 1 1 j −1 4 Existence of ﬁxed points for ﬂows As an application of Theorem 1.3, we establish the existence of a ﬁxed point solution of a ordinary differential equation whose trajectories are being observed in the space of persistence diagrams. To be more precise consider a differential equation z ˙ = f (z), z ∈ R , with the property that it possesses a compact global attractor A (Raugel 2002). Given an initial condition z(0) =¯z ∈ R , we write z(t ) = ϕ(t , z ¯), t ∈[0, ∞) for the solution in forward time. The important consequence of the existence of a compact global attractor is that there exists R > 0 such that for any initial condition z ¯ there exists t > 0 such that ϕ(t , z ¯) < R for all t ≥ t . We say that R is a z ¯ z ¯ bound for A. Observing the persistence diagrams along a trajectory results in a curve Dgm(ϕ(t , z ¯)) ∈ Per. In what follows we do not assume that we have knowledge of the nonlinearity of f , or of the actual trajectories ϕ(t , z); we are only given the curves Dgm(ϕ(t , z ¯)) of persistence diagrams. Even if the persistence diagram is constant, we cannot conclude that the underlying differential equation has a ﬁxed point. As an example, consider a differential equation in R with a periodic solution in which the ﬁrst coordinate z = 0 is constant, and (z , z ) oscillates with the property that 1 ≤ z ≤ z . The associated curve in Per 2 3 2 3 consists of the constant persistence diagram P = {(0, ∞)}. However, Theorem 4.3 provides a scenario under which the observation of suf- ﬁciently many trajectories suggests the existence of a ﬁxed point for the unknown ordinary differential equation that generates the dynamics. More general theorems are possible and, as will be discussed in a later paper, these techniques can be lifted to the setting of partial differential equations deﬁned on bounded intervals. The purpose of this example is to emphasize the importance of Theorem 1.3 from the perspective of data analysis. Thus, we focus on a much more modest result. We will show that if a particular type of neighborhood in Per is positively invariant under the dynamics, i.e. if Dgm(z) is in the neighborhood implies that Dgm(ϕ(t , z)) is in the neighborhood for all t > 0, then there exists a ﬁxed point for the differential equation that generates the dynamics. To state and obtain such a result requires the introduction of additional notation. Deﬁnition 4.1 We shall say that a persistence diagram b d P = p = (p , p ) : m = 1,..., M m m is sparse if each persistence point is unique, i.e. p = p for all m = n. m n Given a sparse persistence diagram we can choose μ> 0 such that p − p ≥ m n ∞ d b 4μ for all m = n and | p − p |≥ 4μ for all m. m m Example 4.2 A sparse persistence diagram Q is shown in Fig. 3. We can choose μ = 0.25. A possible critical value sequence associated to Q is cv(z) = (3, 4.5, 1, 3.5, 2). 123 Contractibility of a persistence map preimage 521 Fig. 3 A sparse persistence diagram Q with persistence points {(1, ∞), (2, 3.5), (3, 4.5)}.The boxes indicate the set N for μ = 0.25 We use μ to deﬁne subsets of R and Per. We begin by constructing a subset of R using the set of cellular strings Str(N , M ). Choose a point z ˆ with persistence diagram P. This gives rise to a ﬁxed critical value sequence cv(z ˆ) and the associated component C (z ˆ) ⊂ R of data is given by C (z ˆ) = T (s). s∈Str(N ,M ) By Theorem 1.3, C (z ˆ) is a contractible union of polytopes. Let B (C (z ˆ)) ⊂ R be the set of points that lie within a distance μ of C (z ˆ) using the sup-norm. The bound on the choice of μ guarantees that if s , s ∈ Str(N , M ) are of maximal dimension and there does not exist s ∈ Str(N , M ) such that s < s and s < s , then B (T (s )) and B (T (s )) are disjoint. Therefore B (C (z ˆ)) is contractible. μ μ μ We now turn to the subset of Per. For each m = 1,..., M set b d P := p = (p , p ) :p − p ≤ μ m m 1 and b d b b d b D := p = (p , p ) : p ∈[ p − μ, R] and 0 ≤ p − p ≤ μ for some R > sup{ p }+ μ. See Fig. 3. Deﬁne N ⊂ Per to be the set of persistence diagrams generated by elements of R with the property that for each m = 1,..., M there exists a unique persistence point in P and any other persistence points lie in D. These constructions allow us to prove the following theorem concerning the exis- tence of ﬁxed points of the unknown, underlying dynamical system ϕ. Theorem 4.3 Consider a dynamical system generated by an ordinary differential equa- tion that has a global compact attractor A with a bound R, and whose trajectories 123 522 J. Cyranka et al. are represented by ϕ(t , z). Let P be a sparse persistence diagram and let N ⊂ Per be deﬁned as above. Assume that if Dgm(z) ∈ N , then Dgm(ϕ(t , z)) ∈ N for all P P t ≥ 0. −1 N Then, for each component of Dgm (N ) ⊂ R there exists a vector z ˆ such that Dgm(z ˆ) ∈ N and ϕ(t , z ˆ) =ˆz for all t ∈ R, i.e. z ˆ is a ﬁxed point for the dynamical system. Proof We begin with the observation that if z ∈ B (C (z ˆ)) and there exists t > 0 such μ 1 that ϕ(t , z)/ ∈ B (C (z ˆ)), then there exists t ∈ (0, t ] such that Dgm(ϕ(t , z)) ∈ / N . 1 μ 0 1 0 P This follows from the stability theorem of persistent homology using the bottleneck distance (Cohen-Steiner et al. 2007). This contradicts the hypothesis, therefore, that B (C (z ˆ)) is a contractible, positively invariant region under the dynamics. By McCord and Mischaikow (1996, Proposition 3.1) the Conley index of the maximal invariant set is that of a hyperbolic attracting ﬁxed point. By McCord (1988, Corollary 5.8) (which utilizes the well known Lefschetz ﬁxed point theorem), the maximal invariant set in B (C (z ˆ)) contains a ﬁxed point. 5 Conclusion and future work Recall from Remark 2.6 that Curry (2018) provides a count of the contractible compo- nents of the preimage of a persistence map. However, to the best of our knowledge, this paper provides the ﬁrst detailed analysis of the homotopy type of these of a compo- nents. Although we have presented the results in the context of sublevel set ﬁltrations, the same arguments can be applied in the setting of superlevel set ﬁltrations. The only signiﬁcant change is that one needs to use 101 cellular strings; see Deﬁnitions 2.3 and 2.7. Theorem 4.3, and the use of persistence diagrams to obtain results about the dynam- ics of an ODE, may appear somewhat artiﬁcial. However, consider a PDE, such as a reaction diffusion equation, deﬁned on an interval. A ﬁnite spatial sampling of the solution at a time point gives rise to a vector. We can think of this vector as arising from two different proceedures: (i) numerical, e.g. the values of an ODE derived from a Galerkin approximation to the PDE, or (ii) experimental, e.g. a pixelated image of the solution. Theorem 4.3 is applicable in both cases, and one expects that for ﬁne enough discretization or resolution that the results of Theorem 4.3 will be applicable to the PDE. The example involving images brings us much closer to current treatments of complex spatio-temporal dynamics (Kramar et al. 2016; Levanger et al. 2019). Hence, the natural next step in our research is to obtain an analogous result about existence of ﬁxed points for one-dimensional PDEs whose trajectories are observed in the persistence space. Finally, the obvious open question as a result of this paper is: given a d-dimensional simplicial complex S with a function f , similar in form to that of Deﬁnition 1.1, can one determine the homology of components of the pre-image of a persistence diagram? Acknowledgements The work of JC and KM was partially supported by Grants NSF-DMS-1125174, 1248071, 1521771 and a DARPA contract HR0011-16-2-0033. CW was supported by NSF grants 1702233 and 2001417. In addition KM was partially supported by DARPA contract FA8750-17-C- 123 Contractibility of a persistence map preimage 523 0054, NIH Grant R01 GM126555-01, and NSF Grants 1934924, 1839294, 1622401, and the NSF HDR TRIPODS award CCF-1934924. In addition JC was partially supported by NAWA Polish Returns Grant PPN/PPO/2018/1/00029. The ﬁrst two authors are grateful to an anonymous reviewer of a dramatically different version of this paper for suggesting the relation of our efforts to K -theory, which greatly simpliﬁed the proof of Theorem 1.3. Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/. References Chazal, F., de Silva, V., Glisse, M., Oudot, S.: The Structure and Stability of Persistence Modules. Springer Briefs in Mathematics. Springer International Publishing AG Switzerland (2016) Cohen-Steiner, D., Edelsbrunner, H., Harer, J.: Stability of persistence diagrams. Discret. Comput. Geom. 37(1), 103–120 (2007) Curry, J.: The ﬁber of the persistence map for functions on the interval. J. Appl. Comput. Topol. 2, 301–321 (2018) Edelsbrunner, H., Harer, J.: Computational Topology. American Mathematical Society, Providence (2010) Kramar, M., Levanger, R., Tithof, J., Suri, B., Xu, M., Paul, M., Schatz, M.F., Mischaikow, K.: Analysis of Kolmogorov ﬂow and Rayleigh–Benard convection using persistent homology. Phys. D-Nonlinear Phenom. 334, 82–98 (2016) Levanger, R., Xu, M., Cyranka, J., Schatz, M.F., Mischaikow, K., Paul, M.R.: Correlations between the lead- ing Lyapunov vector and pattern defects for chaotic Rayleigh–Benard convection. Chaos: Interdiscip. J. Nonlinear Sci. 29(5), 053103 (2019) McCord, C.: Mappings and homological properties in the Conley index theory. Ergod. Theory Dynam. Syst. 8*(Charles Conley Memorial Issue), 175–198 (1988) McCord, C., Mischaikow, K.: On the global dynamics of attractors for scalar delay equations. J. Am. Math. Soc. 9(4), 1095–1133 (1996) Oudot, S.Y.: Persistence Theory: From Quiver Representations to Data Analysis. Mathematical Surveys and Monographs, vol. 209. American Mathematical Society, Providence (2015) Raugel, G.: Global attractors in partial differential equations. In: Fiedler, B. (ed.) Handbook of dynamical systems, vol. 2, pp. 885–982. North-Holland, Amsterdam (2002) Weibel, C.A.: The K -book. Graduate Studies in Mathematics, vol. 145. American Mathematical Society, Providence (2013). An introduction to algebraic K -theory Zomorodian, A., Carlsson, G.: Computing persistent homology. Discret. Comput. Geom. 33(2), 249–274 (2005) Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional afﬁliations.

Journal of Applied and Computational Topology – Springer Journals

**Published: ** Dec 28, 2020

Loading...

You can share this free article with as many people as you like with the url below! We hope you enjoy this feature!

Read and print from thousands of top scholarly journals.

System error. Please try again!

Already have an account? Log in

Bookmark this article. You can see your Bookmarks on your DeepDyve Library.

To save an article, **log in** first, or **sign up** for a DeepDyve account if you don’t already have one.

Copy and paste the desired citation format or use the link below to download a file formatted for EndNote

Access the full text.

Sign up today, get DeepDyve free for 14 days.

All DeepDyve websites use cookies to improve your online experience. They were placed on your computer when you launched this website. You can change your cookie settings through your browser.