On the Categorical Theory of Persistence Modules

On the Categorical Theory of Persistence Modules Riu Rodríguez Sakamoto On the Categorical Theory of Persistence Modules Riu Rodríguez Sakamoto Junio 2021 Memoria presentada como parte de los requisitos para la obtención del título de Máster en Matemáticas por la Universidad de Sevilla. Tutorizada por Prof. Rocío González Díaz This thesis symbolises an important step in my journey through mathematics. I want to thank my advisor, Rocío González Díaz, for introducing me to the field of topological data analysis and for her invaluable guidance and encouragement through this last year. I cannot overstate the help of Manuel Soriano Trigueros, my unofficial coadvisor, whose insight and helpful comments have helped me shape this thesis. Both Rocío and Manuel have provided an important and constant support that has made this an exciting and delightful endeavour. I am most thankful to my parents, whose unceasing support and time has made everything possible for me. Finally, I thank Andrea, for her encouragement and companionship. Resumen ¿Cómo se infieren formas a partir de datos? Se pueden emplear técnicas del álgebra y la topología computacional para responder a esta pregunta, dando lugar al análisis topológico de datos (TDA), un campo que experimenta actualmente un gran crecimiento. La homología persistente es una herramienta clave en TDA que computa características topológicas de un espacio en diferentes resoluciones espaciales a partir de la construcción de complejos simpliciales y su caracterización. Esta herramienta tiene aplicaciones en varias áreas de la matemáticas aplicada y una base teórica sólida formalizada en el marco de la teoría de categorías. En esta tesis hacemos una revisión de la teoría en torno a uno de los pilares centrales de la homología persistente, los módulos de persistencia. Examinamos la descomposición y comparación de estos y teoremas de estabilidad relacionados. En este proceso, nos centramos en buscar el enfoque matemático más útil para expresar estas ideas, que quedan cohesionados por la teoría de categorías. Además de la literatura revisada, también aportamos una serie de contribuciones propias en materia de una construcción particular de módulos de persistencia denominados módulos escalera (ladder modules). Asimismo, presentamos este trabajo de forma lo más autocontenida posible, para que sirva de introducción fluida tanto a esta vertiente de la teoría de categorías como a los conceptos de homología persistente aquí empleados. Palabras clave: Homología persistente, teoría de categorías, análisis topológico de datos, módulos de persistencia, módulos escalera Abstract How is shape infered from data? Algebraic and topological techniques can be employed computationally to answer this question, giving birth to the fast growing field of topological data analysis (TDA). Persistent homology is a key tool in TDA that computes topological features of a space at different spatial resolutions from the construction of simplicial complexes and their characterization. It has both a broad applicability in various areas of applied mathematics and a strong theoretical base that has been formalized in the framework of category theory. In this thesis we review the theory around one of persistent homology’s key elements: persistence modules. We examine their decomposition and comparison and related stability theorems. Along the way, we focus on finding the most useful mathematical language to convey these ideas, which end up being glued by category theory. In addition to the reviewed literature on persistent homology, we also add some contributions of our own regarding ladder modules, a particular construction of persistence modules. Furthermore, we present this work in a self-contained way, to serve as a painless introduction both to this side of category theory and to persistent homology. Keywords: Persistent homology, category theory, topological data analysis, persistence modules, ladder modules 4on the categorical theory of persistence modules composition: given f:A→Band g:B→C, then g◦f:A→Cis defined as g◦f(a) = g(f(a)) ∀a∈A. •Ab, of abelian groups and group homomorphisms. •Vec, of vector spaces and linear maps. •FinVec, of finite vector spaces and linear maps. •SCpx, of simplicial complexes and simplicial maps (cf. Definition 3.1.1). •Top, of topological spaces and continuous maps. The identity map is continuous, and composition of continuous maps too. Remark 2.0.3.The word class is used in category theory to talk about collections of sets. This is usually introduced in the foundations [34, Sec.I.6] [1, Sec.2.2] to overcome Russell’s paradox in set theory. A small class is a set (that has a cardinality), and a proper or large class is a collection bigger than a set. A small category is a category with a set of objects and a set of morphisms. Definition 2.0.4 (Subcategory [34, Sec.I.3]). Asubcategory Dof a category Cis a collection of some objects and some arrows of C. For each arrow f∈D1,dom fand cod fare in D0. For each object X∈D0,1Xis in D1, and for each pair of composable arrows Xf −→ Yg −→ Zin D,g◦fis in D1too. These conditions ensure that Dis itself a category. For any two objects X, Y ∈D0, in general we have D(X, Y )⊆C(X, Y ). We say that Dis a full subcategory of Cif D(X, Y ) = C(X, Y ), i.e. all morphisms between Xand Yin C1are in D1too. Example 2.0.5.FinVec is a full subcategory of Vec because it contains only some objects of Vec (only the finite-dimensional vector spaces), but all linear maps between finite-dimensional vector spaces are contained in FinVec. Definition 2.0.6 (Initial, terminal and zero objects, zero arrow [34, Sec.I.5]). An object iis initial in Cof to each object athere is exactly one arrow i→a. An object tis terminal in Cof to each object athere is exactly one arrow a→t. A zero object 0in Cis an object which is both initial and terminal. The zero arrow between two objects a, b of Cis the unique composite through z:a→0→b. Example 2.0.7.In Vec, the initial and terminal objects are both the zero-dimensional vector space 0, as there is only one linear map sending 0to the zero vector in any vector space, and exactly one linear map sending all elements of a vector space to 0. Therefore 0is the zero object of Vec. Definition 2.0.8 (Epimorphism [34, Sec.I.5]). A morphism f:X→Yin some category Cis called epimorphism (or just epi) if for every other object Z∈Cand every pair of morphisms g1, g2:Y→Zthen g1◦f=g2◦fimplies g1=g2. It is a generalization of surjective functions between sets. X Y Z fg1 g2 Definition 2.0.9 (Monomorphism [34, Sec.I.5]). A morphism f:X→Yin some category Cis called monomorphism (or just mono) if for every other object Z∈C 2. category theory 5 and every pair of morphisms g1, g2:Z→Xthen f◦g1=f◦g2implies g1=g2. It is a generalization of injective maps between sets. We sometimes emphasize that a morphism is mono drawing it with a hook as in Z X Y g1 g2 f The above definition can be restated to emphasize the universal property of a monomorphism: There is at most one morphism g:Z→Xsuch that the following diagram commutes: X Y Z f g(2.2) Definition 2.0.10 (Functor [34, Sec.I.3]). Let C,Dbe categories. A functor F:C→ Dconsists of a a map F:C0→D0, and for each pair X, Y ∈C0, a map F:C(X, Y )→ D(F(X), F(Y)). These maps are compatible with composition and identity: for f:X→ Yand g:Y→Zwe have F(gf) = F(g)F(f), and F(1X) = 1F(X)for X∈C0. Definition 2.0.11 (Natural transformation [34, Sec.I.4]). Let F, G:C→Dbe functors. A natural transformation η:F⇒Gconsists of, for all X∈C0, a morphism ηX:F(X)→G(X)in D, called the component of ηfor X, such that for all morphisms f:X→Ythe diagram F(X)G(X) F(Y)G(Y) ηX F(f)G(f) ηY commutes, which is to say that ηY◦F(f) = G(f)◦ηX. The above diagram is also drawn as follows: F(X)G(X) F(Y)G(Y), F(f)G(f) η =⇒or C D. F G η The set of natural transformations from Fto Gis denoted DC(F, G). Definition 2.0.12 (Natural isomorphism [34, Sec.I.4]). Given two functors F, G:C→ D, a natural isomorphism between Fand Gis a natural transformation η:F⇒G with every component ηXinvertible in D. That is, ηX:F(X)→G(X)has an inverse arrow η−1 X:G(X)→F(X). We write η:F∼ =G, and the inverses (ηX)−1in Dare the 6on the categorical theory of persistence modules components of a natural isomorphism η−1:G⇒F. C D F(X) X G(X) ηX F G η−1 X Definition 2.0.13 (Equivalence [34, Sec.I.4]). An equivalence between two categories C,Dis defined as a pair of functors F:C→D,G:D→Ctogether with natural isomorphisms 1C∼ =G◦F,1D∼ =F◦G. Definition 2.0.14 (Preordered set as category [34, Sec.I.2]). A preorder is a category Pwhere, for any two objects a, b ∈Pthere is at most one arrow a→b. This arrow is the binary relation a≤bwhich is reflexive (there is always the identity arrow a≤a) and transitive (composition: a≤b≤cimplies a≤c). Example 2.0.15.The reals (R,≤)are in particular a preorder (ignoring the antisymmetry condition that a≤b≤aimplies a=b), so it is a category, where the objects are real numbers, and morphisms are inequalities: for any two reals a, b the homset R(a, b)contains one map a≤b. Composition is the transitivity of inequalities: R(b, c)×R(a, b)→R(a, c) b≤c, a ≤b7→ a≤c For every a∈Rthere is an identity morphism 1a∈R(a, a), namely a≤a, such that for every f∈R(a, b), it holds that f◦1a=f, and similarly 1a◦g=gfor every g∈R(c, a). Associativity is also immediate: for every a, b, c, d ∈Rwhere f:a≤b, g:b≤c,h:c≤d: h◦(g◦f)=(h◦g)◦f a≤c≤d a ≤b≤d Example 2.0.16.A finite set {k∈Z+|k < n}for some positive integer ncan be regarded as a category n, where the generating morphisms connect consecutive elements: 12· · · n with the usual composition and identity. We choose not to include 0so we can say that nhas exactly nobjects. It should not be confused with the discrete category of nelements, where the only morphisms are the identity morphisms: 12· · · n 2. category theory 7 Definition 2.0.17 (Functor category, diagram [34, Sec.II.4]). Let C,Jbe categories. The functor category CJis the category whose objects are functors F:J→C, and morphisms are natural transformations between these functors. A functor F:J→C with J(usually very) small(1)is called a J-indexed diagram in C. We also talk about the diagram Fin CJ. Here Cis denoted the target category, and Jthe indexing category. Example 2.0.18.A(Z+,≤)-indexed diagram Fin a category Cis a sequence of objects of Cconnected by morphisms: F1F2F3· · · Likewise, a diagram F∈C(R,≤)has objects Fafor all a∈Rand for each a≤b, a morphism Fa→Fb. The term diagram is also used to talk about the image of a certain diagram in the above sense, that is, some objects of a category Cconnected by some morphisms of C, like (2.1) or (2.2). Definition 2.0.19 (Arrow category [4, 1.6.3]). For Cany category, its arrow category, denoted Arr(C)or C2, has arrows (morphisms) of Cas objects, and an arrow gfrom f:A→Bto f0:A0→B0in Arr(C)is a commutative square A A0 B B0 g1 ff0 g2 where g1and g2are arrows in Csuch that g2◦f=f0◦g1. The identity arrow 1fon an object f:A→Bis the pair (1A,1B). Composition of arrows is done componentwise: (h1, h2)◦(g1, g2) = (h1◦g1, h2◦g2) Remark 2.0.20.One might wonder why the arrow category of Cis denoted C2. This is because it is a special case of a functor category. Indeed, a functor Ffrom 2(the category containing two objects and a morphism 1→2) to Csends •the object 1in 2to an object Ain C. •the object 2in 2to an object Bin C. •the morphism 1→2in 2to a morphism A→Bin C. so it effectively describes two objects of Cand a morphism between them. The category C2has as objects these functors F, or more pedantically, the image of these functors, (1)Recall Remark 2.0.3. We say informally that Jis very small to emphasize that most of the time Jcontains no more than a handfull of objects. 8on the categorical theory of persistence modules i.e. diagrams A→Bin C. 2 C 1A 2B F F F Definition 2.0.21 (Adjunction [43, Def.4.1.1]). An adjunction between categories C and D, denoted CD, consists of a pair of functors F:C→Dand G:D→C together with an isomorphism D(Fc, d)∼ =C(c, Gd) for each c∈Cand d∈Dthat is natural in both variables. Here Fis the left adjoint to Gand Gis the right adjoint to F. Definition 2.0.22 (Product category, bifunctor [34, Sec.II.3]). For two categories Cand D, the product category C×Dis the category whose objects are ordered pairs (c, d)with can object of Cand dan object of D. Morphisms are ordered pairs (f, g) : (c, d)→(c0, d0), and composition is defined componentwise: (f0, g0)◦(f, g) = (f0◦f, g0◦g) A functor F:A×B→Cfrom a product category A×Bis called a bifunctor. Proposition 2.0.23.For categories A,Band C, there is a natural isomorphism CA×B∼ = (CB)A. Proof. This is a standard exercise in Category Theory. See for example [34, II.5 Ex.2]. For a natural isomorphism to exist, we define two functors ϕ:CA×B→(CB)A ψ: (CB)A→CA×B •ϕacting on objects of CA×B: Given T:A×B→C,ϕ(T): A→CBmaps –objects a∈Ato functors T(a, −): B→C. –morphisms f:a→a0to natural transformations ϕ(T)(f): CB→CBwith components ϕ(T)(f)b:T(a, b)→T(a0, b)such that for every functor g:b→ 2. category theory 9 b0in B, the following diagram commutes: b ϕ(T)(a)(b)ϕ(T)(a0)(b) b0ϕ(T)(a)(b0)ϕ(T)(a0)(b0) g ϕ(T)(f)b ϕ(T)(a)(g)ϕ(T)(a0)(g) ϕ(T)(f)0 b T(a, b)T(a0, b) T(a, b0)T(a0, b0) T(f,b) T(a,g)T(a0,g) T(f,b0) •ϕacting on morphisms of CA×B: Given S, T :A×B→C,ϕmaps the morphism η:S→Tto a natural transformation ϕ(η)with components ϕ(η)a=η(a, −): ϕ(S)(a)→ϕ(T)(a) such that the following diagram commutes: a ϕ(S)(a)ϕ(T)(a) a0ϕ(S)(a0)ϕ(T)(a0) f ϕ(η)a ϕ(S)(f)ϕ(T)(f) ϕ(η)a0 S(a, −)T(a, −) S(a0,−)T(a0,−) η(a,−) S(f,−)T(f,−) η(a0,−) •ψacting on objects of (CB)A: Given T:A→CB,ψ(T): A×B→Cmaps –objects (a, b)∈A×Bto objects ψ(T)((a, b)) = T(a)(b). –pairs of morphisms (f, g): (a, b)→(a0, b0)in A×Bto a morphism ψ(T)((f, g)) = T(f)b0◦T(a)(g): ψ(T)((a, b)) →ψ(T)((a0, b0)) (2.3) which we will name T(f)(g)for brevity. •ψacting on morphisms of (CB)A: Given S, T :A→CB,ψmaps the morphism η:S→Tto a natural transformation ψ(η)with components ψ(η)(a,b)= (ηa)b, such that the following diagram commutes: (a, b)ψ(S)((a, b)) ψ(T)((a, b)) (a0, b0)ψ(S)((a0, b0)) ψ(T)((a0, b0)) (f,g) ψ(η)(a,b) ψ(S)((f,g)) ψ(T)((f,g)) ψ(η)(a0,b0) S(a)(b)T(a)(b) S(a0)(b0)T(a0)(b0) (ηa)b S(f)(g)T(f)(g) (ηa0)b0 Recall that ψ(T)maps the pair (f, g)to a composition of the b0component of the natural transformation T(f)after the functor T(a)(g)(2.3). The above 10 on the categorical theory of persistence modules commuting square is thus the diagonal square of the following commuting cube: (a, b)ψ(S)((a, b)) ψ(T)((a, b)) ψ(S)((a0, b)) ψ(T)((a0, b)) ψ(S)((a, b0)) ψ(T)((a, b0)) (a0)(b0)ψ(S)((a0, b0)) ψ(T)((a0, b0)) (f,g) ψ(η)(a,b) ψ(S)((1a,g)) ψ(S)((f,1b)) ψ(T)((f,1b)) ψ(T)((1a,g)) ψ(η)(a0,b) ψ(S)((1a0,g)) ψ(T)((1a0,g)) ψ(η)(a,b0) ψ(S)((f,1b0)) ψ(T)((f,1b0)) ψ(η)(a0,b0) which evaluates to (a, b)S(a)(b)T(a)(b) S(a0)(b)T(a0)(b) S(a)(b0)T(a)(b0) (a0)(b0)S(a0)(b0)T(a0)(b0) (f,g) (ηa)b S(a)(g) S(f)bT(f)b T(a)(g) (ηa0)b S(a0)(g) T(a0)(g) (ηa)b0 S(f)b0T(f)b0 (ηa0)b0 Corollary 2.0.24.For categories A,Band C, there is a natural isomorphism (CB)A∼ = (CA)B. Proof. There is a natural isomorphism A×B∼ =B×A. For objects a∈A,b∈B and morphisms f:a→a0in Aand g:b→b0in B: (a, b)∼ =(b, a) (f, g)∼ =(g, f) Then by Proposition 2.0.23 we have (CB)A∼ =CA×B∼ =CB×A∼ =(CA)B. Note that this agrees with general rules of exponentiation in arithmetic. Definition 2.0.25 (Product [4, Def.2.15]). In a category C, a product diagram for objects Aand Bconsists of an object P(the product) and arrows A P B p1 p2 such that for any diagram of the form Ax1 ←− Xx2 −→ Bthere exists a unique u:X→P 2. category theory 11 such that x1=p1uand x2=p2u, making the following diagram commute: X A P B. x1ux2 p1p2 Definition 2.0.26 (Coproduct [4, Def.3.3]). Dually, a coproduct of objects Aand Bin a category Cconsists of an object Q(the coproduct) and arrows A Q B q1q2 such that for any diagram of the form Az1 −→ Zz2 ←→ Bthere exists a unique u:Q→Z such that uq1=z1and uq2=z2in Z A Q B q1 z1u q2 z2 Example 2.0.27 ([4, 2.4,3.2]).In Set, a product of two sets Aand Bis the cartesian product A×B={(a, b) : a∈A, b ∈B}. Their coproduct is their disjoint union A+B={(a, 1) : a∈A}∪{(b, 2) : b∈B}. Example 2.0.28.In Vec, the product of two vector spaces Vand Wis the usual product V×W={(v, w) : v∈V, w ∈W}, and the coproduct is the direct sum V⊕W. Definition 2.0.29 (Equalizer [4, Def.3.13]). In a category C, given two parallel arrows (parallel as having same domain and codomain) X Y f g an equalizer of fand gconsists of an object Eand an arrow e:E→Xsuch that fe =ge and for any z:Z→Xwith fz =gz, there is a unique u:Z→Ewith eu =z, all as in the diagram E X Y Z fe g uz Definition 2.0.30 (Coequalizer [4, 3.18]). Given two parallel arrows f, g :X→Y in a category C, a coequalizer consists of Qand q:Y→Qsuch that qf =qg and for 12 on the categorical theory of persistence modules any z:Y→Zwith zf =zg, then there exists a unique u:Q→Zsuch that uq =z. X Y Q Z f g q zu Definition 2.0.31 (Kernel, cokernel [43, Def.E.5.1]). The kernel ker(f)of a morphism f:X→Yis the equalizer of fwith the zero arrow, and the cokernel coker(f) is the coequalizer of fwith the zero arrow. K X Y C ker ff 0 coker f Example 2.0.32.In Vec, the kernel and cokernel of f:V→Wcoincide with the linear algebra notions of the terms, respectively the nullspace of fand the quotient space W/ im(f). Definition 2.0.33 (Abelian category [34, Sec.VIII.3]). A category Cis abelian if •it has a zero object 0, •for every two objects, their product and coproduct always exist, •for every morphism, its kernel and cokernel always exist, and •all monomorphisms and epimorphisms are kernels and cokernels, respectively. This means that if f:X→Yis monic, then f= kergfor some g:Y→Z. If f:X→Yis epi, then f= coker gfor some g:Z→X. Example 2.0.34.Vec is abelian. The first three conditions are met by Example 2.0.7, Example 2.0.28 and Example 2.0.32. The last one is proved next. Let f:X→Ybe a monomorphism. The quotient space Y/X exists by Example 2.0.32. Let g:Y→Y/ im(f)be the projection sending y∈Yto the equivalence class y+f(X)∈Y/ im(f). The kernel of gis some morphism h:E→Ysuch that gh = 0h. gh:E→Y/ im(f) 0h:E→Y/ im(f) e7→ g(e) + f(X)e7→ 0 + f(X) A perfect candidate for h:E→Ywhere g(e) + f(X) = 0 + f(X)is of course h=f, E=X. To really prove that f= ker gthough, we need to show that given any other h:E→Y, there exists a unique u:E→X. But this is just fulfilled by the universal property of fbeing a monomorphism (2.2). Any epimorphism f:X→Yis the cokernel of ker fby a dual argument. Proposition 2.0.35 ([34, Sec.VIII.3]).If Cis an abelian category then so is CDfor any small category D. 2. category theory 13 Definition 2.0.36 (Cone [4, Def.5.15]). Acone toadiagram D∈CJconsists of an object Cin Cand a family cj:C→Djof arrows in C, one for each object j∈J, such that for each arrow f:i→jin Jthe following triangle commutes: C Dj Di cj ci D(f) Amorphism of cones θ: (C, cj)→(C0, c0 j)is an arrow θin Cmaking each triangle C C0 Dj θ cj c0 j commute. This forms a category Cone(D)of cones to D. Definition 2.0.37 (Limit [4, Def.5.16]). Alimit for a diagram D:J→Cis a terminal object in Cone(D), and it is denoted lim ←−jDj. The limit has projections πi: lim ←− j Dj→Di Definition 2.0.38 (Inverse limit [1, Ch.III Ex.11.4.3]). Let Ibe a poset considered as a category (Example 2.0.15 treats Ras a preordered set, but the same construction can be adapted to Ras a poset). The limits of I-indexed diagrams are called inverse (or projective) limits. Example 2.0.39 (Inverse limit in Set(N,≥)[1, Ch.III Ex.11.4.3]).Let I= (N,≥)be the category of natural numbers where there is an arrow i→jwhenever i≥j(opposite of the usual ordering). A diagram Din Set(N,≥)is a sequence · · · D2D1D0. d2 3d1 2d0 1 A projective limit of Dis the set lim ←−nDnof all sequences (xn)n∈Nsuch that xn∈Dn and dn n+1(xn+1) = xnfor each n∈N. The map πmis a restriction of the m-th projection pm: Πn∈NDn→Dm. lim ←−nDn · · · D2D2D0. π2π1π0 d2 3d1 2d0 1 Example 2.0.40 (Cones and inverse limit in Vec).Let I= (Z+,≤)be the category 20 on the categorical theory of persistence modules •0-homology: The 0-cycles and 0-boundaries are: Z0= ker ∂0=hx, yi B0= im ∂1=hx−yi where the boundaries are generated by x−ybecause ∂a =y−x,∂b =x−y, ∂c =x−x= 0. H0(P, Z) = Z0/B0≃Z •1-homology: Similarly: H1(P, Z) = Z1/B1=ha+b, ci/ha+b+c, a+b−ci≃ha+b, ci/ha+b, 2ci ≃ Z/2Z=Z2 •2-homology: H2(P, Z) = Z2/B2= 0/0=0 The chain complex over Z2produces the same 0- and 2-homology. However for the 1-homology: B1(P, Z2) = ha+b+c, a +b−ci=ha+b+ci and thus H1(P, Z2) = ha+b, ci/ha+bi ≃ Z2. Even though H1(P, Z) = Z2and H1(P, Z2) = Z2, the first case is a finite cyclic group with a torsion coefficient of 2respect to the base field Zand its Betti number is b1= 0. In the latter case, the 1-homology is an infinite cyclic group and b1= 1. This reflects the fact that the projective plane is even-dimensional, and thus non-orientable. Calculating the Betti number over Zproduces a torsion coefficient, and working over Z2forgets orientation, generating a cycle in its place. 3.2.1 Homology as functor The homology explained and exemplified above is called simplicial homology. It defines afunctor Hk:SCpx →Vec (3.1) from the category of simplicial complexes and simplicial maps to the category of vector spaces and linear maps.(1) Given two simplicial complexes connected by a simplicial map Kϕ −→ L,Hkoutputs two vector spaces connected by a linear map Hk(K)→ Hk(L). It is a functor because it respects identity maps and composition. Example 3.2.2.The 0-homology functor applied to Kϕ −→ Lin Figure 3.2 outputs (1)Recall that we are working over Z2. In case of homology over Z, it would be a functor Hn:SCpx → Ab, where Ab is the category of abelian groups and group homomorphisms. 3. persistent homology 21 x0x1 x2 x3 K y0 y1 y2 L ϕ Figure 3.2: Two simplicial complexes connected by a simplicial map. F2 1 0 0 1! −−−−−→ F2, and the 1-homology functor outputs F0 −→ 0. Both are vector spaces connected by linear maps. Singular homology is another notion of homology that is defined for topological spaces. Simplices are replaced with singular simplices, which are continuous maps σ: ∆n→Xfrom the standard n-simplex to the topological space, and k-chains are formal sums of k-dimensional singular simplices. This defines a functor [11, Ex.2.4] Hk:Top →Vec from the category of topological spaces and continuous maps to Vec. As remarked in [18], singular and simplicial homologies coincide whenever Xis homeomorphic to the geometric realization of a simplicial complex, and thus we are able to indifferently talk about simplicial or singular homology for simplicial complexes and topological spaces. We could also work with homology of CW complexes, ∆-complexes (as in Example 3.2.1), etc. In general, the definition of a k-homology functor can be given for any abelian category. 3.3 Persistence modules and generalizations The classical definitions of persistence [25] and persistence modules introduced in computational topology have been formalized and expanded in the framework of category theory in several ways. We give next various definitions of persistence modules and related constructions. 22 on the categorical theory of persistence modules Definition 3.3.1 (Persistence module [11]). Diagrams in Vec(R,≤)are often called persistence modules. A persistence module is a functor Vfrom (R,≤)to Vec that sends real numbers to vector spaces and inequalities between two reals to linear maps:(2) V: (R,≤)→Vec t7→ Vt s≤t7→ vt s:Vs→Vt where composition and identity are expressed as vt svs r=vt r∀r≤s≤tin R, vt t=1Vt∀t∈R. 1Vt:Vt→Vtis the identity morphism sending Vtto itself. A morphism ϕbetween two persistence modules V,Wis a (R,≤)-indexed family of linear maps {ϕt}t∈(R,≤)such that for any s, t ∈Rwhere s≤t, the following diagram commutes: VsVt WsWt vt s ϕsϕt wt s The set of all morphisms from Vto Wis denoted Hom(V,W). An identity morphism from Vto itself is denoted 1V, and it consists of a family of identity maps 1Vt:Vt→Vt. The set of all endomorphisms of V, that is, morphisms from Vto itself, is denoted as End(V). Some variations of Definition 3.3.1 are made where the indexing category are the reals (R,≤)(Example 2.0.15), the integers (Z,≤), or a finite set n(Example 2.0.16). Definition 3.3.1 is generalized in [10] by letting the indexing category to be any preordered set P, and the target category (usually Vec) to be any category C. Further generalizations as [21] are out of the scope of this work. The level of abstraction that we are going to work with here is to consider persistence modules as P-indexed diagrams in Vec where Pis usually (R,≤)or n. Remark 3.3.2.The indexing category (R,≤)includes the cases (Z,≤),(Z+,≤)and nby suitable inclusion and retraction functors [11, 2.2.3]. For example the inclusion functor i:Z→Rgiven by i(j) = jhas a (left adjoint) ceiling functor c:R→Zgiven by c(t) = dte. Proposition 3.3.3.These categories of persistence modules, that is, of P-indexed diagrams in Vec, are abelian categories. (2)In this work, a map from Vsto Vtis denoted vt s, while in [19] they are denoted ρts, and in [16] the super- and subindex are flipped as in vs t. 3. persistent homology 23 Proof. Since Vec is an abelian category (Example 2.0.34), these categories are too by Proposition 2.0.35. Remark 3.3.4 ([10, Sec.1.1]).A persistence module in Vecncan be regarded as the composition of a functor F:n→SCpx and the simplicial homology functor (3.1) which takes the diagram of simplicial complexes connected by simplicial maps S1,→ S2,→ · · · ,→Snand outputs a diagram of vector spaces connected by linear maps V1→V2→ · · · → Vnas in Example 3.2.2. A complete picture of a persistence module is then n SCpx Vec. FHk We will discuss the nature of the functor Flater in Section 3.4. 3.3.1 Zigzag modules From the applied viewpoint, there are many techniques to construct a simplicial complex from a given point cloud in Rn: the Čech complex, the Vietoris-Rips complex, the alpha complex, etc. A limitation of persistent homology is that the resulting sequence of spaces must be a nested family for the homology functor to produce a persistence module, and several situations in topological data analysis arise where this sequential nesting is too limited [44]. Zigzag persistence are introduced in [13] to address this limitation borrowing results from quiver theory (graph representation theory) and extends diagrams in Vecnby not requiring the morphisms to go all in the same direction. Some background terminology of quiver theory is given next. Definition 3.3.5 (Quiver). Aquiver Q= (Q0, Q1)is a directed graph, also called multigraph, with a set of vertices Q0and a set of arrows Q1. Each arrow in Q1has a source s∈Q0and a target t∈Q0. Example 3.3.6 (An(τ)).Given an orientation τ= (τ1, . . . , τn−1), the An(τ)quiver is defined as An(τ) : 1 2 · · · n τ1τ2τn−1 where the i-th arrow is i−→ (i+ 1) if τi=~τ and i←− (i+ 1) if τi= ~ τ. Adjunction Cat Quiv [42, 4.]. We can think of quivers as small categories with identity morphisms and composition forgotten. The functor Forget: Cat →Quiv from Cat (the category of small categories) to Quiv (the category of directed graphs) sends each category (an object of Cat) to its underlying directed graph (an object of Quiv). The left adjoint of this functor gives the free category from a directed graph: Free: Quiv →Cat. The free category or path category Free (Q)of a graph Q[9, 5.1] has the vertices of the graph as objects and the set of paths starting in xand ending at y(i.e. all compatible compositions of arrows in the graph) as the set of morphisms between xand y. 24 on the categorical theory of persistence modules Quiv Cat 123 123 Free −−→ ←−−− Forget 1 2 1 2 Figure 3.3: Example of two objects of Quiv and their correponding free categories, objects of Cat. Example 3.3.7.Free(An(τ)) with τ= (~τ, . . . ,~τ)(i.e. all forward arrows) is isomorphic to n.Free(−)assigns an object to each vertex in An(τ)0and a morphism to each arrow in An(τ)1. The functor Free(−)together with the An(τ)quiver generalize nas an indexing category by not requiring the orientation to be all forward maps, and allows to describe zigzag modules as diagrams in VecFree(An(τ)). Definition 3.3.8 (Representation of a quiver [42, 4.]). The representation of a quiver Qis an object of VecFree(Q), i.e. a functor from its free category Free (Q)to Vec R: Free(Q)→Vec where Rsends each vertex to a vector space and each edge to a linear map. Here Free(Q)is not an object of Cat but itself a category. Example 3.3.9.Let A3(τ)be the An(τ)quiver with three vertices and τ= (~τ1,~τ2). Its free category Free(A3(τ)) has three objects, three identity morphisms, two morphisms ~τ1,~τ2and all compositions between these morphisms. For example, ~τ2◦12◦~τ1is a valid morphism in Free (A3(τ)). The representation of A3(τ)has three vector spaces, three identity linear maps, two linear maps v2 1and v3 2and all compositions of morphisms, e.g. v3 1=v3 2◦v2 1∈ Vec(V1, V3). We will not write R◦Free (Q)but rather R∈VecFree(A3(τ)), because Free(−)is a functor that acts on quivers as objects of Quiv and outputs a category as an object of Cat, while Rtakes Free (G)not as an object of Cat but as a category by itself. Ris a particular representation of Free (A3(τ)), fixing specific vector spaces and linear maps. Another R0may represent Free (A3(τ)) with another set of vector spaces 3. persistent homology 25 and linear maps. Free(A3(τ)) 1 2 3 ~τ ~τ R −→ Vec V1V2V3 v2 1v3 2 A zigzag module is a sequence of vector spaces and linear maps of length n, where the directions of the maps are encoded in the orientation τ. It is a representation of aAn(τ)quiver. The orientation of a zigzag module is a sequence of n−1symbols in {~τ, ~ τ}where ~τ stands for forward maps and ~ τfor backward maps. For example, the zigzag module V1→V2←V3←V4is of length 4and has orientation τ= (~τ, ~ τ, ~ τ). Zigzag modules of a given length nand an orientation τare called τ-modules, and the class(3)of τ-modules is denoted by τMod. Persistence modules fit naturally in this definition, where their orientation is composed of only forward maps ~τ. Proposition 3.3.10.τMod is an abelian category. Proof. This is remarked in [13, p.5], defining the relevant kernels, images and cokernels. A shorter proof can be made by noting that τMod ≃VecFree(An(τ)) and applying Proposition 3.3.3. 3.3.2 Ladder modules Motivated by these connections between persistent homology and quiver theory and also by TDA applications in material science and protein structural analysis, ladder modules are introduced in [3] as persistence modules on the commutative ladder. A commutative ladder is another example of a quiver, which we define next. Example 3.3.11 (Ladder quiver Ln(τ)).Let τ= (τ1, . . . , τn−1)be an orientation. The ladder quiver Ln(τ)is the following quiver: Ln(τ): 1 2 · · · n 1020· · · n0 τ1τ2τn−1 τ1τ2τn−1 where the directions of the arrows on both the top and bottom rows are determined by the orientation τ. The commutative ladder CLn(τ)is the ladder quiver Ln(τ)bound by commutative relations. Intuitively this means that any two paths with common source and targets are equivalent (we take the quotient by this equivalence relation). Ladder modules can be defined in multiple ways: (3)see Remark 2.0.3. 26 on the categorical theory of persistence modules •A persistence module on the commutative ladder CLn(τ)[3, Def.2]. •A representation of the CLn(τ)quiver [3, Def.2]. •A diagram in VecFree(CLn(τ)). •A morphism between An(τ)quivers. This is proved in [3, Th.2], where Rep Qis a notation for an object of VecFree(Q)for some quiver Qand Arr(C)is the arrow category of a category C: RepCLn(τ)∼ =Arr(RepAn(τ)) Example 3.3.12 ([10, Ex.1.1.2]).To show how such a construction can arise from a practical example, consider two nested families of abstract simplicial complexes (Ki) and (Li)that we want to relate with each other, K1⊆K2⊆K3⊆K4, L1⊆L2⊆L3⊆L4. These can be thought of as functors K, L:4→SCpx where 4is the ncategory with four objects. A natural question would be to ask if there is a morphism between (Ki)and (Li). Suppose ϕ4:K4→L4is a simplicial map which restricts to simplicial maps ϕi:Ki→Lifor all i. Then ϕ= (ϕi)is a natural transformation K⇒L. The commutative diagram K1K2K3K4 L1L2L3L4 ϕ1ϕ2ϕ3ϕ4 shows the maps and contains all required commutative squares. 3.3.2.1 Alternative definition of ladder modules We propose an alternative definition of ladder module taking inspiration from Definition 3.3.1. First we fix the target category to be the arrow category of Vec: Definition 3.3.13. The arrow category of Vec, notated as Arr(Vec)or Vec2, is a functor category from 2to Vec. •Objects: Linear maps ϕ:V→Wof Vec, where Vand Ware objects of Vec. •Morphisms: A morphism ρt s= (vt s, wt s): ϕs→ϕtfrom an object ϕs:Vs→Wsto ϕt:Vt→Wtis a pair of linear maps (vt s:Vs→Vt, wt s:Ws→Wt)of Vec, such that the following diagram commutes: VsVt WsWt vt s ϕsϕt wt s 3. persistent homology 27 Definition 3.3.14. Aladder module is a functor from (R,≤)to Arr(Vec). M: (R,≤)→Arr(Vec) t7→ ϕt s≤t7→ ρt s:ϕs→ϕt A ladder module can be equivalently defined as an object of (Arr(Vec))(R,≤), i.e. a(R,≤)-indexed diagram in Arr(Vec). In the case of a finite ladder module, it is an object of (Arr(Vec))n. Proposition 3.3.15.Consider An(τ)and nthe indexing category with nobjects. There exists an equivalence between (Arr(Vec))nand Arr(RepAn(τ)) with τ= (~τ, . . . ,~τ). Proof. The chain of equivalences follow: (Arr(Vec))n≃Vec2n≃(Vecn)2≃(Rep An(τ))2≃Arr(Rep An(τ)) The first and last equivalences are clear by the definition of arrow category. We can prove the equivalence of the categories (Vecn)2≃(RepAn(τ))2by proving the equivalence of the underlying categories Vecn≃RepAn(τ). This follows from n≃F(An(τ)) with τ= (~τ, . . . ,~τ)(Example 3.3.7) and RepAn(τ)being notation for an object of VecF(An(τ)). Letting A=2,B=nand C=Vec, we have (Vecn)2∼ =Vec2nby Corollary 2.0.24. This is clear if we note that objects of both categories are partial applications of the bifunctor from the product category n×2to Vec, which is what Corollary 2.0.24 tells us. As the cartesian product of two posets is also a poset (with a chosen order, like lexicographic order), the product category n×2is also an indexing category that defines a diagram. In the case of (Vecn)2, the bifunctor is first applied in 2and then in n, and viceversa for Vec2n. Example 3.3.16.Let n=3be the indexing category with three elements and morphisms between them: 123 We omit the identity morphisms and the compositions from the diagram. The isomorphism (Vec3)2∼ =(Vec2)3amounts to saying that arrows Vi→Wiindexed by 3hold the same information than an arrow between persistence modules Vand W: 6vector spaces connected by some arrows. The difference in hierarchy of single and double arrows can be illustrated as follows (recall Definition 2.0.11 for the diagramatic 28 on the categorical theory of persistence modules notation). V1V2V3V1V2V3 W1W2W3W1W2W3 ⇓ ⇒ ⇒ 3.4 Filtrations Topological persistence emerges as a tool to infer the underlying geometric and topological structure of a finite point cloud in a metric space using what is called a filtering function [15,45]. In keeping with the theme of this work, we will introduce it’s classical definition and it’s categorical reformulation. In Section 3.4.1 we will look at conditions under which morphisms between filtrations exist, and finish with a theorem of existence of ladder modules. Definition 3.4.1 (Filtering function in Set [36, Sec.3.]). Let Sbe a finite set, and P(S)its power set. A filtering function on Sis any function fS:P(S)→Rwhich satisfies the monotonicity condition: fS(ς)≤fS(σ), for all subsets ς⊆σ⊆S. We will omit the subscript and write fSjust as fif it is clear from the context. The definition of a filtering function is not particular to Set. In fact, it is common to define it for simplicial complexes too: Definition 3.4.2 (Filtering function in SCpx). Let Kbe a simplicial complex. A filtering function on Kis a function fK:K→Rsatisfies the monotonicity condition: fK(ς)≤fK(σ)for any simplex ςcontained in another σ(as a face) in K. This leads us to define a general filtered object in an arbitrary category. Definition 3.4.3 (Filtered object, filtration [40]). Given a category C, a filtered object is an object Xof Cequipped with a filtration.(4)Afiltration of Xis a sequence of morphisms (often required to be monomorphisms) of the form · · · → Xn−1→Xn→Xn+1 → · · · → X where Xnare objects of Cand Xis the last element of the sequence. We will refer to a filtration of Xwith the symbol X. (4)We have kept only the definition of descending filtration. A descending filtration of Xis typically denoted in category theory as · · · → Xn+1 →Xn→Xn−1→ · · · → X, but we have flipped the indexing order here to accomodate the usual order of persistence modules. 3. persistent homology 29 Two ways of constructing a filtration of an object Xare: •Using the previously defined filtering functions fX. This is known as the inverseimage construction [10, 3.2], or sublevelset construction [16, Sec.2.1]. See Example 3.4.4. •Defining an indexing functor directly and looking at its image. See Example 3.4.6. Example 3.4.4 (Sublevelset).Given a filtering function in Set fS:P(S)→R, the sublevelset construction or inverse-image construction FSis a functor FS: (R,≤)→Set s7→ f−1(−∞, s] s≤t7→ f−1(−∞, s]⊆f−1(−∞, t] This is defined similarly as FK: (R,≤)→SCpx for fK:K→Rwith Ka simplicial complex, fX:X → Rfor Xa topological space, and filtering functions in other categories. We say that these filtering functions fencode the times of appearance of the sets/simplices/spaces. The next construction starts from a point cloud in a finite metric space, which we define first for good measure. Definition 3.4.5 (Metric, metric space [12, Def.1.1.1]). Let Xbe an arbitrary set. A function d:X×X→R∪ {∞} is a metric on Xif the following conditions are satisfied for all x, y, z ∈X. •Positiveness: d(x, y)>0if x6=yand d(x, x)=0. •Symmetry: d(x, y) = d(y, x). •Triangle inequality: d(x, z)≤d(x, y) + d(y, z). Ametric space (X, dX)is a set Xwith a metric dXon it. A metric space (X, dX)is finite if the set Xis finite. A metric space (X, dX)is bounded if there exists some number rsuch that d(x, y)≤rfor all x, y ∈X. Example 3.4.6 (Vietoris-Rips [26, Sec.III.2]).Let (X, dX)be a finite metric space, for example a set of points in Rnwith the usual Euclidean distance. The Vietoris-Rips complex of radius s, denoted VRs(X), is the maximal simplicial complex built from {σ⊆X:dX(xi, xj)<2s, ∀xi, xj∈σ}. VR: (R,≤)→SCpx s7→ VRs(X) s≤t7→ VRs(X)⊆ VRt(X) 36 on the categorical theory of persistence modules If we post-compose with the homology functor Hk: (R,≤)−→ 2−→ SCpx Hk −→ Vec (3.5) and interpret (R,≤)and 2as indexing categories, we get back an object of ((Vec)2)(R,≤). This is a ladder module!(6) To close this section, we can summarize the above in the following theorem. Theorem 3.4.23. Let (X, dX),(Y, dY)be two metric spaces, and VR(X)and VR(Y) their Vietoris-Rips filtrations. Let ϕ:VR(X)→ VR(Y)be a simplicial map, and ϕ(0) :X→Yits corresponding vertex map sending xi7→ ϕ(0)(xi) = yi. If ϕ(0) isashort map, then there exists a ladder module between the persistence modules Hk(VR(X)) and Hk(VR(Y)). Proof. By Corollary 3.4.21 we have a morphism Φ : VR(X)→ VR(Y), and by the reasoning above (3.5), composing Φwith Hkwe obtain an object of (Arr(Vec)(R,≤), i.e. a ladder module. This result ties up our definition of ladder modules (Definition 3.3.14) with the introduction of filtrations and their categorical conditions of existence (Proposition 3.4.15) which translate to a condition on metric spaces (Corollary 3.4.21) in the special case of Vietoris-Rips filtrations. 3.4.2 Vietoris-Rips as bifunctor We have defined the Vietoris-Rips filtration as an indexed category from (R,≤)to SCpx. The point cloud data is implicit in the functor definition. If we want to make this dependence explicit, we would like to define a ‘category of point clouds’. We first give the necessary definitions to formalize a metric space as a category. Definition 3.4.24 (Symmetric monoidal preorder [28, Def.2.2]). Asymmetric monoidal preorder Vis a preorder (X, ≤)with •a monoidal unit I∈V0, and •a monoidal product ⊗:V×V→V such that for all x1, x2, y1, y2, x, y, z ∈V0the following hold: 1. Monotonicity: If x1≤y1and x2≤y2, then x1⊗y1≤x2⊗y2. 2. Unitality: I⊗x=xand x⊗I=x. (6)We could even define ladder modules in the SCpx category as objects of (Arr(SCpx))(R,≤) without applying Hk, but to avoid confusion, we will apply Hkto get exactly the same objects as the original definition. 3. persistent homology 37 3. Associativity: (x⊗y)⊗z=x⊗(y⊗z). 4. Symmetry: x⊗y=y⊗x. Example 3.4.25.([0,∞],≥)[28, Ex.2.37] and other categories that we have seen throughout this work like (R,≤),nand (Z,≤)are symmetric monoidal preorders. An enriched category is a category where homsets (the set of morphisms between two objects) have additional structure: they form a vector space, or a topological space, etc. These homsets themselves become objects of a suitable monoidal category K, which has to be monoidal because composition in the enriched category is defined in terms of the tensor product: ◦: Hom(y, z)⊗Hom(x, y)→Hom(x, z) Such a category is called a category enriched over K, or a K-category. Definition 3.4.26 (V-category [28, Def.2.46]). A category Cenriched over a symmetric monoidal category Vhas •a set of objects C0. •for each pair of objects a, b ∈C0, a hom-object C(a, b)∈V0. such that for all a, b, c ∈C0 1. there exists an identity element ja:I→C(a, a), and 2. there exists a composition morphism ◦a,b,c :C(b, c)⊗C(a, b)→C(a, c)in Vwhich is associative and unital. Definition 3.4.27 (Lawvere metric space [28, Sec.2.3.3]). ALawvere metric space is a metric space including ∞but with less constraints: It has a metric d, which for elements x, y, z satisfies two conditions: 1. d(x, x) = 0 2. Triangle inequality: d(x, y) + d(y, z)≥d(x, z). The symmetry axiom is not imposed: In general, d(x, y)6=d(y, x). Proposition 3.4.28 ([32]).Lawvere metric spaces are categories enriched in the symmetric monoidal preorder ([0,∞],≥), where tensor product is addition and composition is the triangle inequality. We will denote a Lawvere metric space as a category L. Objects of Lare points. Building on L, we are interested in defining ordered sets of points in this Lawvere metric space. However we are interested in defining only morphisms that translate to inclusions of Vietoris-Rips complexes later so that Corollary 3.4.21 becomes a consequence of functoriality, thus we define a subcategory of [n,L]as follows: 38 on the categorical theory of persistence modules Definition 3.4.29. The category PCloud isasubcategory of [n,L]consisting of •Objects: Point clouds, that is, ordered sets of nobjects in L:X={x1, x2, . . . , xn∈ L}. These form metric spaces (X, dX)restricting the domain of dto X×X. •Morphisms: Short maps between point clouds, that is, a map m:X→Ysuch that dX(i, j)≥dY(i, j). They are composable, as two maps Xm −→ Y˜m −→ Zcompose to ˜m◦m:X→Ywith dX(i, j)≥dZ(i, j). A Vietoris-Rips complex is then a bifunctor VR: ([0,∞],≥)×PCloud →SCpx (r, X)7→ VRr(X) = n{u1, u2, . . . } ∈ Xkui−ujk ≤ ro (r≤s, X)7→ VRr(X),→ VRs(X) (r, X →Y)7→ VRr(X),→ VRr(Y) where there are suitable inclusions of VR complexes when changing the radius r≤s and also when changing between point clouds where the distance matrix has contracted. This way we do not lose information about the points positions. Theorem 3.4.23 becomes then a consequence of functoriality: short maps between metric spaces get mapped to inclusions of Vietoris-Rips complexes. 4 Decomposition of persistence modules To analyze persistence modules, it is useful to have a decomposition into indecomposable building blocks. This section is devoted to the decomposition of certain persistence modules defined in Section 3.3. Section 4.1 presents the tools used in classical persistent homology to tackle decompositions of persistence modules in FinVec(Z,≤). We then focus on one hand in decompositions of zigzag modules by [13] in Section 4.2, because they offer a constructive decomposition algorithm which highlights the computational applications of persistent homology theory. On the other hand, we give an overview in Section 4.3 of the work by [19] describing decomposition of persisence modules over (R,≤), to discuss some techniques from category theory (and originally from representation theory) used in persistent homology. Although not reviewed in this chapter, we cite [27, Theorems 3 and 4], where the decomposition of ladder modules is addressed. 4.1 Interval decomposition The idea of combining two ‘simple’ modules and get a ‘bigger’ one is through direct sums. Definition 4.1.1 (Direct sum [16, Sec.2.5]). The direct sum W=U⊕Vof two persistence modules U,V∈VecPis the pointwise direct sum in Vec: Wt=Ut⊕Vtwt s=ut s⊕vt s This generalizes to arbitrary (finite or infinite) direct sums. Remark 4.1.2.Wis still a module over P, as VecPis closed under direct sums. The notion of direct sum of vector spaces coincides with coproduct in a general category. Also, as VecPis an abelian category, there is a canonical isomorphism between (finite) products and coproducts. 40 on the categorical theory of persistence modules Definition 4.1.3 (Indecomposable persistence module [16, Sec.2.5]). A persistence module Wis indecomposable if the only decompositions W=U⊕Vare the trivial decompositions W⊕0and 0⊕W, where 0is the zero persistence module consisting of zero vector spaces 0and identity morphisms between them. Our basic building blocks are intervals. Definition 4.1.4 (Interval [13, Def.2.3]). An interval τ-module (with τan orientation) or simply an interval Iτ(b, d)where 1≤b≤d≤n= length(τ)represents a feature which ‘persists’ over an interval specified by its birth index band its death index d. For example, given that persistence modules are build over a field F, the interval Iτ(2,3) with τ= (~τ, ~ τ, ~ τ)is 1FF0. 0 1 1 When the orientation is known, we usually drop the subscript and write I(b, d). When Idenotes an interval in a totally ordered set (e.g. in (R,≤)), we write I(I)to denote the interval module supported over I. Interval modules are indecomposable [16, Prop.2.6]. In the case of τ-modules, the converse is also true. The theory of zigzag persistence is based on a special case of Gabriel’s theorem [29] (that says which quiver representations are finitely decomposable) that applies to representations of An(τ)quivers: Theorem 4.1.5. [13, Th.2.5] The indecomposable τ-modules are the intervals I(b, d). Equivalently, every τ-module can be written as a direct sum of intervals. However, for other kinds of persistence modules like ones that are not pointwise finite dimensional, not all indecomposable persistence modules admit an interval decomposition. See [16, Th.2.8(3)] for an example. In case that a persistence module is decomposable into interval modules, the next result asserts that the decomposition is unique. Proposition 4.1.6 (Krull-Remak-Schmidt-Azumaya).Let Vbe a persistence module with two different interval decompositions V=M m∈M I(bm, dm) = M n∈N I(b0 n, d0 n). Then there is some permutation σ:M→Nsuch that I(bm, dm) = I(b0 σ(m), d0 σ(m))for all m∈M. This is proved for τ-modules in [13, Prop.2.2], and for finite type persistence diagrams (i.e. ones that admit such interval decompositions) in Vec(R,≤)in [11, Cor.4.7] 4. decomposition of persistence modules 41 and [16, Th.2.7]. The uniqueness of the interval decomposition can be thought of as the uniqueness up to isomorphism of coproducts. Once our goal of decomposing persistence modules is formalized as finding a direct sum of intervals, realise that the essence of a decomposition is just the birth and death indices. This data is encoded in persistence diagrams and barcodes. Definition 4.1.7 (Persistence [13, Def.2.6]). Let Vbe a persistence module of length ndecomposable as I(b1, d1)⊕ · · · ⊕ I(bN, dN). The persistence of Vis defined to be the multiset Pers(V) = {[bj, dj]⊆ {1, . . . , n} | j= 1, . . . , N} Proposition 4.1.6 asserts that this definition is unique up to reordering. Pers(V)is represented graphically as a set of lines against a single axis (the barcode), or as a multiset of points in R2lying on or above the diagonal in the positive quadrant (the persistence diagram). See Figure 4.2 for an example of both. These graphical representations sometimes replace the notation of Pers(V)to dgm(V)[16, Sec.2.6] or B(V)[6], but they refer ultimately to the same data. 4.2 Decomposition algorithm for zigzag modules Theorem 4.1.5 is the relation between quiver representations and zigzag modules: Out of the many classes of quiver representations, Anquivers (graphs) have the same structure as zigzag modules, which can be decomposed as a sum of intervals thanks to this corollary of Gabriel’s theorem. Isomorphism classes of persistence diagrams of zigzag modules are thus a special case of the classification problem for quiver representations. Theorem 4.1.5 is an existence theorem. Carlsson and De Silva give in [13] a constructive proof of it and build an algorithm to compute the interval summands of a given τ-module. We will give here a brief summary of the proof and the algorithm, applying it at the end in an example. The general strategy is to construct the decomposition by an iterative process. Definition 4.2.1 (Submodule, summand, direct sum [13, 2.2]). A submodule Wof aτ-module Vis defined by subspaces for all i: Wi⊆Vis.t.    ~τi(Wi)⊆Wi+1 case ~τi Wi⊇ ~ τi(Wi+1)case ~ τi A submodule Wis called a summand of Vif there exists a submodule X⊆Vwhich is complementary to W, i.e. Vi=Wi⊕Xifor all i. In that case Vis the direct sum of W,X, and we write V=W⊕X. 42 on the categorical theory of persistence modules Remark 4.2.2.A submodule Wof Vcorresponds to an object Wof τMod with a monomorphism W,→V. Filtered vector spaces are filtered objects (introduced in Section 3.4) in Vec. We briefly characterize this category, based on remarks in [13, 3.2], in Proposition 4.2.4 and Proposition 4.2.5. Definition 4.2.3 (Filtn). The category of filtered vector spaces of length nis defined by: •Objects: Sequences of nvector spaces connected by injections. Vcan be for example V1V2· · · Vn. •Morphisms: A morphism f:V→Win Filtnis a set of nlinear maps between two filtered vector spaces of length nsuch that the diagram below commutes. V1V2· · · Vn W1W2· · · Wn. f1f2fn(4.1) Objects of Filtnare filtered objects Vin Vec ordered by n, and morphisms in Filtnare morphisms between filtered objects.Filtncontains intervals of the form I(i, n) = (0,...,0,F,...,F), which constitute the indecomposables, and direct sums of them. Proposition 4.2.4.Filtnis not an abelian category (Definition 2.0.33), since morphisms do not generally have cokernels [13, 3.2]. Proof. Consider V= (0 0 −→ F)and W= (F1 −→ F)two filtered vector spaces in Filtn with n= 2, and a morphism f:V→W. 0F F F f1=0 f2=1 1 f1and f2have cokernels coker(f1) = W1/im(f1) = Fand coker(f2) = W2/im(f2)=0. However coker(f1)→coker(f2)is not a monomorphism, which is the condition for a sequence of vector spaces to be a filtered vector space. Proposition 4.2.5.Filtnis a full subcategory (Definition 2.0.4) of Vecn. Proof. Itisasubcategory, as objects in Filtnare indexed by n. Not all objects in Vecnare in Filtnthough, as only those which are filtrations are in Filtn. Next, let V,Wbe two filtrations. As objects of Vecn,Vand Ware functors from nto Vec. The commutativity condition of a natural transformation α:V→Wis equivalent to (4.1), 4. decomposition of persistence modules 43 thus the ncomponents of αare the linear maps αi:Vi→Withat define a morphism in Filtn. Therefore every morphism in Vecnis also in Filtn, making the latter a full subcategory of the former. A specific filtered vector space can be obtained from a τ-module using the following operator. Definition 4.2.6 (Right-filtration operator [13, Def.3.1]). The right-filtration of aτ-module Vof length nis a a filtered vector space R(V)=(R0, R1, . . . , Rn)∈ Filtn+1(1)where the Riare subspaces of Vn, the right-most vector space of V, satisfying the inclusion relations 0 = R0⊆R1⊆ · · · Rn=Vn. R(V)is defined recursively, starting with the left-most vector space V1and incrementing in each step the scope to V1↔V2,V1↔V2↔V3and so on. •Base case: R(V1) = (0, V1)=(R0, R1). •Recursive step: Suppose we have alredy defined R(V1↔ · · · ↔ Vk) = (R0, R1,· · · , Rk) up to a step k < n. Depending on τkbeing ~τkor ~ τk, we define the next step as R(V1↔ · · · ↔ Vk+1) =    (~τk(R0),~τk(R1),· · · ,~τk(Rk), Vk+1)case ~τk (0, ~ τ−1 k(R0), ~ τ−1 k(R1),· · · , ~ τ−1 k(Rk)) case ~ τk (4.2) Example 4.2.7.Let V= (V1 ~τ1 −→ V2), with V1=F2,V2=F3and ~τ1=   1 0 0 1 0 0   Then R(V1) = (0, V1)where 0 = 0 0!V1=h 0 1!, 1 0!i and the next right-filtration would be R(V1 ~τ1 −→ V2)=(~τ1(0),~τ1(V1), V2)with ~τ1(0) =    0 0 0  ~τ1(V1) = h~τ1 0 1!,~τ1 1 0!i=h   0 1 0  ,   1 0 0  iV2=h   0 0 1  ,   0 1 0  ,   1 0 0  i. Definition 4.2.8 (Birth-time index [13, Def.3.6]). The birth-time index b(τ) = (b1, b2, . . . , bn)is a vector of integers biwhich indicate the birth times associated with the subquotients Ri/Ri−1of the right-filtration of a τ-module. This is defined recursively: (1)We have defined an object of Filtnas a sequence of nvector spaces connected by injections, by which R(V)is in Filtn+1 because it consists of n+ 1 vector spaces. 44 on the categorical theory of persistence modules •Base case: For Vof length 1,b(τ) = (1). •Given b(τ1, . . . , τk−1) = (b1, . . . , bk), b(τ1, . . . , τk−1, τk) =    (b1, . . . , bk, k + 1) case ~τk (k+ 1, b1, . . . , bk)case ~ τk Definition 4.2.9 ([13, Def.3.15]). Aτ-module Vis (right-)streamlined if each ~τ is injective and each ~ τis surjective. The following lemmas and theorem lead up to Theorem 4.2.13, which together with Algorithm 1 provide a constructive way of obtaining a decomposition of an arbitrary τ-module. Lemma 4.2.10 (Decomposition Lemma [13, Lemma 3.18]).Le Vbe a streamlined τ-module and let R=R(V). For any decomposition R=S1⊕ · · · ⊕ SN, there exists a unique decomposition V=W1⊕ · · · ⊕ WNsuch that Si=R(Wj)for all j. Theorem 4.2.11 (Interval decomposition for streamlined modules [13, Th.3.19]). Let Vbe a streamlined τ-module of length n, and write dim(R(V)) = (c1, . . . , cn)and b(τ)=(b1, . . . , bn). Then there is an isomorphism of τ-modules V∼ =M q≤i≤n ciI(bi, n) where I(bi, n)is a streamlined interval born in biand dying in n. Given a τ-module V=V1 τ1 ←→ · · · τn−1 ←−→ Vn, the truncation of Vto length k(with 1≤k≤n) is denoted V[k] = (V1 τ1 ←→ · · · τk−1 ←−→ Vk), and its orientation τ[k]is a truncation of τ. Lemma 4.2.12 ([13, Lemma 4.3]).Let V=V1 τ1 ←→ · · · τn−1 ←−→ Vnbe a τ-module of length n. Then there exists a direct-sum decomposition V=V1⊕V2⊕ · · · ⊕ Vn where each Vkis a τ[k]-module supported over the indices {1,2, . . . , k}and is rightstreamlined over that range. 4. decomposition of persistence modules 45 Theorem 4.2.13 (Interval decomposition [13, Th.4.1]). Let Vbe a τ-module. For 1≤k≤n, write the birth vector (bk 1, bk 2, . . . , bk k) = b(τ[k]). Writing R=R(V[k]), define the dimension vector as (ck 1, ck 2, . . . , ck k) =    dim(Rk∩ker(~τk)) (2) case ~τ dim(Rk)−dim(Rk∩im( ~ τk)) case ~ τ(4.3) when k6=n, and (cn 1, cn 2, . . . , cn n) = dim(Rn). Then V=M 1≤k≤n Vk∼ =M 1≤k≤n  M 1≤i≤k ck iI(bk i, k)  .(4.4) Equation (4.3) has to be understood elementwise: Rk∩ker(~τk)is the sequence of vector spaces (Rk 0∩ker(~τk), . . . , Rk k∩ker(~τk)) and dim(Rk∩ker(~τk)) is the vector (ck 1, . . . , ck k). Similarly for ~ τ. A priori zigzag modules generalize persistence modules because they allow the functions between spaces to be forwards or backwards (~τ or ~ τ), but they force the ~τ functions to be injective and ~ τfunctions to be surjective in order to obtain a rightstreamlined module. All intervals into which a module is decomposed die at n. However, later this restriction is lifted, firstly decomposing an arbitrary τ-module in a direct sum of modules which are right-streamlined in their rank by Lemma 4.2.12, and then decomposing these into intervals with Theorem 4.2.11. Finally, one obtains a double direct sum (4.4) of intervals I(bk i, k)with their respective multiplicities ck i, and the intervals are not forced to be born/die at a specific time. The algorithm to compute the right-filtration Rk=R(V[k]), the birth-time index b(τ[k]) and the dimensions ck ifrom (4.3) iteratively through k= 1,2, . . . is given next: 52 on the categorical theory of persistence modules which turns out to be disjoint and covers Vt.ByLemma 4.3.7,F+ It =WIt ⊕F− It and by [19, Lemma 6.1] Vis the direct sum of the submodules WI, which are direct sums of interval modules I(I)by [19, Lemma 5.3]. We have thus reviewed decomposition proofs of two kinds of persistence modules, one of them about zigzag modules alongside a constructive algorithm, and another focusing solely on the categorical techniques for persistence modules over R. These two results support the soundness of taking the barcode of some persistence modules as a representation of the topological information within them. However, it is important to remember that there are other kinds of persistence modules that are not representationfinite, i.e. whose set of indecomposables is infinite. This is for example the case of ladder modules with n≥5, as discussed in [27, Theorems 3 and 4]. 5 Comparison and stability of persistence modules Once the concept of persistent modules is introduced and we know how to decompose certain classes of them, a reasonable question to ask is how we can compare them and obtain a ‘distance’ between their topological features. The notion of ‘closeness’ or ‘distance’ of persistence modules was first quantified by the bottleneck distance. However, other kinds of distances are also used. For example, distance in input data is usually quantified by the Gromov-Hausdorff distance, calculated over a metric space. In this chapter we are going to deal mainly with the interleaving distance, applied both to ladder modules and Vietoris-Rips filtrations. Filtering functions are compared using the L∞distance. Furthermore, this motivates the study of stability, arguably one of the most important results in topological data analysis. Stability theorems relate closeness in different domains, e.g. how close two persistence modules are to how close the input data is. Figure 5.1 gives an overview of distances and stability theorems discussed in this chapter. But first we start by motivating its use by defining the most fundamental metric structure to endow onto the space of persistence modules, the bottleneck distance. 5.1 Bottleneck distance The bottleneck distance was first introduced in [25] to study the stability of persistence diagrams. Definition 5.1.1 (Bottleneck distance). Let X, Y be multisets of points. The bottleneck distance between Xand Yis dB(X, Y ) = inf γsup xky−γ(x)k∞ where x∈Xand y∈Yand γare bijections from Xto Y. 54 on the categorical theory of persistence modules Filtered complex (Interleaving distance) Data in a metric space (Gromov- Hausdorff distance) Data with a filtering function (L∞distance) Persistence module (Interleaving distance) Barcode (Bottleneck distance) Vietoris-Rips Sublevel set HkPers Theorem 5.2.12 Theorem 5.2.9 Proposition 5.2.14 Isometry theorem Figure 5.1: TDA workflow (double arrows) and stability theorems (single arrows). One can start either with data in a metric space or with a filtering function, from which one obtains a filtered simplicial complex. The homology functor produces the persistence module, and finally this is represented by a barcode. The ‘comparison distance’ used in each box is indicated between parenthesis. Single arrows indicate stability theorems between metrics in different boxes. Inspired by the diagram in [10, p.8]. The bottleneck distance between two persistence modules V,Wis understood to be between their persistence diagrams Pers(V)and Pers(W)extended with a set of diagonal points with infinite multiplicity [27, Eq.3.9]. This distance has some restrictive conditions like the continuity of the filtration function and triangulability of the space, and the next distance is introduced in [14] to address these limitations. 5.2 Interleaving distance Bottleneck distances are difficult to generalize to the multidimensional case (that is, where the indexing set is multidimensional), and the interleaving distance provides a good alternative [33, p.4]. To present the interleaving distance, first we have to talk about isomorphic persistence modules. Two persistence modules V,W∈Vec(R,≤)are isomorphic if there are maps Φ∈Hom(V,W),Ψ∈Hom(W,V)such that ΦΨ = 1Vand ΨΦ = 1W[16, Ch.4]. 5. comparison and stability of persistence modules 55 This condition is however too strong against uncertainty and noise in data. Therefore an ‘approximate isomorphism’ is defined in terms of shifted morphisms, which we defined for filtrations in Definition 3.4.9. The definition adapted for persistence modules in Vec(R,≤)is given next. Definition 5.2.1 (Shifted morphism [16, Sec.4.1]). Aδ-shifted morphism (or shifted homomorphism)Φof degree δbetween persistence modules in Vec(R,≤)shifts the value of the persistent index by δ: Φ = (φt:Vt→Wt+δ|t, δ ∈R)∈Homδ(V,W) such that the following diagram commutes: VsVt Ws+δWt+δ vt s φsφt wt+δ s+δ Homδ(V,W)is the set of all δ-shifted morphisms from Vto W.Endδ(V)are endomorphisms of degree δin V, i.e. families of morphisms from Vto itself shifting the persistent index by δ. An important example is 1δ V= (vt+δ t:Vt→Vt+δ)∈Endδ(V) Note that by definition Φ1δ U=1δ VΦbecause composition is unique and associative. Both Homδand Endδare given categorical definitions in terms of translation functors in [11, Sec.3], [10, Sec.2.2]. Once a δ-shifted morphism between persistence modules is defined, we can combine two δ-shifted morphisms going back and forth between two persistence modules to define a distance between them. Definition 5.2.2 (δ-interleaved persistence modules [16, Sec.4.2]). Two persistence modules V,Ware said to be δ-interleaved if there are maps Φ∈Homδ(V,W),Ψ∈ Homδ(W,V)such that ΦΨ = 12δ VΨΦ = 12δ W 56 on the categorical theory of persistence modules and these four diagrams commute for all s≤t: VsVt Ws+δWt+δ vt s φs φt wt+δ s+δ Vs−δVs+δ Ws vs+δ s−δ φs−δψs Vs+δVt+δ WsWt vt+δ s+δ wt s ψs ψt Vs Ws−δWs+δ φs ws+δ s−δ ψs−δ (5.1) Definition 5.2.3 (Interleaving distance [16, Sec.5.1]). The interleaving distance is defined as the infimum over such δ-interleavings: dI(V,W) = inf{δ|V,Ware δ-interleaved} Two important inequalities involving interleaving distances are the triangle inequality for any three persistence modules U,Vand W[16, Prop.5.3]: dI(U,W)≤dI(U,V)+dI(V,W) and the next proposition: Proposition 5.2.4 ([10, Th.2.5.5]).Let F, G ∈CPbe two persistence modules, where Pis any preordered set as a category, and Cis any category. Let H:C→Dbe any functor from Cto any other category D. Then dI(HF, HG)≤dI(F, G). A theorem that relates the interleaving distance with the bottleneck distance is the isometry theorem. Theorem 5.2.5 (Isometry theorem [16, Th.5.14]). Let V,Wbe two p.f.d.(1) persistence modules in Vec(R,≤). Then dI(V,W)=dB(Pers(V),Pers(W)) The interleaving distance dIis a generalization of the bottleneck distance dBin the sense that dBcan be recovered as a specific interleaving distance [11, 4.3]. Additionally, Theorem 5.2.5 is also interesting because the interleaving distance can (1)The cited theorem is stronger, as it applies to q-tame persistence modules (ones where rank(vt s)< ∞whenever s < t). A p.f.d. persistence module has dim(Vs)<∞, so it implies q-tameness (cf. [16, p.51]). 5. comparison and stability of persistence modules 57 be defined in more situations than the bottleneck distance, for example on multidimensional persistence modules [33] and filtrations [14]. It has been generalized also to include other kinds of metrics as particular cases: the Hausdorff distance, L∞-distance on Rnand the L∞-distance between filtering functions among others [21, Sec.3]. This means that all boxes in Figure 5.1 have an associated interleaving distance, and that this is a useful concept to think about when comparing these objects. In fact, in the next two subsection we are going to study interleaving distances applied to ladder modules and Vietoris-Rips filtrations, and give for each of them a boundness relation (Proposition 5.2.8 and Proposition 5.2.14). 5.2.1 Interleavings between ladder modules We borrow the notation from Definition 5.2.2 and define δ-interleavings and interleaving distance between ladder modules. Definition 5.2.6 (δ-interleaving of ladder modules). Given δ≥0, two ladder modules α, β ∈(Vec2)(R,≤)(interpreted here as (R,≤)-indexed arrows αi:Vi→Wiand βi:V0 i→W0 i) are δ-interleaved if there exist δ-shifted morphisms Φ∈Homδ(α, β),Ψ∈Homδ(β, α) such that ΨΦ = 12δ α,ΦΨ = 12δ β. More expansively, this means that there are pairs of maps φt:αt→βt+δψt:βt→αt+δ defined for all t∈R, such that the following diagrams αsαt βs+δβt+δ φs φt αs−δαs+δ βs φs−δψs αs+δαt+δ βsβt ψs ψt αs βs−δβs+δ φs ψs−δ (5.2) in Vec2commute for all s<t. The interleaving distance between ladder modules is defined in an analogous man- 58 on the categorical theory of persistence modules ner as dI(α, β) = inf{δ≥0|α, β are δ-interleaved}(5.3) where we set dI(α, β) = ∞if αand βare not δ-interleaved for any δ≥0. These definitions of δ-interleaved ladder modules and interleaving distance are special cases of interleaving of diagrams [11, Def.3.1, Def.3.2], setting their arbitrary category Dto be Vec2. (5.3) fits also in the definition of interleaving distance given for generalized persistence modules in [21]. As noted in [11, Sec.3], dIfails to be a metric because it can take the value ∞ and dI(α, β) = 0 does not imply α∼ =β. Notice that if αand βare 0-interleaved, then α∼ =β. However dI(α, β)=0only implies that αand βare δinterleaved for all δ > 0. This does not imply that α∼ =β. To see why this is the case, consider the next example. Example 5.2.7.Consider V,W∈Vec(R,≤), where Vs= 0 for all s∈Rand Wsis the ground field for s= 0 but is otherwise 0. V· · · → 0→0→0→ · · · W· · · → 0→F→0→ · · · For all δ > 0, the four diagrams commute so Vand Ware δ-interleaved. However, replacing δ= 0 and s= 0, the diagram Vs Ws−δWs+δ φs ψs−δ becomes 0 F F φ0 id ψ0 which doesn’t commute, thus they are not 0-interleaved, because in fact, αβ. Notice that αi:Vi→Wiand βi:V0 i→W0 iare arrows between vector spaces, which individually form persistence modules V= (Vi)i∈R,V0= (V0 i)i∈R,W= (Wi)i∈R, W0= (W0 i)i∈R, in Vec(R,≤). By Corollary 2.0.24,αand βare isomorphic to objects of (Vec(R,≤))2, so α∈Hom(V,W), β ∈Hom(V0,W0). We next give a lower bound of the interleaving distance between ladder modules. 5. comparison and stability of persistence modules 59 Proposition 5.2.8.Let Cbe any category, and let V,V0,W,W0∈C(R,≤). Given two ladder modules α∈Hom(V,W)and β∈Hom(V0,W0), their interleaving distances are lower bounded by max{dI(V,V0),dI(W,W0)} ≤ dI(α, β).(5.4) Proof. αand βare objects of (C2)(R,≤). Let dI(α, β) = δ. This implies there are maps Φand Ψthat define a δ+-interleaving: for any  > 0, the four diagrams (5.1) commute for δ+=δ+for all s≤t. These diagrams in C2can be written as diagrams in C, like shown: αsαt βs+δ+βt+δ+ φs φt VsVt V0 s+δ+V0 t+δ+ WsWt W0 s+δ+W0 t+δ+ αs φs φt αt βs+δ+ βt+δ+ φs φt (5.5) and similarly for the other three diagrams. Inspecting the lower and upper planes, one can observe that αand βbeing δ+-interleaved implies Wand W0are at most δ+-interleaved (lower plane), and Vand V0too (upper plane): dI(V,V0)≤dI(α, β) dI(W,W0)≤dI(α, β) 5.2.2 Stability and interleavings of filtrations Let K∈SCpx and fK,gKtwo filtering functions. The distance between fKand gK is measured by the L∞distance: kfK−gKk∞= sup σ∈K kfK(σ)−gK(σ)k. From fKone obtains a filtered complex FKapplying the sublevelset construction (Example 3.4.4), and similarly from gK,GK. The following is a stability theorem of the interleaving distance between filtered complexes with respect to the L∞distance between their filtering functions, and is sometimes called the functional stability theorem. 60 on the categorical theory of persistence modules Theorem 5.2.9. dI(FK, GK)≤ kfK−gKk∞ Proof. This theorem is the first part of [11, Th.5.1]. There is also a notion of stability of filtration functors with respect to the underlying metric space. As mentioned in the introduction of this chapter, the ‘closeness’ between two metric spaces is given by the Gromov-Hausdorff distance, defined here in terms of correspondences. Definition 5.2.10 (Correspondence [12, Def.7.3.17]). Let Xand Ybe two sets. The set M⊂X×Yis a correspondence between Xand Yif •for all x∈Xthere exists some y∈Ywith (x, y)∈ M, and •for all y∈Ythere exists some x∈Xwith (x, y)∈ M. Definition 5.2.11 (Gromov-Hausdorff distance [12, Th.7.3.25]). The Gromov-Hausdorff distance between metric spaces (X, dX)and (Y, dY)is dGH(X, Y ) = 1 2inf Msup (x1,y1)∈M (x2,y2)∈M |dX(x1, x2)−dY(y1, y2)| where the infimum is taken over all correspondences M. Given two datasets with similar geometric structure, quantified by the Gromov- Hausdorff distance, a filtration is stable if the filtrations of both datasets, quantified by the bottleneck distance, is also similar. The next theorem states that the Vietoris- Rips filtration is stable. Theorem 5.2.12 (Stability of Rips filtration [17, p.2]). For (X, dX)and (Y, dY) finite metric spaces and all positive integers k, dBPers HkVR(X),PersHkVR(Y)≤2·dGH(X, Y ). The definition of interleaving distance can be used also for Vietoris-Rips filtrations as objects of SCpx(R,≤), before using the simplicial homology functor Hk:SCpx → Vec. A shifted morphism Φshifts the value of the parameter: Φ = (φr:VRr(X)→ VRr+δ(Y)|r, δ ∈R)∈Homδ(VR(X),VR(Y)) such that the corresponding diagram commutes. Two Vietoris-Rips filtrations are δ-interleaved similarly to regular persistence modules and ladder modules. 5. comparison and stability of persistence modules 61 Remark 5.2.13.The existence of a shifted morphism between Vietoris-Rips filtrations can be specified as a relation between the metric spaces (or alternatively, between the distance matrices of the underlying point clouds) by Corollary 3.4.22. Moreover, this allows to define a δ-interleaving analogous to the one defined for persistence modules (Definition 5.2.2) and ladder modules (Definition 5.2.6) and an interleaving distance. This interleaving distance can be used as an upper bound, as proposed next. Proposition 5.2.14.The interleaving distance between two Vietoris-Rips filtrations VR(X),VR(Y)and the interleaving distance of their persistence modules (obtained by applying the simplicial homology functor Hk) satisfy: dIHk(VR(X)), Hk(VR(Y))≤dIVR(X),VR(Y). Proof. Recall (R,≤)is a preordered set as a category (Example 2.0.15). Apply Proposition 5.2.4 to VR(X),VR(Y)∈SCpx(R,≤)and Hk:SCpx →Vec. This last proposition gives an upper bound to the interleaving distance between two persistence modules obtained from Vietoris-Rips filtrations, without having to compute the homology of the filtrations. This may be interesting from an applied viewpoint, as a direct implementation of classical homology computation by linear algebra methods yields an O(N3)algorithm [37]. 68 on the categorical theory of persistence modules [11] Bubenik, P., and Scott, J. A. Categorification of Persistent Homology. Discrete and Computational Geometry 51, 3 (2014), 600–627. [12] Burago, D., Burago, I. D., and Ivanov, S. A course in metric geometry. No. v. 33 in Graduate studies in mathematics. American Mathematical Society, Providence, RI, 2001. [13] Carlsson, G., and de Silva, V. Zigzag Persistence. Foundations of Computational Mathematics 10, 4 (2010), 367–405. [14] Chazal, F., Cohen-Steiner, D., Glisse, M., Guibas, L. J., and Oudot, S. Y. Proximity of persistence modules and their diagrams. In Proceedings of the 25th annual symposium on Computational geometry - SCG ’09 (Aarhus, Denmark, 2009), ACM Press, p. 237. [15] Chazal, F., Cohen-Steiner, D., Guibas, L. J., Mémoli, F., and Oudot, S. Y. Gromov-Hausdorff Stable Signatures for Shapes using Persistence. Computer Graphics Forum 28, 5 (July 2009), 1393–1403. [16] Chazal, F., de Silva, V., Glisse, M., and Oudot, S. The Structure and Stability of Persistence Modules. SpringerBriefs in Mathematics. Springer International Publishing, Cham, 2016. [17] Chazal, F., de Silva, V., and Oudot, S. Persistence stability for geometric complexes. arXiv:1207.3885 [cs, math] (Nov. 2013). [18] Chazal, F., and Michel, B. An introduction to Topological Data Analysis: fundamental and practical aspects for data scientists. arXiv:1710.04019 [cs, math, stat] (Feb. 2021). [19] Crawley-Boevey, W. Decomposition of pointwise finite-dimensional persistence modules. Journal of Algebra and its Applications 14, 5 (July 2014), 1–8. [20] de Silva, V., Morozov, D., and Vejdemo-Johansson, M. Dualities in persistent (co)homology. Inverse Problems 27, 12 (Dec. 2011), 124003. [21] de Silva, V., Munch, E., and Stefanou, A. Theory of interleavings on categories with a flow. arXiv 33, 21 (2017), 583–607. [22] de Silva, V., and Vejdemo-Johansson, M. Persistent Cohomology and Circular Coordinates. Proceedings of the 25th annual symposium on Computational geometry - SCG ’09 (2009), 227. [23] Deligne, P. Théorie de Hodge, II. Publications Mathématiques de l’Institut des Hautes Études Scientifiques 40 (1970), 5–57. BIBLIOGRAPHY 69 [24] Dey, T. K., Fan, F., and Wang, Y. Computing topological persistence for simplicial maps. Proceedings of the Annual Symposium on Computational Geometry (2014), 345–354. [25] Edelsbrunner, Letscher, and Zomorodian. Topological Persistence and Simplification. Discrete & Computational Geometry 28, 4 (Nov. 2002), 511–533. [26] Edelsbrunner, H., and Harer, J. Computational topology: an introduction. American Mathematical Society, Providence, R.I, 2010. [27] Escolar, E. G., and Hiraoka, Y. Persistence Modules on Commutative Ladders of Finite Type. Discrete and Computational Geometry 55, 1 (2016), 100–157. [28] Fong, B., and Spivak, D. I. Seven Sketches in Compositionality: An Invitation to Applied Category Theory. arXiv:1803.05316 [math] (Oct. 2018). [29] Gabriel, P. Unzerlegbare Darstellungen I. Manuscripta mathematica 6, 1 (Mar. 1972), 71–103. [30] Ghrist, R. Barcodes: The persistent topology of data. Bulletin of the American Mathematical Society 45, 01 (Oct. 2007), 61–76. [31] Hatcher, A. Algebraic Topology. Cambridge University Press, Cambridge ; New York, 2002. [32] Lawvere, F. W. Metric spaces, generalized logic, and closed categories. Rendiconti del Seminario Matematico e Fisico di Milano 43, 1 (1973), 135–166. [33] Lesnick, M. The Theory of the Interleaving Distance on Multidimensional Persistence Modules. Foundations of Computational Mathematics 15, 3 (June 2015), 613–650. [34] Mac Lane, S. Categories for the Working Mathematician, vol. 5 of Graduate Texts in Mathematics. Springer New York, New York, NY, 1978. [35] McCleary, A., and Patel, A. Positivity of Multiparameter Persistence Diagrams and Bottleneck Stability. arXiv:1905.13220 [math] (Oct. 2020). [36] Memoli, F. A Distance Between Filtered Spaces Via Tripods. arXiv:1704.03965 [cs, math] (Dec. 2017). [37] Morozov, D. Persistence algorithm takes cubic time in worst case. BioGeometry News, Dept. Comput. Sci., Duke Univ 2 (2005). [38] Munkres, J. R. Elements of algebraic topology, 12. ed. Perseus Books, Cambridge, Mass, 2018. 70 on the categorical theory of persistence modules [39] nLab authors. Dagger category. http://ncatlab.org/nlab/revision/ dagger+category/42, May 2021. [40] nLab authors. Filtered object. http://ncatlab.org/nlab/revision/ filtered+object/15, May 2021. [41] nLab authors. Limits and colimits by example. http://ncatlab.org/nlab/ revision/limits+and+colimits+by+example/47, May 2021. [42] nLab authors. Quiver. http://ncatlab.org/nlab/revision/quiver/46, May 2021. [43] Riehl, E. Category theory in context. Aurora: Dover modern math originals. Dover Publications, Mineola, New York, 2016. [44] Tausz, A., and Carlsson, G. Applications of Zigzag Persistence to Topological Data Analysis. arXiv:1108.3545 [cs] (Aug. 2011). [45] Xia, K., and Wei, G.-W. Persistent homology analysis of protein structure, flexibility, and folding. International Journal for Numerical Methods in Biomedical Engineering 30, 8 (Aug. 2014), 814–844.