128 VI PersistenceVI.1 Persistent HomologyA main purpose of persistent homology is the measurement of the scale orresolution of a topological feature. There are two ingredients, one geometric,assigning a function to a space, the other algebraic, turning the function intomeasurements. The measurements make sense only if the function does. In thissection, we focus on the second step and simplify the scenario by substitutingan ordering of the simplices for the function.Filtrations. Let K be a simplicial complex. A filtration is a nested sequenceof subcomplexes,∅ = K0⊂ K1⊂ . . . ⊂ Kn= K.We may think of the filtration as a description of how to construct K byadding chunks at a time. We have seen an example is Section III.3 where weconstructed the Delaunay complex in a sequences of alpha complexes. Morethan in the sequence of complexes, we are interested in their topological evo-lution expressed by the corresponding sequence of homology groups. SinceKi−1⊂ Ki, the inclusion map defined by f (x) = x induces a homomorphismbetween the homology groups, f∗: Hp(Ki−1) → Hp(Ki). The nested sequenceof complexes thus corresponds to sequences of homology groups connected byhomomorphisms,0 = Hp(K0) → Hp(K1) → . . . → Hp(Kn) = Hp(K),one for each dimension p. The filtration defines a partial ordering on thesimplices with σ ∈ Ki−Ki−1preceding τ ∈ Kj−Kj−1if i < j. We can extendthis to a total ordering by deciding on the ordering of the simplices withineach Ki− Ki−1. We do this such that each simplex is preceded by its faces.Equivalently, we may assume that Ki− Ki−1consists of a single simplex, σi,for each i. In other words, the simplices of K are ordered as σ1, σ2, . . . , σnsuchthat Ki= {σ1, σ2, . . . , σi} for each 0 ≤ i ≤ n.Incremental algorithm. We consider the problem of updating the Bettinumbers while adding a single simplex to a complex, Ki= Ki−1∪ {σi} withdim σi= p. The addition of σichanges only two boundary matrices, the p-thand the (p + 1)-st. Since Ki−1is a complex it contains none of the cofaces ofσi. The additional row in the (p + 1)-st boundary matrix is therefore zero, asin Figure VI.1. This implies that the ranks of Zp+1and Bpremain unchanged.However, the additional column in the p-th boundary matrix is generally non-zero and we distinguish two cases.VI.1 Persistent Homology 1291. The column is a linear combination of prior columns. We can use rowoperations to zero-out the new column. The rank of Zptherefore increasesby one and the rank of Bp−1stays the same. Hence, βp(Ki) = βp(Ki−1)+1and all other Betti numbers remain as before.2. The additional column is not a linear combination of prior columns. Wecan use row and column operations to extend the diagonal of ones byone position. The rank of Zpremains unchanged and the rank of Bp−1increases by one. Hence, βp−1(Ki) = βp−1(Ki−1) − 1 and all other Bettinumbers remain as before.BrankZrankpp−1BrankZrankpp+1zeroFigure VI.1: Adding a p-simplex adds a column to the p-th and a row to the (p +1)-stboundary matrices.The computation of Betti numbers thus reduces to deciding whether a newp-simplex gives birth to a new p-cycle and thus increases βpor it gives deathto a (p − 1)-cycle (changes it to a (p − 1)-boundary) and thus decreases βp−1.Calling the former simplices positive and the latter negative, we can expressthe idea of persistence as pairing positive with negative simplices and this wayassessing homology classes in terms of their lifetime within a filtration.Persistent homology groups. Recall that the filtration of complexes de-fines a sequence of homology groups connected by homomorphisms for eachdimension. We simplify the notation by writing Hip= Hp(Ki) and add the zerohomology group at the end, giving0 = H0p→ H1p→ . . . → Hnp→ Hn+1p= 0.The homomorphisms can be composed giving maps fi,jp: Hip→ Hjp. The imageof fi,jpconsists of all p-dimensional homology classes that are born at or before130 VI PersistenceKiand die after Kj. The effect of adding the zero group at the end is thatevery class eventually dies.Definition. The dimension p persistent homology groups are the images ofthe homomorphisms induced by inclusion, Hi,jp= im fi,jp, for 0 ≤ i ≤ j ≤ n + 1.The corresponding dimension p persistent Betti numbers are the ranks of thesegroups, βi,jp= rank Hi,jp.Note that Hi,ip= Hip. The persistent homology groups consist of the homologyclasses of Kithat are still alive at Kjor, more formally, Hi,jp= Zip/(Bjp∩ Zip),where Zipand Bjpare the p-th cycle and boundary groups of Kiand Kj. Cor-respondingly, the persistent Betti numbers count the independent homologyclasses in Kithat are still alive and independent in Kj. Equivalently, theycount the independent homology classes in Kjthat are born at or before Ki.We have such a number for each dimension p and each index pair i ≤ j. Tovisualize all these numbers we introduce multiplicities,µi,jp= (βi,j−1p− βi,jp) − (βi−1,j−1p− βi−1,jp),for all i < j. We have added the parentheses to suggest the following interpre-tation of this formula. The first difference counts the classes in Kj−1born ator before Kithat die entering Kj. The second difference counts the classes inKj−1born at or before Ki−1that die entering Kj. It follows that µi,jpcountsthe p-dimensional homology classes born at Kithat die entering Kj. Since weadd only one simplex at every step, there is at most one class born at Ki. Fortrivial reasons, this implies that there is at most one class born at Kithat diesentering Kj. Hence µi,jpis either zero or one for each choice of p, i, j. We drawthe non-zero multiplicities as points in the plane, getting a collection for eachdimension p.Definition. The dimension p persistence diagram of the filtration, denotedas Dgmp, is the set of points (i, j) ∈ R2with µi,jp= 1.Since the multiplicities are defined only for i < j all points lie above thediagonal. For technical reasons which will become clear later, we usually addthe points on the diagonal to the diagram. The definition of µi,jpmay be viewedas an inclusion-exclusion formula for Betti numbers. Specifically, we associateβk,lpwith the point (k, l) and do inclusion-exclusion on the four vertices of a unitsquare, as illustrated in Figure VI.2. Adding up the multiplicities representedby points in an upper, left quadrant cancels all terms other than that at thecorner of the quadrant. This implies that a persistent
View Full Document
Unlocking...