An entropy-based persistence barcode

An entropy-based persistence barcode $ Harish Chintakunta a , Thanos Gentimis a , Rocio Gonzalez-Diaz b, n , Maria-Jose Jimenez b , Hamid Krim a a ECE Dept., NCSU, Raleigh, NC USA b Applied Math Dept., School of Computer Engineering, U. Seville, Spain article info Article history: Received 1 October 2013 Received in revised form 27 June 2014 Accepted 28 June 2014 Available online 8 July 2014 Keywords: Persistent homology Persistence barcodes Hasse diagram Simplicial complexes Entropy Filtration Filter abstract In persistent homology, the persistence barcode encodes pairs of simplices meaning birth and death of homology classes. Persistence barcodes depend on the ordering of the simplices (called a filter) of the given simplicial complex. In this paper, we define the notion of “minimal”barcodes in terms of entropy. Starting from a given filtration of a simplicial complex K, an algorithm for computing a “proper”filter (a total ordering of the simplices preserving the partial ordering imposed by the filtration as well as achieving a persistence barcode with small entropy) is detailed, by way of computation, and subsequent modification, of maximum matchings on subgraphs of the Hasse diagram associated to K. Examples demonstrating the utility of computing such a proper ordering on the simplices are given. 1. Introduction In recent years persistent homology has successfully been used to characterize topological properties of given sets and structures [10]. Persistence and ZigZag barcodes [3] have helped identify characteristic properties of the underlying space in data mining, network coverage and social networks. The theory of persistence has proven to be robust and invariant under small perturbations of the original state of the data. The algebraic structure of the set of persistence barcodes viewed as a module is well understood [27], and various stability theorems are proven in [4] when the space is equipped with the Wasserstein distance. In particular, it is proven that the persistence barcode is stable under “noise”that is, small changes in the function used to create a filtration to compute persistent homology imply only small changes in the persistence barcode. It is obvious that a persistence barcode depends heavily on the filter considered for such computation. An “interval”in a persistence barcode representation is a horizontal line segment in a plane whose length is equal to the lifespan of the corresponding homology class. A typical persistence barcode contains short-lived intervals representing topological holes (homology classes) which may not represent real features of the space being analyzed. In such cases one has to set a “threshold”of significance on the length of the intervals of the persistence barcode, and this is normally carried out a posteriori (see, for example, [14] where authors consider a “simplified”barcode). On the other hand, if someone examines in depth typical cases where persistent homology is used, one will be faced with the inherent problem of “noise” in the persistence barcodes. A similar problem was posed in [6,12] where various algorithmic results were presented. Those problems take the form of non-significant topological holes in sensor networks and inefficiencies of the filtration coming from the construction of the Rips (or Čech) complex in data sets. Motivated by practical applications of persistent homology computation, our starting point is a given simplicial complex and an initial filtration. Although the total number of intervals in a persistence barcode remains invariant (as we will see later), the lengths of its intervals depend on the selected filter. Since nonsignificant intervals (i.e., intervals with short length) may not imply relevant homological information, we are interested in looking for a filter which preserves the partial ordering imposed by the given filtration, in order to minimize the number of significant intervals and maximize their lengths. From an information-theoretic viewpoint, and if we interpret the number of significant intervals as the coding length of a complex, our goal is to select the most “parsimonious”representation (also by Occam's razor principle). As is also well known, the coding length is intimately related to the notion of entropy (i.e., a ☆ Authors partially supported under Grant No. MTM2012-32706, DTRA Grant No. HDTRA1-08-1-0024, and NSF Grant No. CCF-1217874. n Corresponding author. E-mail addresses: [email protected] (H. Chintakunta), [email protected] (T. Gentimis), [email protected] (R. Gonzalez-Diaz), ma[email protected] (M.-J. Jimenez), [email protected] (H. Krim). topological entropy of the barcodes in our case). While one would ideally want to balance the minimization with a penalty term of the number of non-significant intervals [18], further knowledge of statistical distribution of the long intervals is required and postponed to future work. This paper completes the work proposed in [12] by providing additional insights, examples, results and proofs. A new definition of “minimal barcode”is given using the notion of entropy, and an algorithm for computing persistence barcodes with small entropy starting from a given filtration is provided. The remainder of this paper is organized as follows. Section 2 covers the relevant background material. In Section 3, we give the definition of minimal barcodes based on the notion of entropy. In Section 4, an algorithm for computing a filter which preserves the partial ordering imposed by the filtration and whose associated persistence barcode has small entropy, is computed on the Hasse diagram of the poset of faces of a given complex. Section 5 is devoted to relations between minimal barcodes and discrete Morse theory. Conclusions and future work are presented in Section 6. 2. Preliminaries Homology theory uses algebraic groups to encode the topological structure of a simplicial complex K. In general, we will always consider connected, finite simplicial complexes K(i.e., with m simplices, mo1) unless stated otherwise. 2.1. Homology The set of i-simplices, σ i (superscript denotes dimension), will be denoted by K i . The number of simplices in a set Sis denoted by jSj. The dimension of the simplicial complex is nZ0ifK n a∅and K m ¼∅;8m4n. Finite formal sums of simplices of K i with coefficients in a field (called i-chains), define an additive Abelian group structure on K i . In our case, the coefficients for those sums belong to Z 2 thus the group of i-chains, C i ðK;Z 2 Þis a vector space over Z 2 with basis elements the simplices of dimension i. If a simplex σ is a face of another simplex σ 0 , we write σ!σ 0 . We say that σ 0 is a coface of σ .Aproper face of σAK i , is a face of σ of dimension i1. The boundary of σ , denoted by ∂ðσÞis the formal sum (with coefficients in Z 2 ) of the proper faces of σ . The boundary operator is extended to all chains of Kby linearity. An i-chain ais an i-cycle if ∂ i ðaÞ¼0 i.e., aAKer ∂ i ;itisan i-boundary if there is an (iþ1)-chain bsuch that ∂ iþ1 ðbÞ¼ai.e., aAImð∂ iþ1 Þ. Two i-cycles aand a 0 are homologous if aþa 0 is an i-boundary. Since ∂ i ∂ iþ1 ¼0, Imð∂ iþ1 ÞDKer ∂ i . The quotient of i-cycles over i-boundaries is the i-th homology group of K i.e., H i ðKÞ¼Kerð∂ i Þ=Imð∂ iþ1 Þ. The elements of H i (K) are called homology classes. Since the considered field of coefficients is Z 2 , the i-th Betti number (denoted by β i ) is the rank of the i-th homology group of K. Then, the basic topological structure of Kis quantified by the number of independent classes in each homology group. See [25,15]. Given a simplicial complex K, a nested sequence of simplicial complexes ∅¼K 0 K 1 ⋯K p1 K p ¼K is called a filtration of K. An ordering of the simplices of a simplicial complex K¼f σ 1 ;…;σ m gis called a filter if it satisfies the property that sotwhenever σ s !σ t . Then we can create a filtration by setting: K t ¼fσ 1 ;…;σ t g;for 1rtrm: 2.2. Metric filtrations Many applications of Computational Topology start with a cloud of points embedded in R n . Using a specific radius rone can then define Alpha-complexes A(r), Čech complexes C(r), and Rips-complexes R(r). Furthermore, one can obtain a filtration ∅¼K 0 K 1 ⋯K p1 K p ¼K by gradually increasing rwhere K i is Aðr i Þ,Cðr i Þor Aðr i Þdepending on the complex Kwe are creating (Alpha, Čech or Rips-complex) and r i or j if ioj(see [7, page 70] and [10]). In particular, all vertices enter at K 0 , and K t and K tþ1 differ by at least one simplex. 2.3. Lower-star filtrations In lecture 11 of their course 1 in computational geometry and topology, Edelsbrunner and Kerber argue that if we choose a reasonable filtration, we can learn more about a complex than just analyzing its Betti numbers. They propose the creation of a filtration given some function on the vertices. Examples of these are the grayscale value of images, or height information in geographical data. Let Kbe a simplicial complex with distinct real values specified at their vertices h:K 0 -R. We can then order the vertices by an increasing function value as hðv 1 Þo⋯ohðv m 0 Þwhere m 0 ¼jK 0 j. Each simplex σ has a unique maximum vertex v max , i.e., hðv max Þ¼maxfhðvÞ:vAK 0 and v!σg The lower star filtration of h [7, Section VI.3] is the nested sequence of complexes ∅¼K 0 K 1 ⋯K m 0 ¼Ksuch that: K t \K t1 ¼fσAK:maximum vertex of σis v t g In particular, K t and K tþ1 differ by at least one simplex since each simplex has a unique maximum vertex. 2.4. Persistent homology Persistent homology [6,27] studies homology classes and their “lifetimes”(persistence) along a nested sequence of objects (simplicial complexes in our case). Given a filter of K, the algorithm for computing persistence barcodes that appears in [6], marks an i-simplex σ t as positive (birth) if it belongs to an i-cycle in K t ¼fσ 1 ;…;σ t g(i.e., σ t creates a new homology class at time t) and negative (death) otherwise (i.e., σ t destroys a homology class created at some time sfor 0rsot). Given a filter fσ 1 ;…;σ m g,apersistence barcode [3] is a graphical representation of pairs of birth and death times, as a collection of horizontal line segments (intervals) in a plane. If a simplex σ s creates a homology class at time s(the index in the filter) which is destroyed at time t,0rsotrm, then the interval ½s;tÞis added to the corresponding persistence barcode. If a simplex σ s ,0rsrm creates a homology class at time swhich survives along the process, then the interval ½s;1Þ is added to the persistence barcode. For a fixed i, the i-barcode is the set of intervals of a given persistence barcode corresponding to the pairs of positive i-simplices and negative (iþ1)-simplices of K. See [3]. The following lemma holds. Lemma 1. Independent of the selected filter of a simplicial complex K, the number of intervals in an i-barcode, 0rirn, is β i þ∑ n j¼iþ1 ð1Þ iþ1j ðjK j jβ j Þ; 1 http://www.pub.ist.ac.at/courses/2012/computationalgeometryandtopology/ Lectures/Lecture-11.pdf where jK j jis the number of j-simplices in K and n is the dimension of K. Proof. Notice first that, the number of intervals of infinite length in the i-barcode is independent of the filter since it coincides with the i-th Betti number of K, β i . Furthermore, recall that each i-simplex σ i t in the given filter, 0rtrm, is marked as positive or negative. No simplex can remain unmarked after the whole process. Therefore, counting the number of finite intervals in an i-barcode, is equivalent to counting the number of negative ðiþ1Þ simplices. Let b i (resp. d i ) be the number of positive (resp. negative) i-simplices. We then have that d 0 ¼d nþ1 ¼0; and jK i j¼b i þd i and β i ¼b i d iþ1 , for 0rirn(see [5]). Hence d n ¼jK n jb n ¼jK n jβ n and by induction, we have: d i ¼jK i jb i ¼jK i jβ i d iþ1 ¼jK i jβ i ∑ n j¼iþ1 ð1Þ iþ1j ðjK j jβ j Þ¼ ∑ n j¼i ð1Þ ij ðjK j jβ j Þ:□ In addition, since d 0 ¼0 we have that ∑ n j¼0 ð1Þ j ðjK j jβ j Þ¼0, which yields the known expression for the Euler characteristic [5, page 777]: χðKÞ¼ ∑ n j¼0 ð1Þ j jK j j¼ ∑ n j¼0 ð1Þ j β j : 3. Minimal barcodes Our general aim is to find, under some constraints depending on the nature of the application, filters that minimize the number of long-life homological classes which are associated with significant intervals in the persistence barcodes. A “minimality”in the construction of these persistence barcodes is needed since the ultimate goal is to be able to use them to compare two different topological spaces, for example simplicial complexes Xand Y coming from grayscale images [19]. If there is no “uniform”way of constructing a filter, we may end up having similar persistence barcodes describing completely different spaces. In this paper our starting point is a given filtration of a simplicial complex K, and our aim is to find a “proper”filter preserving the partial ordering imposed by the filtration trying to answer the following question: If we have a shape in 3D, which filtration should we choose for persistent homology computation? The example shown in Fig. 1 of a conical shape with “empty bottom”demonstrates the importance of choosing the appropriate filtration. If we choose an ordering of the vertices using the function F1, and obtain the lower-star filtration, then no holes appear throughout the process. On the other hand, if we choose an ordering of the vertices using F2 and the lower-star filtration, then a hole survives until the last vertex on the top is added, and we thereby unveil much more information about the 3D shape. We first rigorously formulate a notion of minimality. Consider that a simplicial complex Kof dimension nwith mþ1 simplices, is given. 3.1. Entropy of a persistence barcode A general idea in the study of topological persistence is that significant topological attributes must have long life-times, and topological features with short life-times are considered to be “noise”. Following this idea, a notion of k-significant intervals was introduced in [12]: Fix k40, an interval ½s;tÞis k-significant if kots. Persistence barcodes associated to different filters of Kcan be compared by the amount of k-significant intervals they contain. Another form of comparison between persistence barcodes can be given in terms of entropy. To that end, we need a convention about intervals that persist to “infinity”: Remark 2. In persistent homology theory, intervals that extend all the way to the end of the filter are denoted by ½a;1Þ. In our case we denote them by ½a;mþ1Þ. This way all intervals have finite length. Definition 3. Given a filter Fand the corresponding persistence barcode B¼f½a j ;b j :jAJg,wedefine the entropy (Shannon entropy) of Fas EðFÞ¼∑ jAJ p j log ðp j Þð1Þ where p j ¼ℓ j =L,ℓ j ¼b j a j , and L¼∑ jAJ ℓ j . Observe that Formula (1) can also be written as EðFÞ¼log ðLÞ1 L∑ jAJ ℓ j log ðℓ j Þ: Remark 4. Since p j r1, then log ðp j Þr0 and the entropy of a filter (or barcode) is always positive. Intuitively, entropy measures how different bars of the barcodes are in length. A barcode with uniform lengths has small entropy. For example, consider the barcodes B1,B2 and B3 shown in Fig. 2 and the filters F1,F2 and F3 associated to them. We have that EðF1Þ¼2:198816406, EðF2Þ¼1:474560793 and EðF3Þ¼ 1:45962243. The upper bound of the entropy of a probability mass function pis given by log jpj, where jpjis the cardinality of the support set of p. The upper bound is achieved for a uniform distribution. In the definition of entropy of a barcode, we use the normalized sequence of lengths of the bars in place of the probability mass function. In order to meaningfully compare different barcodes using the entropy function, we need the support sets of the corresponding probability mass functions to have the same cardinality (number of intervals in the barcode). Lemma 1 establishes this fact. 3.2. Minimal barcodes and filtrations As stated in [7, page 149], the measurements of the scale or resolution of topological features using persistent homology make sense only if the function on the given simplicial complex does. This is the reason why we begin with a scenario in which a partial Fig. 1. Two orderings of the vertices for the same 3D shape using the functions F1 (increasing weight) and F2 (increasing height). ordering on the simplices of Kis given (derived, for example, from a metric or a lower-star filtration). We then define F K ¼fall filters on Krespecting the pre imposed partial orderingg Since in general there are many ways to construct a filter out of a collection of simplices satisfying the pre-imposed partial ordering, an important question arises as to which of these will result in a “minimal”barcode, and in what sense this is “minimal”? A notion of minimality using k-significant intervals is the following: Definition 5 (Rocio Gonzalez-Diaz et al. [12]). A persistence barcode associated with a filter FAF K is k-minimal if the persistence barcode associated with any other filter in F K contains greater or equal number of k-significant intervals. Though not unique, such a filter always exists since there are finitely many filters with a fixed set of original conditions on a finite simplicial complex. See Fig. 2 for examples of 1-minimal barcodes. The drawback of this definition is that it depends on determining the right integer k. So, another question arises, which integer kshould we choose? As before, it will depend on the nature of the application. However, this drawback may be entirely avoided by adopting an information theoretic definition as follows. Define an equivalence relation on F K : F 1 F 2 3EðF 1 Þ¼EðF 2 Þð2Þ or in other words two filters with the same entropy will be considered equivalent. Consider the set of equivalence classes ~ F K . The entropy function induces a partial ordering on this set as follows: EðFÞrEðF 0 Þ)FrF 0 : Definition 6. Afilter F min A~ F K is E- minimal if for any other filter FA~ F K we have F min rFaccording to the entropy ordering. We note that there is no direct relation between k-minimal and E-minimal barcodes since k-minimality minimizes the number of intervals with length greater than kwhile E-minimality looks for a barcode with short intervals being as short as possible and long intervals as long as possible. 4. Algorithm for computing persistence barcodes with small entropy Given a simplicial complex K, and a filtration ∅¼K 0 K 1 ⋯K p ¼K; our goal is to find a filter fσ 1 ;…;σ m gof Kwith associated persistence barcode having small entropy and satisfying the preimposed partial ordering on the simplices of Kgiven by the filtration. In order for our algorithm to work, we need the following result. Suppose that the length of all the intervals in a filter FðℓÞof Kis fixed except for one interval ½s;twith variable length ℓ. This variable ℓrepresents the different possibilities of inserting the simplices σ s and σ t in the filter. Therefore, ℓA½min;maxwhere 1rminrℓrmaxrm. Observe that ℓomþ1 since there always exists one interval with maximal length mþ1 (the interval representing the connected component of K). Lemma 7. The minimum value for EðFðℓÞÞ can be found in ℓ¼min or ℓ¼max. Proof. Varying ℓand fixing the rest of the parameters, the entropy EðFðℓÞÞ can be written as EðFðℓÞÞ ¼ log ðLþℓÞcþℓlog ðℓÞ Lþℓ; where Land care positive constants. The solution for the equation E 0 ðFðℓÞÞ ¼ 0isℓ¼e c=L . Furthermore, E″ðFðe c=L ÞÞo0. Therefore ℓ¼e c=L is a maximum. Consequently, the minimum values for EðFðℓÞÞ are obtained in ℓ¼min or ℓ¼max. □ Since lim ℓ-þ1 EðFðℓÞÞ ¼ 0, there always exists a positive value x4e c=L such that EðFðxÞÞoEðFðminÞÞ. Observe that if maxox, this value is not valid as a length of the interval. 4.1. Hasse diagrams The Hasse diagram H of Kis the graph whose node set is the set of simplices and whose arcs are the pairs ðσ;σ 0 Þif σ is a proper face of σ 0 . We draw the Hasse diagram in the plane in such a way that, Fig. 2. An example of three different persistence barcodes obtained from the same simplicial complex. Intervals corresponding to 0-barcodes are in blue. Intervals corresponding to 1-barcodes are in red. Top-right: barcode B1;down-left:barcodeB2; down-right: barcode B3.Thefilters can be read on the x-axis of each of the diagrams. For B1,itis F1¼fa;b;c;d;e;f;ab;ac;bd;cf ;de;ef ;bc;be;ce;abc;bde;cef g;ForB2,F2¼fb;c;bc;e;be;ec;a;ab;ac;abc;d;bd;de;bde;f;ef ;cf ;cef g;ForB3,F3¼fa;b;ab;c;ac;bc;abc;d;bd;e;bd;de; bde;f;ef ;cf ;ce;cef g. (For interpretation of the references to color in this figure caption, the reader is referred to the web version of this article.) if σ!σ 0 then σ is in a higher level than that of σ 0 . We thus get a multipartite graph where each level corresponds to the dimension of the simplices (see [9]). Given a filtration of a simplicial complex K, consider the subgraphs fH i g 1rirp of the Hasse diagram H generated by the simplices σAK i \K i1 . We thus could construct a function T:K-½0;msatisfying the following properties: (1) For σ;σ 0 in Ksuch that σ!σ 0 ,wehaveTðσÞoTðσ 0 Þ. (2) For any i, the entry times of simplices in H i will surjectively lie in a single closed interval in N. (3) Given two simplices σ;σ 0 AKsuch that σAK j and σ 0 AK i \K j for some joi,wehaveTðσÞoTðσ 0 Þ. For each σAK,TðσÞdenotes the entry time of σ . An order on the simplices of K,fσ 1 ;…;σ m gcan be given by Tðσ t Þ¼t. The first property on Tensures that fσ 1 ;…;σ m gis a valid filter of K, and the second property resembles that of consecutive labeling. The third property states that the order prescribed by the given filtration is preserved in the filter. 4.2. Algorithm Now, starting from a given filtration of a simplicial complex K, an algorithm for computing a “proper”filter (preserving the partial ordering imposed by the filtration as well as achieving a persistence barcode with small entropy) is detailed, using an adaptation of a maximum matching on the subgraphs H i associated to K. Fix i, let e i be the maximum level of the subgraph H i and let h i be the number of nodes of H i . Given a matching in H i between levels jand jþ1, let the completion number of a matched (jþ1)- simplex σ , denoted by cðσÞ, be the number of its proper faces each of which is matched to a (jþ1)-simplex. If σ is matched to a j-simplex, then cðσÞis at least 1. Algorithm 8. Assigning a time value to the simplices on each subgraph H i . 1: for each subgraph H i ,1rirpdo 2: set j¼0, t¼1 3: while joe i do 4: if there are no j-simplices in H i ,then 5: increment jby one 6: else 7: compute a maximum matching between levels jand jþ1inH i . 8: for each unmatched j-simplex σAH i do 9: remove σ from the subgraph H i 10: assign tðσÞ¼t 11: increment tby one. 12: end for 13: 14: while there are matched j-simplices in H i do 15: for each matched (jþ1)-simplices σ in H i do 16: compute cðσÞ 17: end for 18: if there is no matched (jþ1)-simplex σ with cðσÞ¼1then 19: find a (jþ1)-simplex μ with cðμÞmaximum 20: for the j-simplex σ matched with μ , assign tðσÞ¼t 21: unmatch μ 22: increment tby one 23: else 24: for each (jþ1)-simplex μ with cðμÞ¼1do 25: take the j-simplex σAH i matched to μ 26: remove σ and μ from the subgraph H i 27: assign tðσÞ¼tand tðμÞ¼tþ1 28: increment tby 2. 29: end for 30: end if 31: end while 32: end if 33: Increment jby one 34: end while 35: for each unmatched e i simplex σ of H i do 36: assign tðσÞ¼t 37: increment tby one 38: end for 39: end for Algorithm 8 has been implemented and can be downloaded from here. 2 At the termination of Algorithm 8, all simplices of H i , where 1rirp, will have been assigned a time value. Fig. 3 Now, to obtain an entry time function Tfor the whole Kwe proceed as follows: 1: for each σAKdo 2: find the index i,1rirp, such that σAH i \H i1 ; 3: TðσÞ¼tðσÞþ∑ i1 j¼1 h j . 4: end for Notice that the length of some intervals produced by the output filter is constrained by the order induced by the starting filtration. That is the case of the interval of length 8 in the example of Fig. 5, since the simplices b(birth of the corresponding homology class) and be (death of the homology class) belong to different subgraphs H 1 and H 2 and remain, respectively, unmatched. 4.3. Discussion of the algorithm This subsection presents the justification/correctness of Algorithm 8described in Section 4.2. The output of the algorithm is a filter built on any given filtration of K. In order to obtain a persistence barcode with small entropy, the idea is to try to “kill”any homology class as soon as possible, while still respecting the partial ordering prescribed on the simplices by the given filtration. Such a process will reduce the topological noise by keeping “unwanted”intervals as short as possible. In light of the result given in Lemma 7, the minimum entropy can be found when intervals have length as minimum as possible or as maximum as possible. Since our starting point is a preordering of the simplices given by the input filtration, we cannot ensure to achieve intervals with maximum lengths. This is why we look for intervals with minimum length. An easy way to obtain a filter from a given filtration of Kis by adding the simplices of K i \K i1 in order of their dimension. There is no prescribed order for simplices of equal dimension, and are considered to be added simultaneously. In this work, we show that choosing the right order for simplices in K i \K i1 is very useful in significantly improving the quality of the persistence barcode. Successive placements of simplices of each matching in the ordering serve to limit the length of the corresponding interval to one. This way, every interval of length 1 in the barcode will 2 http://www4.ncsu.edu/hkchinta/code.html Fig. 3. (a) (resp. (b), (c)) The histogram of the lengths of the barcode B1 (resp. B2,B3) shown in Fig. 2. Fig. 4. Example of execution of the algorithm to construct a filter, starting from a filtration ∅¼K 0 K 1 K 2 . Fig. 5. Persistence barcode associated to the filter provided in Fig. 4. correspond to a matching between two simplices of K i \K i1 , for some iand every interval of length greater than 1 will be associated to non-matched simplices. By construction, the output of the algorithm is an ordering on the simplices that is in fact a filter of Ksince properties (1), (2) and (3) enumerated in the introduction of this section are satisfied. By convention, we have the vertices of Kin the top row of the Hasse diagram H.Fixi,letH 0 i be the directed graph obtained from H i by pointing the matched edges down, and all other edges up. Update H 0 i atthesametimeasH 0 when running the algorithm. For a fixed jin the algorithm, let ðσ;σ 0 Þbe a matched pair of a j-simplex and a (jþ1)- simplex. The pair ðσ;σ 0 Þcan be “safely”added to the filter (preserving the simplicial structure) only when the completion number of σ 0 is equal to 1 due to the following results: Lemma 9. If there exists a directed cycle in H 0 i , then the ordering induced on the simplices by this matching is not a valid filter. Proof. Suppose there exists a directed cycle between levels jand jþ1. Let σ 1 ;σ 2 ;…;σ n be the nodes of the directed cycle. Suppose that σ 1 is a j-simplex and σ s is matched to σ sþ1 for sbeing odd. Observe that nmust be even, σ n1 matched to σ n and σ 1 !σ n . Then, σ n1 must precede σ n in the filter. Since σ 1 is matched to σ 2 , then σ 1 must precede σ 2 in the filter. If we iterate this procedure, we obtain that σ n must precede σ 1 and σ 2 but σ 1 !σ n ,so σ n cannot precede to σ 1 .□ The following theorem derives the condition (used in the algorithm) to identify the existence of such a directed cycle. Theorem 10. For fixed i and j, all the matched (jþ1)-simplices have completion number 41in H i if and only if there exists a directed cycle between levels j and jþ1in H 0 i . Proof. First, take any (jþ1)-simplex σ 2 matched to a j-simplex σ 1 such that cðσ 2 Þ41. Suppose that σ 2 is matched with a j-simplex σ 1 . Since cðσ 2 Þ41, there exists a j-simplex σ 3 connected to σ 2 and matched to a (jþ1)-simplex σ 4 . If we iterate this procedure, for some odd number s,aj-simplex σ s is matched to a (jþ1)-simplex σ sþ1 which is connected to the j-simplex σ 1 , creating the directed cycle. Finally, if there exists a directed cycle between levels jand jþ1inH 0 i then the completion number of the (jþ1)-simplices of the cycle is at least 2. □ Theorem 11. Given a filtration of a simplicial complex K, the entry time function T provides a filter of K respecting the partial ordering on the simplices of K given by the filtration. Proof. First, let σ be a j-simplex and σoσ 0 then TðσÞoTðσ 0 Þ(i.e., the ordering of the simplices of Kis a filter). The following cases can occur: 1. If σ is matched to σ 0 , then Tðσ 0 Þ¼TðσÞþ1 by construction. 2. If σ is not matched to σ 0 and σ;σ 0 AK i \K i1 , then σ;σ 0 are nodes of H i , so: 2.1. If cðσ 0 Þ¼0, then tðμÞotðσ 0 Þfor any j-simplex μ of H i ,soin particular tðσÞotðσ 0 Þand therefore TðσÞoTðσ 0 Þ. 2.2. If cðσ 0 Þ¼1, then σ 0 is not matched to any other (jþ1)- simplex, so tðσÞotðμÞfor any (jþ1)-simplex μAH i . In particular, tðσÞotðσ 0 Þand therefore TðσÞoTðσ 0 Þ. 3. If σAK i and σ 0 AK j \K i , for some ioj, then Tðσ 0 Þ¼tðσ 0 Þþ ∑ j1 s¼1 h s Z∑ i s¼1 h s ZTðσÞ: Second, the ordering of the simplices in the filter satisfies the partial ordering imposed by the given filtration by the same arguments as in point 3 above. □ Complexity of Algorithm 8 depends on the complexity of the algorithm selected to compute a maximum matching between consecutive levels in each Hasse diagram (see line 7 of Algorithm 8). The Hasse diagram is a bipartite graph, and in this case, the worst-case complexity of the classical algorithm for finding a maximum matching (Hopcroft–Karp algorithm) is Oðffiffiffiffiffiffiffi jVj pjEjÞ,wherejVjis the number of vertices between two consecutive levels, and Eis the number of edges. Apart from this, the rest of the algorithm runs in OðjVj 2 Þdue to the two for instructions inside the while loop. 4.4. Persistence barcodes with small entropy from lower-star filtrations In this subsection we will show using examples that given a lower-star filtration, the persistence barcode obtained using our algorithm has small entropy, and improves the barcode in the sense of “making short intervals very short and long intervals long”. Given a simplicial complex K, start with distinct real values specified at the vertices h:K 0 -R, which can be thought of as a set of “heights”. Construct the lower-star filtration, ∅¼K 0 K 1 ⋯ K m 0 ,ofK(where m 0 ¼jK 0 j) as explained in Section 2.3. Order the vertices by increasing function value as hðv 1 Þo⋯ohðv m 0 Þ where m 0 ¼jK 0 j. Construct the lower-star filtration, ∅¼K 0 K 1 ⋯K m 0 ; of K(where m 0 ¼jK 0 j) as explained in Section 2.3. For each simplex σAK, assign a height to σ which is equal to the maximum height on its faces. This way, a set of subgraphs fH i g 1rirm 0 of Hassociated with the lower-star filtration of K, can be constructed, where the nodes of H i are the simplices of Kwith height equal to hðv i Þfor each i. After applying the procedure explained in Section 4.2, an entry time function T:K-Nis obtained satisfying the pre-imposed partial ordering on the simplices of Kgiven by the lower-star filtration. Consider the example shown in Fig. 6. The barcodes for filters obtained using random ordering on the simplices in a lower-star filtration and using the algorithm presented here are shown in Figs. 7 and 8 respectively. The intervals corresponding to the 0-homology are shown in blue and the intervals corresponding to 1-homology are shown in red. Even though the homology of the complex is trivial, the ordering on the vertices causes at least one long interval for the first homology as seen in both cases. However, if the ordering on the other simplices is not chosen properly, the resulting barcode may have several other long bars as seen in Fig. 7. As another example, consider the simplicial complex shown in Fig. 9. Using the embedding in the plane, we consider the y-coordinate as the function on the vertices. Again, preserving the ordering on the vertices induced by this function, we obtain two filters, (1) using the algorithm presented here, and (2) using random ordering on the simplices. The resulting barcodes for the Fig. 6. The function value on a vertex v i is equal to i. The indices of other simplices are in the lexicographic order. first homology are shown in Fig. 9. The following observations are in order. (1) Both barcodes look similar, since we use same function on the vertices. (2) The lengths of the intervals in the barcode obtained using our algorithm are smaller than that obtained using random ordering on simplices with equal height. This is because we are optimizing the ordering. For this example, the entropy for the barcode obtained using our algorithm is 3.42 and that obtained using random ordering on simplices with equal height is 4.47. The two barcodes in the figure look very similar to each other due to scale. The difference is much clearer in Fig. 10(a), which compares the histograms of the lengths of the intervals for the two barcodes. We can make the following observations from Fig. 10(a): (1) For small values of kand k41, the number of k-significant intervals is larger for the barcode obtained using random ordering on simplices with equal height. (2) For large values of k, the number k-significant intervals is larger for the barcode obtained using our algorithm. (3) The above two points provide evidence for the fact that the barcode obtained using our algorithm minimizes the length of small intervals and maximizes the length of large intervals. Fig. 10(b) shows simulation results which further corroborates the effectiveness of the algorithm to produce barcodes with small entropies. The simplicial complexes considered in the experiments Fig. 7. Barcode obtained using lower-star filtration with arbitrary ordering on the simplices at any stage. Fig. 8. Barcode obtained using the algorithm presented in this paper. The simplicial complex considered 0 500 1000 1500 2000 2500 0 50 100 150 200 250 300 350 minimal bar code 0 500 1000 1500 2000 2500 0 50 100 150 200 250 300 350 bar code using lower star filtration Fig. 9. (a) The simplicial complex being considered, (b) barcode obtained from our algorithm, and (c) barcode obtained using random ordering. The y-axis represents the index of the simplices in the given filter. are random geometric complexes obtained from points on a plain. We generated 50 samples for each case of 100 points and 150 points, and created Rips complexes so that the underlying 1-skeleton has an average degree of 10 (these choices are arbitrary). The entropy for each sample complex was then computed, using the height function as a pre-ordering on the vertices, for the lower-star filtration and the filter obtained using the algorithm presented here. Since the upper bound for the entropy varies with the number of intervals Mas log(M), we normalize the entropies by log(M). In Fig. 10(b), the points in black are the entropies obtained for 100 points and those in red are entropies obtained for 150 points. The x-axis corresponds to entropy of lower star filtration (E ls ) and the y-axis to the entropy of the barcodes using our algorithm (E m ), which as seen, is lower. 5. In relation to discrete morse theory It is clear that our work in this paper resembles that of the computation of optimal discrete Morse functions. We clarify here the differences between both problems. Discrete Morse theory was developed by Forman in [8,9] as a combinatorial approach, on cell complexes, to Morse theory. Once a Morse function has been defined on a cell complex, then information about its topology can be deduced from its critical elements. A function, f:K-Ris a discrete Morse function if for every σAK,ftakes a value less than or equal to fðσÞon at most one coface of σ , or takes a value greater than or equal to fðσÞon at most one face of σ . A cell σ is critical if all of its cofaces take strictly greater values and all its faces are strictly lower. A cell which is not critical is called regular. A discrete vector field Vis a collection of pairs ðσ i !σ iþ1 Þof cells in Ksuch that each cell is in at most one pair of V. A discrete Morse function defines a discrete vector field by pairing σ i !σ iþ1 whenever fðσ i ÞZfðσ iþ1 Þ. The critical cells are precisely those which do not appear in any pair. Discrete vector fields which arise from Morse functions are called gradient vector fields.AV-path is a sequence of cells (of dimensions jand jþ1): σ j 0 ;σ jþ1 0 ;σ j 1 ;σ jþ1 1 ;…σ j r1 ;σ jþ1 r1 ;σ j r where ðσ j t ;σ jþ1 t ÞAV,σ j tþ1 !σ jþ1 t and σ j t aσ j tþ1 .AV-path is a nontrivial closed V-path if σ j r ¼σ j 0 for rZ1. Forman showed that a discrete vector field is the gradient vector field of a discrete Morse function if and only if there are no nontrivial closed V-paths, so a discrete Morse function can be computed from a partial matching in the Hasse diagram with no directed cycles. From this point of view, consider the final set of matchings computed in all the subgraphs H i through Algorithm 8 (removing the corresponding matching, as it is stated in the algorithm, when there is no matched (jþ1)-simplex σ with cðσÞ¼1). Then this matching provides a way to construct a discrete Morse function for a cell complex of arbitrary finite dimension. The nonexistence of directed cycles in the subgraphs H 0 i implies that there cannot be any directed cycle in the Hasse diagram of the whole complex. This is due to the fact that all the faces of a given cell σAH i for some i belong to ⋃ ℓ¼1…i H ℓ (because every K i in the filtration is a cell complex itself). So a cycle in Hcannot be decomposed in paths in different subgraphs H 0 i . There have been several works in the literature addressing the problem of obtaining optimal discrete Morse functions, with the minimum possible number of critical cells in each dimension (see for example [20,22,16,21]) and perfect Morse functions, for which the number of critical i-cells coincides with the i-th Betti number of the complex [1]. An optimal Morse function can be interpreted in terms of a maximum matching in the corresponding Hasse diagram with no directed cycles. We cannot guarantee optimality in the global Morse matching provided by our algorithm since (1) the partial order imposed by the filtration may constrain the possible matchings, forcing some simplices to be left unmatched (that is the case of simplices eand be in example of Fig. 4); (2) when a directed cycle is detected in our algorithm, we eliminate a matching, but perhaps an alternative maximum matching with no cycles could be found. Since maximal matching at each H i cannot generally guarantee optimality in entropy, this heuristic is acceptable. This is particularly reasonable, in light of the fact that determining an optimal Morse function is computationally expensive [20,16,2]. In general, optimal discrete Morse functions cannot yield minimal barcodes (in fact not even valid filters) as resulting matchings between different subgraphs H i , could violate the pre-imposed ordering of the vertices. Conversely, a set of matchings provided by a minimal barcode respecting a given filtration may not lead to an optimal discrete Morse function, since the matching may not even be maximal. Numerous papers addressed the computation of discrete Morse functions in different contexts, also trying to respect some filtration on the set of vertices. In [17], an algorithm is proposed to 510 15 20 25 30 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 length of a bar number of bars Minimal bar code lower star filtration 0 0.002 0.004 0.006 0.008 0.01 0.012 0.014 0.016 0 0.002 0.004 0.006 0.008 0.01 0.012 0.014 0.016 Entropy of Lower Star barcode (normalized) Entropy of minmal barcode (normalized) Fig. 10. (a) Comparison of the histograms of the lengths of the intervals in barcodes obtained from our algorithm to that obtained using random ordering on simplices with equal height. The y-axis (“number of bars”) represents the probability of the length of the bars in the corresponding barcode and (b) figures show a comparison of entropies of the barcodes obtained from the lower star filtration (E ls ) with that obtained using the algorithm presented here (E m ). All the points lie below the E m ¼E ls line demonstrating the algorithm produces barcodes with small entropies.