Rank-based persistence

Mattia G. Bergomi Note: Champalimaud Research, Champalimaud Centre for the Unknown, 1400-038 Lisbon, Portugal. ${$mattia.bergomi, pietro.vertechi $}$@neuro.fchampalimaud.org Pietro Vertechi^†^†footnotemark:

Abstract

Persistence has proved to be a valuable tool to analyze real world data robustly. Several approaches to persistence have been attempted over time, some topological in flavor, based on the vector space-valued homology functor, other combinatorial, based on arbitrary set-valued functors. To unify the study of topological and combinatorial persistence in a common categorical framework, we give axioms for a generalized rank function on objects in a target category so that functors to that category induce persistence functions. We port the interleaving and bottleneck distances to this novel framework and generalize classical equalities and inequalities. Unlike sets and vector spaces, in many categories the rank of an object does not identify it up to isomorphism: to preserve information about the structure of persistence modules, we define colorable ranks, persistence diagrams and prove the equality between multicolored bottleneck distance and interleaving distance in semisimple Abelian categories. To illustrate our framework in practice, we give examples of multicolored persistent homology on filtered topological spaces with a group action and labeled point cloud data.

Keywords

rank, persistence, categorification, regular category, abelian category, semisimple category, classification, group action, point cloud, poset, bottleneck, interleaving

AMS subject classification

18E10, 18A35, 55N35, 68U05

1 Introduction

Topological persistence offers valuable tools to give encompassing representations of the geometry and topology of sampled objects, even in high dimension. Moreover, persistent homology and its encoding via persistence diagrams are endowed with essential properties in data analysis, such as stability [9] and resistance to occlusions [10]. Equipped with these fundamental features, persistent homology has been successfully employed in a vast number of applications [15].

We provided a first generalized theory of persistence to concrete categories in [4]. This first generalization allows one to define persistence in a very general setting, that includes not only topological spaces or weighted graphs but also arbitrary categories of presheaves. However, it fails to fully generalize the classical theory, for it does not show how to define persistence functions based on functors to the target category of vector spaces (such as the homology functors). The primary technique developed in [4] to define stable persistent functions (named coherent sampling) requires using finite sets as target category, thus failing to recover, for example, the study of higher persistent homology groups.

Here, we aim at providing a new categorical generalization, embracing both the classical theory and the framework described in [4]. With this aim in mind, we first decompose classical persistent homology into its basic ingredients: 1. A filtration in a source category $\mathbf{Top}$ . 2. A functor $H_{k}$ from the source category to a target category $\mathbf{FinVec}_{\mathbb{K}}$ . 3. A notion of rank in the target category (the dimension of the vector space).

Thereafter, we explore which axioms each of these ingredients must respect for the classical results on persistence diagrams, bottleneck and interleaving distances to hold.

Not only we establish a common generalization of the combinatorial [4] and topological approach to persistence [12], but we also find examples of novel target categories, different from $\mathbf{FinSet}$ or $\mathbf{FinVec}_{\mathbb{K}}$ , giving rise to persistence modules with structure. Of particular interest is the case of persistent group representations, which arises naturally in the study of filtrations of topological spaces or simplicial objects with a group action compatible with the filtering function. By coloring the resulting persistence diagram, we are able to recover a notion of similarity that respects the structure of our target category, e.g., the group action. This construction holds in any target semisimple Abelian category: we show examples arising from labeled point cloud datasets, relevant for instance in a machine learning context.

The paper is organized as follows. In section 2 we determine what are the features of the functions cardinality of a set and dimension of a vector space that make them suitable as a notion of rank of an object in a target category. We lay down an axiomatic foundation for such rank functions in the general setting of regular categories and provide as an example the length of an object in an Abelian category, which naturally generalizes the dimension of a vector space. In section 3, we first show how a functor from an arbitrary category to a regular category equipped with a rank function defines a categorical persistence function. Then, we port the classical notions (e.g. regular and critical value, tameness and cornerpoint multiplicity) to the categorical setting and use them to define persistence diagrams. We show how persistence diagrams relate to persistence modules in the case of a semisimple category. Finally, we discuss the notions of interleaving and bottleneck distance and prove the inequality between them, i.e. that the interleaving distance is always greater or equal than bottleneck, with great generality. Equality between the two distances requires additional assumptions: in section 4 we discuss how, in the case of a semisimple target category, one can color the persistence diagram: a bottleneck distance computed allowing only color-preserving bijections is then equal to the interleaving distance. We finally show examples of multicolored persistence in the case of topological spaces with group actions and labeled point clouds.

For the sake of readability, we provide and exemplify basic definitions of category theory in appendix A.

2 Rank functions in regular categories

Historically, there have been two different treatments of persistent homology, one associating to a map of topological spaces the cardinality of the image of a map of sets [16], the other the dimension of the image of a map of vector spaces [13]. To unify them in a common framework, we introduce here the concept of ranked category, i.e. a regular category (definition A.3.2) equipped with an integer-valued rank function on objects.

The reason behind choosing to work with regular categories is that, by definition, every morphism $X\xrightarrow{\phi}Y$ in a regular category $\mathbf{R}$ can be factored in $X\xrightarrow{\varepsilon}\mathrel{\mkern-14.0mu}\rightarrow Z\xhookrightarrow{\mu}Y$ such that $\phi=\mu\circ\varepsilon$ , where $\mu$ is a monomorphism (definition A.1.2) and $\varepsilon$ a regular epimorphism (definition A.3.1), which in turn gives a good notion of image of a morphism ( $Z$ being the image of $X\xrightarrow{\phi}Y$ ). This notion of image will allow us to define persistence functions based on the rank of the image of a morphism. As both monomorphisms and regular epimorphisms are preserved by pullbacks (definition A.2.9), we will be able to prove classical properties of persistence by building appropriate diagrams.

Definition 1.

Let $\mathbf{R}$ be a regular category. Given a lower-bounded function $r:\textnormal{Obj}(\mathbf{R})\to\mathbb{Z}$ , we say that $r$ is a rank function if:

1.

For any monomorphism $A\hookrightarrow B$ , $r(A)\leq r(B)$
2.

For any regular epimorphism $B\twoheadrightarrow D$ , $r(B)\geq r(D)$

For any pullback square:

where $\iota_{1},\iota_{2}$ are monomorphisms and $\pi_{1},\pi_{2}$ are regular epimorphisms, the following inequality holds:

r(B)-r(A)\geq r(D)-r(C)

We say that a rank function $r$ is strict if the inequalities in conditions 1 and 2 are strict unless the morphisms are invertible. If furthermore $\mathbf{R}$ has an initial object $\emptyset$ and $r(\emptyset)=0$ , we say that $r$ is $0$ -based. A ranked category $(\mathbf{R},r)$ is simply a regular category $\mathbf{R}$ equipped with a rank function $r$ .

The pullback requirement in the third condition is not necessary: this will prove useful in the following sections when working with functors that do not preserve pullback squares.

Proposition 1.

Given a ranked category $(\mathbf{R},r)$ , for any commutative square (not necessarily pullback):

where $\iota_{2}$ is a monomorphism and $\pi_{2}$ is a regular epimorphism, the following inequality holds:

r(B)-r(A^{\prime})\geq r(D)-r(C)

Proof.

We can build the pullback square:

where $\iota_{1}$ is a monomorphism (as it is pullback of a monomorphism) and $\pi_{1}$ is a regular epimorphism (as it is pullback of a regular epimorphism).

Therefore $r(B)-r(A)\geq r(D)-r(C)$ . We have a natural monomorphism $A^{\prime}\hookrightarrow A$ , therefore, by property 1:

r(B)-r(A^{\prime})\geq r(B)-r(A)\geq r(D)-r(C)

∎

Proposition 2.

If a functor $F:\mathbf{Q}\to\mathbf{R}$ preserves the image factorization, i.e. it preserves monomorphisms and regular epimorphisms, and $r$ is a rank function on $\mathbf{R}$ , then $r\circ F:\textnormal{Obj}(\mathbf{Q})\to\mathbb{Z}$ is a rank function on $\mathbf{Q}$ .

Proof.

As $F$ preserves monomorphisms, given a monomorphism $A\hookrightarrow B$ we have a monomorphism $F(A)\hookrightarrow F(B)$ and therefore $r(F(A))\leq r(F(B))$ . Similarly given a regular epimorphism $B\twoheadrightarrow D$ we have a regular epimorphism $F(B)\twoheadrightarrow F(D)$ so $r(F(B))\geq r(F(D))$ . Finally, given a pullback square:

We have a commutative square (not necessarily pullback):

By proposition 1 we have $r(F(B))-r(F(A))\geq r(F(D))-r(F(C))$ ∎

This in particular applies to regular functors, i.e. functors that preserve regular epimorphisms and finite limits, as preserving limits implies preserving monomorphisms.

2.1 Fiber-wise rank functions

In this section we formalize the notion of fiber-wise rank function, i.e. a function respecting the assumptions of definition 1, whose behavior on regular epimorphisms can be determined from fibers on “points” (see example A.2.6).

Definition 2.

Given a regular category $\mathbf{R}$ with terminal object pt, we say that a function $r:{\textnormal{Obj}}(\mathbf{R})\to\mathbb{Z}$ is fiber-wise if, for all regular epimorphism $B\overset{\phi}{\twoheadrightarrow}D$ , we have the following equality:

r(B)-r(D)=\sum_{\iota\in\textnormal{Hom}({\textnormal{pt}},D)}(r(B\times_{D}^{\iota}{\textnormal{pt}})-r({\textnormal{pt}}))

(1)

where the $B\times_{D}^{\iota}{\textnormal{pt}}$ realizes the pullback:

The conditions of definition 1 become easier to prove in the case of fiber-wise functions.

Proposition 3.

Let $\mathbf{R}$ be a regular category with terminal object pt and $r:\textnormal{Obj}(\mathbf{D})\to\mathbb{Z}$ a lower-bounded function such that:

1.

For any monomorphism $A\hookrightarrow B$ , $r(A)\leq r(B)$
2.

For any regular epimorphism $A\twoheadrightarrow{\textnormal{pt}}$ , $r(A)\geq r({\textnormal{pt}})$
3.

$r$ is fiber-wise

Then $r$ defines a rank function on $\mathbf{R}$ .

Proof.

We will prove that $r$ respects the assumptions of definition 1. It obviously respects the first assumption. It also respects the second as, given $A\twoheadrightarrow C$ :

r(A)-r(C)=\sum_{\iota\in\textnormal{Hom}({\textnormal{pt}},C)}(r(A\times_{C}^{\iota}{\textnormal{pt}})-r({\textnormal{pt}}))

and the right-hand side is $\geq 0$ as it is a sum of nonnegative quantities. To verify assumption 3, let us consider an inclusion ${\textnormal{pt}}\xhookrightarrow{\iota}C$ and the following diagram, where all squares are pullback

As the outermost square is pullback, we have an isomorphism $A\times_{C}^{\iota}{\textnormal{pt}}\simeq B\times_{D}^{\iota_{2}\circ\iota}$ , thus

	$\displaystyle r(A)-r(C)$	$\displaystyle=\sum_{\iota\in\textnormal{Hom}({\textnormal{pt}},C)}(r(A\times_{C}^{\iota}{\textnormal{pt}})-r({\textnormal{pt}}))=\sum_{\iota\in\textnormal{Hom}({\textnormal{pt}},C)}(r(B\times_{D}^{\iota_{2}\circ\iota}{\textnormal{pt}})-r({\textnormal{pt}}))$
		$\displaystyle\leq\sum_{\iota^{\prime}\in\textnormal{Hom}({\textnormal{pt}},D)}(r(B\times_{D}^{\iota^{\prime}}{\textnormal{pt}})-r({\textnormal{pt}}))=r(B)-r(D)$

where the inequality comes from the fact that all summands are nonnegative and one sum has all the summands of the other plus potentially some more. ∎

Under the stronger assumptions of Abelian category (definition A.3.5), the fiber-wise condition simplifies greatly. As Abelian categories have a null object, given an epimorphism $B\overset{\phi}{\twoheadrightarrow}D$ , eq. 1 is equivalent to $r(B)-r(D)=r(ker(\phi))-r(0)$ , where of course $ker(\phi)\hookrightarrow B\overset{\phi}{\twoheadrightarrow}D$ is a short exact sequence.

Proposition 4.

Let $\mathbf{R}$ be an Abelian category. Then $r:\textnormal{Obj}(\mathbf{R})\to\mathbb{Z}$ is fiber-wise if and only if for all short exact sequence $A\hookrightarrow B\twoheadrightarrow D$ , $r(A)+r(D)=r(B)+r(0)$ .

In the Abelian case fiber-wise functions require less assumptions to verify the rank properties:

Proposition 5.

Let $\mathbf{R}$ be an Abelian category. If $r:\textnormal{Obj}(\mathbf{R})\to\mathbb{Z}$ is fiber-wise and for all $D\in\textnormal{Obj}(\mathbf{R})$ , $r(0)\leq r(D)$ then $r$ is a rank. Furthermore, if $r(0)=r(D)$ only if $D$ is null then $r$ is strict.

Proof.

We can embed any monomorphism or epimorphism in a short exact sequence $A\hookrightarrow B\twoheadrightarrow D$ where, as $r$ is fiber-wise, $r(0)+r(B)=r(A)+r(D)$ . As $r(0)\leq r(D)$ , $r(B)\geq r(A)$ . Similarly, as $r(0)\leq r(A)$ , $r(B)\geq r(D)$ .

To prove strictness, let us assume for example that $r(A)=r(B)$ , then $r(D)=r(0)$ therefore $D$ is null so $A\simeq B$ . Similarly if $r(B)=r(D)$ then $r(A)=r(0)$ therefore $A$ is null so $B\simeq D$ . ∎

Examples of fiber-wise rank functions

The cardinality function $|-|:\mathbf{FinSet}\to\mathbb{Z}$ is fiber-wise (the terminal object pt being the singleton). Indeed given a surjective map of sets $A\overset{f}{\twoheadrightarrow}D$ :

|A|-|D|=\sum_{d\in D}(|f^{-1}(d)|-1)

$|-|$ is clearly a rank function: it is nondecreasing on monomorphisms and nonincreasing on epimorphisms. $|-|$ is also strict, as a monomoprhism (or an epimorphism) between two sets with the same number of elements is invertible.

The category $\mathbf{FinVec}_{\mathbb{K}}$ is regular and the dimension function is a strict fiber-wise rank. This case can be generalized to a wide variety of Abelian categories. We recall from [14, Sect. 1] that, in an Abelian category an object $X$ has finite length if there exists a series of inclusions:

0\simeq X_{0}\hookrightarrow X1\hookrightarrow\dots\hookrightarrow X_{n}\simeq X

where all quotients $X_{i}/X_{i-1}$ are simple. If such series exists, then $length(X)=n$ If all objects in an Abelian category have finite lenght, we say that the category has finite length.

The function $length$ is $0$ -based and, by [14, Sect. 1], for all short exact sequence $A\hookrightarrow B\twoheadrightarrow D$ , we have $length(B)=length(A)+length(D)$ so, by proposition 4, $length$ is fiber-wise.

Proposition 6.

Given $\mathbf{D}$ an Abelian category of finite length, the function

length:\textnormal{Obj}(\mathbf{D})\to\mathbb{Z}

is a strict $0$ -based fiber-wise rank.

Proof.

$length$ is nonnegative, and $length(X)=0$ if and only if $X$ is initial so, by proposition 5, it is a strict $0$ -based fiber-wise rank. ∎

The rank function $length$ is is characterized by the following two features: 1. It is $0$ -based and fiber-wise. 2. It has value $1$ on simple objects. Furthermore $length$ and $|-|$ share the additive property, i.e. given two objects $X,Y\in\textnormal{Obj}(\mathbf{R})$ , $r(X\amalg Y)=r(X)+r(Y)$ .

Remark 1.

Even though the category $\mathbf{FinMod}_{\mathbb{Z}}$ of finitely generated Abelian groups (i.e. finitely generated $\mathbb{Z}$ -modules) does not have finite length, we have an image factorization-preserving functor $-\otimes_{\mathbb{Z}}\mathbb{Q}:\mathbf{FinMod}_{\mathbb{Z}}\to\mathbf{FinVec}_{\mathbb{Q}}$ . By proposition 2, the rank function $dim:{\textnormal{Obj}}(\mathbf{FinVec}_{\mathbb{Q}})\to\mathbb{Z}$ induces a rank function on $\mathbf{FinMod}_{\mathbb{Z}}$ , which coincides with the rank of finitely generated Abelian groups.

3 Categorical persistence

In general, given an arbitrary functor $\Psi$ from a source category $\mathbf{C}$ to a regular target category $\mathbf{R}$ equipped with a rank $r$ , we can not naturally define a rank on $\mathbf{C}$ , unless $\mathbf{C}$ is regular and $\Psi$ preserves the image factorization (i.e. monomorphisms and regular epimorphisms), see proposition 2. Unfortunately, these assumptions do not hold in many common cases: for instance the category $\mathbf{Top}$ is not regular and, even though $\mathbf{FinSimp}$ is regular, no homology functor $H_{k}:\mathbf{FinSimp}\to\mathbf{FinVec}$ preserves the image factorization. However, we can still define an integer-valued function on the morphisms of $\mathbf{C}$ , as a categorical persistence function. While categorical persistence functions have very mild assumptions, they will be sufficient to guarantee the classical constructions and results of persistent homology. See table 1 for an intuitive comparison between the classical framework and ours.

3.1 Categorical persistence functions

In persistent homology, the functor $H_{k}$ maps a filtration of topological spaces and a field of coefficients $\mathbb{K}$ , into a sequence of $\mathbb{K}$ -vector spaces $V_{u}$ equipped with maps $V_{u}\to V_{v}$ for $u\leq v$ . The persistent homology group and persistent Betti number correspond to the image of $V_{u}\rightarrow V_{v}$ and its rank, respectively. The aim of this section is to extend this procedure to arbitrary categories.

First, we extend the notion of persistence function from [4], which in turn generalizes persistent Betti number functions.

Definition 3.

Let $\mathbf{D}$ be a category. We say that a lower-bounded function $p:\textnormal{Morph}(\mathbf{D})\to\mathbb{Z}$ is a categorical persistence function if, for all $u_{1}\to u_{2}\to v_{1}\to v_{2}$ , the following inequalities hold:

1.

$p(u1\to v1)\leq p(u2\to v1)$ and $p(u2\to v2)\leq p(u2\to v1)$ .
2.

$p(u2\to v1)-p(u1\to v1)\geq p(u2\to v2)-p(u1\to v2)$ .

If $\mathbf{D}$ is the poset category ${(\mathbb{R},\leq)}$ whose objects are real numbers, with a unique morphism from $u$ to $v$ if $u\leq v$ , then we recover the definition of persistence function from [4]. In some sense, this is a categorification [3] of that notion.

Proposition 7.

Given a functor $F:\mathbf{C}\to\mathbf{D}$ and a categorical persistence function $p$ for $\mathbf{D}$ , $p\circ F$ is a categorical persistence function for $\mathbf{C}$ .

Proof.

Given $u_{1}\to u_{2}\to v_{1}\to v_{2}$ we have, by functoriality, $F(u_{1})\to F(u_{2})\to F(v_{1})\to F(v_{2})$ , so:

(p\circ F)(u_{1}\to v_{1})=p(F(u_{1}\to v_{1}))\leq p(F(u_{2}\to v_{1}))=(p\circ F)(u_{2}\to v_{1})

All other inequalities are proved in an analogous way. ∎

Remark 2.

All functors we consider are covariant. Contravariant functors, if used, will be written in the covariant form $F:\mathbf{C}^{op}\to\mathbf{D}$ .

Classical persistent homology is defined in terms of dimensions of images of maps between vector spaces. The same construction holds in this setting. Given a regular category $\mathbf{R}$ , we denote by $im:\textnormal{Morph}(\mathbf{R})\to\textnormal{Obj}(\mathbf{R})$ the map associating to each morphism its image. Given a rank function $r$ on $\mathbf{R}$ and a functor $F:\mathbf{C}\to\mathbf{R}$ , the function $r\circ im\circ F:\textnormal{Morph}(\mathbf{C})\to\mathbb{Z}$ is a categorical persistence function. We will prove it in the following two propositions.

Proposition 8.

Given a ranked category $(\mathbf{R},r)$ , $r\circ im$ defines categorical persistence function on $\mathbf{R}$ .

Proof.

Let us consider a diagram $u_{1}\to u_{2}\to v_{1}\to v_{2}$ in $\mathbf{D}$ . Then, we have an inclusion

im(u1\to v1)\hookrightarrow im(u_{2}\to v_{1}),

and thus

r(im(u_{1}\to v_{1}))\geq r(im(u_{2}\to v_{1})).

Similarly, we have an epimorphism $im(u_{2}\to v_{1})\twoheadrightarrow im(u_{2}\to v_{2})$ , so $r(im(u_{2}\to v_{1}))\geq r(im(u_{2}\to v_{2}))$ . To prove the second condition of definition 1, we remind that the inequality of the third condition of the same definition holds for all commutative squares and not only pullback squares. Thus, we can build the following commutative diagram:

where $\iota_{1},\iota_{2}$ are monomorphisms and $\pi_{1},\pi_{2}$ are regular epimorphisms. By the third condition of definition 1, we have:

r(im(u_{2}\to v_{1}))-r(im(u_{1}\to v_{1}))\geq r(im(u_{2}\to v_{2}))-r(im(u_{1}\to v_{2}))

∎

By combining proposition 8 and proposition 7, we obtain:

Proposition 9.

Given a ranked category $(\mathbf{R},r)$ and a functor $F:\mathbf{C}\to\mathbf{R}$ , the function $r\circ im\circ F:\textnormal{Morph}(\mathbf{C})\to\mathbb{Z}$ is a categorical persistence function.

Functors to $(\mathbf{FinSet},|-|)$ allow to recover persistent 0-Betti numbers, as well as all examples of coherent sampling in [4] such as blocks, edge-blocks and $\cal F$ -connected components. In this framework , classical persistent homology can be seen as a combination of the functor $H_{k}:\mathbf{FinSimp}\to\mathbf{FinVec}_{\mathbb{K}}$ with the fiber-wise rank function dimension.

Remark 3 ( ${(\mathbb{R},\leq)}$ -indexed diagrams).

Classically, persistent Betti numbers, as well as persistence functions in the sense of [4], are defined on $\Delta^{+}$ , i.e. on pairs $(u,v)\in\mathbb{R}^{2}$ with $u\leq v$ . Categorical persistence functions, on the other hand, are defined more abstractly on ${\textnormal{Morph}}(\mathbf{C})$ . However, as $\Delta^{+}$ is in one-to-one correspondence with ${\textnormal{Morph}}({(\mathbb{R},\leq)})$ , to define a function on $\Delta^{+}$ from a categorical persistence function in $\mathbf{C}$ , we simply need a functor $F:{(\mathbb{R},\leq)}\to\mathbf{C}$ . We denote the category of these functors as $\mathbf{C}^{(\mathbb{R},\leq)}$ and call them ${(\mathbb{R},\leq)}$ -indexed diagrams in $\mathbf{C}$ . They are analogous to filtrations with the difference that, given a ${(\mathbb{R},\leq)}$ -indexed diagram $F$ , we do not require morphisms $F(u)\to F(v)$ to be monomorphisms. As an example, given a topological space $X$ and a real-valued function $f:X\to\mathbb{R}$ , the functor

	$\displaystyle F:{(\mathbb{R},\leq)}\to\mathbf{Top}$
	$\displaystyle u\mapsto f^{-1}((-\infty,u])$

is a ${(\mathbb{R},\leq)}$ -indexed diagram in $\mathbf{Top}$ , with $F(u\leq v)$ given by the inclusion $f^{-1}((-\infty,u])\subseteq f^{-1}((-\infty,v])$ . Similarly, the homology in degree $k$ of the various sublevels also naturally forms a ${(\mathbb{R},\leq)}$ -indexed diagram $u\mapsto H_{k}(f^{-1}((-\infty,u])))$ , where morphisms are no longer necessarily injective.

Refer again to Table 1 for an intuitive list of analogies between the classical and proposed frameworks.

Table 1: From the classical to the categorical framework.

Classical framework	Categorical framework
Topological spaces	Source category $\mathbf{C}$
Vector spaces	Regular target category $\mathbf{R}$
Dimension	Rank function on $\mathbf{R}$
Homology functor	Arbitrary functor from $\mathbf{C}$ to $\mathbf{R}$
Filtration of topological spaces	${(\mathbb{R},\leq)}$ -indexed diagram in $\mathbf{C}$

3.2 Persistence diagrams

After generalizing the main ingredients of persistence, it is important to discuss how the notion of persistence diagram can be defined in this new context. Indeed, persistence diagrams are agile tools, that allow one to easily represent the features determined by the persistence function as a multiset of two-dimensional points. This representation is suitable for both rapid visualization and comparison of filtered objects.

In the following we will work with an arbitrary category $\mathbf{C}$ , a categorical persistence function $p:\textnormal{Morph}(\mathbf{C})\to\mathbb{Z}$ , as well as a ${(\mathbb{R},\leq)}$ -indexed diagram $F$ , and the induced persistence function on $\Delta^{+}$ :

	$\displaystyle p_{F}:\Delta^{+}\to\mathbb{Z}$
	$\displaystyle(u,v)\mapsto p(F(u\leq v))$

To define a persistence diagram we follow the approach given in [4], which in turn draws from the definition of multiplicity of [11] and [17]. We will limit ourselves to the tame case: to do so we will need to generalize the definition of tameness from [5].

Definition 4.

[5, Def. 4.3] Let $F\in\mathbf{C}^{(\mathbb{R},\leq)}$ . Let $I\subset{\mathbb{R}}$ be an interval. We say that $F$ is constant on $I$ if for all $a\leq b\in I$ we have $p_{F}(a,a)=p_{F}(a,b)=p_{F}(b,b)$ . We call $a\in{\mathbb{R}}$ a regular value (resp. right- or left-regular) for $F$ if there is a connected neighborhood (resp. connected right or left neighborhood) $I\;\reflectbox{$\in$}\;a$ such that $F$ is constant on $I$ . Otherwise we call $a$ a critical value. $F$ is tame if it has a finite number of critical values.

In the classical case of finite dimensional vector spaces, the regularity condition requires that maps $F(a)\xrightarrow{\phi}F(b)$ are isomorphisms for $a,b$ in a neighborhood of a regular value (see [5, Def. 4.3]). However, for a strict rank (such as $dim$ or more generally $length$ ) this is equivalent to our condition $r(F(a))=r(F(b))=r(im(\phi))$ thanks to the following lemma:

Lemma 1.

Let $r$ be a strict rank function and $A\xrightarrow{\phi}B$ a morphism such as $r(A)=r(B)=r(im(\phi))$ . Then $\phi$ is an isomorphism.

Proof.

We have a natural regular epimorphism $A\overset{\chi}{\twoheadrightarrow}im(\phi)$ and $r(A)=r(im(\phi))$ , so $\chi$ is an isomorphism. Similarly we have a natural monomorphism $im(\phi)\xhookrightarrow{\psi}B$ and $r(im(\phi))=r(B)$ so $\psi$ is an isomorphism. $\phi=\psi\circ\chi$ is therefore also an isomorphism. ∎

We will need one more lemma to be able to use persistence functions to compute multiplicity of cornerpoints.

Lemma 2.

Let $p$ be a persistence function on a category $\mathbf{C}$ . Then, given a diagram

A\to B\to C\to D

in the category $\mathbf{C}$ , the function:

p(B\to C)-p(A\to C)-p(B\to D)+p(A\to D)

is weakly decreasing in $A$ and $C$ and weakly increasing in $B$ and $D$ .

Proof.

Let us prove that it is weakly decreasing in $A$ , i.e. that given a diagram $A\to A^{\prime}\to B\to C\to D$ , the following inequality holds

		$\displaystyle p(B\to C)-p(A\to C)-p(B\to D)+p(A\to D)\geq$
		$\displaystyle p(B\to C)-p(A^{\prime}\to C)-p(B\to D)+p(A^{\prime}\to D)$

Or, equivalently:

-p(A\to C)+p(A\to D)\geq-p(A^{\prime}\to C)+p(A^{\prime}\to D)

which is simply the second property of definition 3. ∎

Definition 5.

Given $u<v\in\mathbb{R}\cup\{-\infty,+\infty\}$ we define the multiplicity of $u,v$ as the minimum of the following expression, over $I_{u},I_{v}$ disjoint connected neighborhoods of $u$ and $v$ respectively:

p_{F}(\sup(I_{u}),\inf(I_{v}))-p_{F}(\inf(I_{u}),\inf(I_{v}))-p_{F}(\sup(I_{u}),\sup(I_{v}))+p_{F}(\inf(I_{u}),\sup(I_{v}))

We denote this quantity by $\mu(u,v)$ . Whenever $\mu(u,v)>0$ we say $(u,v)$ is a cornerpoint. By convention in this definition we consider $p_{F}(u,v)=\min_{x,y}p_{F}(x,y)$ whenever either $u$ or $v$ is not finite.

Remark 4.

By lemma 2, the quantity:

p_{F}(\sup(I_{u}),\inf(I_{v}))-p_{F}(\inf(I_{u}),\inf(I_{v}))-p_{F}(\sup(I_{u}),\sup(I_{v}))+p_{F}(\inf(I_{u}),\sup(I_{v}))

is weakly increasing in both $I_{u}$ and $I_{v}$ (where the ordering on the intervals is given by inclusion), so in practice this minimum is achieved for $I_{u}$ and $I_{v}$ sufficiently small intervals around $u$ and $v$ respectively.

Remark 5 (Cornerpoints at infinity).

We identify the vertical line $\varrho$ of equation $u=k$ with the pair $(k,+\infty)$ . Definition 5 allows one to define the multiplicity $\mu(\varrho)$ as the minimum of

p_{F}(\sup(I_{k}),v)-p_{F}(\inf(I_{k}),v).

Whenever $\mu(\varrho)>0$ , we say that $\varrho$ is a cornerpoint at infinity.

Definition 6.

The persistence diagram $\mathcal{D}F$ associated with the persistence function $p_{F}$ is the multiset of its cornerpoints, along with all the diagonal points $\{(u,u)|u\in\mathbb{R}_{\geq 0}\}$ with infinite (countable) multiplicity.

It is easy to show that if $F$ is tame the persistence diagram has only a finite number of off-diagonal points. The following property is relevant when measuring distances between diagrams and will be key in the remainder of this section.

Proposition 10.

If $\alpha<\beta\leq\gamma<\delta\in\mathbf{R}\cup\{+\infty\}$ are right-regular points, then sum of the multiplicities of the cornerpoints $(u,v)$ s. t. $\alpha<u\leq\beta$ and $\gamma<v\leq\delta$ is

p_{F}(\beta,\gamma)-p_{F}(\alpha,\gamma)-p_{F}(\beta,\delta)+p_{F}(\alpha,\delta)

Proof.

By induction on the number of cornerpoints in the box. ∎

3.3 Indecomposable persistence modules

Given a tame (with respect to a strict rank) ${(\mathbb{R},\leq)}$ -indexed diagram $F\in\textnormal{Obj}(\mathbf{D}^{(\mathbb{R},\leq)})$ , we can partition $\mathbb{R}$ into a finite number of non-empty intervals $C_{1},\dots,C_{n}\subseteq\mathbb{R}$ such that $F(x\leq y)$ is an isomorphism whenever $x,y$ lie in the same interval. The full subcategory of such ${(\mathbb{R},\leq)}$ -indexed diagrams is equivalent to the category of representations of the poset $(\{1,\dots,n\},\leq)$ . Given a sequence of points $c_{i}\in C_{i}$ , the equivalence of the two representation categories is induced by the pair of order-preserving maps:

\displaystyle\begin{aligned} &\iota:(\{1,\dots,n\},\leq)\to{(\mathbb{R},\leq)}\\ &i\mapsto c_{i}\end{aligned}

and

\displaystyle\begin{aligned} &\pi:{(\mathbb{R},\leq)}\to(\{1,\dots,n\},\leq)\\ &x\mapsto i\mbox{ such that }x\in C_{i}\end{aligned}

If $\mathbf{D}$ is an Abelian category of finite length, then so is $\mathbf{D}^{(\{1,\dots,n\},\leq)}$ . Indeed, we can bound the length of any $F\in\mathbf{D}^{(\{1,\dots,n\},\leq)}$ as follows:

length(F)\leq\sum_{i=1}^{n}length(F(i))

By Krull-Schmidt theorem [1], $F$ can then be decomposed as direct sum of indecomposable objects

F=\bigoplus_{k\in K}I_{k}

Indecomposable objects in $\mathbf{D}^{(\{1,\dots,n\},\leq)}$ have been characterized in the case $\mathbf{D}=\mathbf{FinVec}_{\mathbb{K}}$ . Indeed, let $A_{n}$ be the quiver having as nodes the points $\{1,\dots,n\}$ and non-trivial edges $i\to i+1$ for $i\in\{1,\dots,n-1\}$ . Then, $A_{n}$ has trivially the same representations of $(\{1,\dots,n\},\leq)$ and is one of the ADE Dynkin diagrams for which Gabriel’s theorem [18] can characterize all indecomposable representations. See [19] for a treatment of persistence homology that takes Gabriel’s theorem and Krull-Schmidt theorem as starting points. We can not, unfortunately, use Gabriel’s theorem as we wish to work with a more general $\mathbf{D}$ , but we will provide an equivalent classification for the quiver $A_{n}$ and $\mathbf{D}$ semisimple (definition A.3.7). To do so, we will need to generalize [5, Def. 4.1].

Definition 7.

[5, Def. 4.1] Given a semisimple Abelian category $\mathbf{D}$ , a simple object $S\in\textnormal{Obj}(\mathbf{D})$ and an interval $I\subseteq\mathbb{R}$ we define the diagram $\chi_{I,S}\in\mathbf{D}^{(\mathbb{R},\leq)}$ as:

\displaystyle\chi_{I,S}(a)=\begin{cases}{}S&\text{if }a\in I\\ 0&\text{otherwise}\end{cases}

and

\displaystyle\chi_{I,S}(a\leq b)=\begin{cases}{}\textnormal{Id}_{S}&\text{if }a,b\in I\\ 0&\text{otherwise}\end{cases}

When working in $\mathbf{D}^{(\{1,\dots,n\},\leq)}$ we abuse of the same notation and write:

\chi_{[b,d],S}=\underbrace{0\to\dots\to 0}_{[1,b-1]}\to\underbrace{S\xrightarrow{Id}\dots\xrightarrow{Id}S}_{[b,d]}\to\underbrace{0\to\dots\to 0}_{[d+1,n]}

We say that a $F$ has finite type if $F=\bigoplus_{k\in K}\chi_{I_{k},S_{k}}$

Proposition 11.

If $\mathbf{D}$ is semisimple, all indecomposable objects in $\mathbf{D}^{(\{1,\dots,n\},\leq)}$ are isomorphic to an “interval object” of the form $\chi_{[b,d],S}$ where $S$ is a simple object.

Proof.

We proceed by contradiction. Let us take the smallest $n\in\mathbb{N}$ for which this does not hold and an indecomposable $F\in\mathbf{D}^{(\{1,\dots,n\},\leq)}$ not isomorphic to any $\chi_{[b,d],S}$ . $F(1)\not\simeq 0$ and $F(n)\not\equiv 0$ as otherwise we could find a counter-example for $\mathbf{D}^{(\{1,\dots,n-1\},\leq)}$ . Similarly $\phi=F(n-1\leq n)$ cannot be an isomorphism, as otherwise we would have a counter-example in $\mathbf{D}^{(\{1,\dots,n-1\},\leq)}$ . $\phi$ must be epi, otherwise, we could write $F(n)=im(\phi)\oplus C$ with $C\not\simeq 0$ and $F$ would be the direct sum of:

\displaystyle i\mapsto\begin{cases}im(\phi)&\text{ if }i=n\\ F(i)&\text{ otherwise }\end{cases}

and

\displaystyle i\mapsto\begin{cases}C&\text{ if }i=n\\ 0&\text{ otherwise}\end{cases}

So, necessarily $\phi$ is not monic, as in an Abelian category morphisms that are both monic and epic are isomorphisms. We can decompose each $F(i)$ starting from $i=1$ and proceeding recursively, by setting $F(i)=ker(F(i\leq n))\oplus C_{i}$ , for every $i\in\{1,2,\dots,n-1\}$ , where we can take $C_{i}$ such that $F(i-1\leq i)(C_{i-1})\subseteq C_{i}$ . We can then decompose $F$ as a direct sum of:

\displaystyle i\mapsto\begin{cases}F(n)&\text{ if }i=n\\ C_{i}&\text{ otherwise}\end{cases}

and

\displaystyle i\mapsto\begin{cases}0&\text{ if }i=n\\ ker(F(i\leq n))&\text{ otherwise}\end{cases}

By assumption $F(n)\not\simeq 0$ and $ker(F(n-1\leq n))\not\simeq 0$ so this is a non-trivial decomposition which is absurd. ∎

Theorem 1.

In a semisimple Abelian category equipped with the rank function $length$ , a ${(\mathbb{R},\leq)}$ -indexed diagram $F$ is of finite type if and only if it is tame.

Proof.

If $F$ is of finite type, then all points that are not extrema of some of the intervals defining $F$ are regular, so there can only be finitely many critical values. Conversely, if $F$ is tame, then we can find some partition of the real line in nonempty intervals $C_{1},\dots,C_{n}\subseteq\mathbb{R}$ (which we assume to be sorted, i.e. $c_{i}<c_{j}$ whenever $c_{i}\in C_{i}$ , $c_{j},\in C_{j}$ and $i<j$ ) such that $F(x\leq y)$ is an isomorphism whenever $x,y$ lie in the same interval. We can then build $\tilde{F}\in\textnormal{Obj}(\mathbf{D})^{A_{n}}$ by $\tilde{F}(i)=F(c_{i})$ (where $c_{i}$ is some point in $C_{i}$ ). By proposition 11 $\tilde{F}\simeq\chi_{[b,d],S}$ for some $b,d\in\{1,\dots,n\}$ and some simple object $S$ , so $F\simeq\chi_{I,S}$ where $I=\cup_{i=b}^{d}C_{i}$ . ∎

3.4 Interleaving and bottleneck distances

There is a natural notion of distance between ${(\mathbb{R},\leq)}$ -indexed diagram, the interleaving distance. Here we recall the categorical notion of interleaving from [5], which in turn draws from [8]. Note that here we will only consider strong interleavings, thus not considering the weaker definition provided in [8].

As in [5] we define the translation functor $T_{b}:{(\mathbb{R},\leq)}\to{(\mathbb{R},\leq)}$ as $T_{b}(a)=a+b$ and the natural transformation $\eta_{b}:Id_{(\mathbb{R},\leq)}\to T_{b}$ given by $\eta_{b}:a\leq a+b$ .

Given a ${(\mathbb{R},\leq)}$ -indexed diagram $F$ , $FT_{\epsilon}$ is simply defined by $x\mapsto F(x+\epsilon)$ . We will often compose functors to the left of natural transformation (thus applying the functor to the morphism the natural transformation returns) or to the right (thus calling the natural transformation on the object returned by the functor). For example, starting from $\eta_{b}:Id\to T_{b}$ , we can compose $F$ to the left and obtain a new natural transformation $F\eta_{b}:F\to FT_{b}$ . Then, similarly, we can compose $T_{c}$ to the right and obtain $F\eta_{b}T_{c}:FT_{c}\to FT_{b+c}$ .

Definition 8.

[5, Def. 3.4] We remind that given two ${(\mathbb{R},\leq)}$ -indexed diagrams $F,G$ , they are $\epsilon$ -interleaved if there are natural transformations $\phi^{F}:F\to GT_{\epsilon}$ and $\phi^{G}:G\to FT_{\epsilon}$ such that:

\displaystyle(\phi^{G}T_{\epsilon})\phi^{F}=F\eta_{2\epsilon}

and

\displaystyle(\phi^{F}T_{\epsilon})\phi^{G}=G\eta_{2\epsilon}

The interleaving distance $d(F,G)$ is the infimum of all $\epsilon$ values such that $F$ and $G$ are $\epsilon$ -interleaved.

There is a simple example coming from filtering functions. Given a topological spaces $X$ and two real-valued functions $f,g:X\to\mathbb{R}$ , if $f$ and $g$ differ no more than $\epsilon$ , i.e., for all $x\in X$ , $|f(x)-g(x)|\leq\epsilon$ , then there is a natural $\epsilon$ -interleaving between the two ${(\mathbb{R},\leq)}$ -indexed diagrams corresponding to the sublevels of $f$ and $g$ respectively.

It is natural to define persistence starting from one or sometimes more functors (see section 4.3 for an example with two functors):

\mathbf{C}_{0}\xrightarrow{\Psi_{1}}\mathbf{C}_{1}\xrightarrow{\Psi_{2}}\dots\xrightarrow{\Psi_{n}}\mathbf{C}_{n}

where $\mathbf{C}_{0},\dots,\mathbf{C}_{n-1}$ are arbitrary categories, whereas $(\mathbf{C}_{n},r)$ is a ranked category. A ${(\mathbb{R},\leq)}$ -indexed diagram $F\in\mathbf{C}_{0}^{(\mathbb{R},\leq)}$ is mapped by the various functors $\Psi_{i}$ in ${(\mathbb{R},\leq)}$ -indexed diagrams

\Psi_{1}(F)\in\mathbf{C}_{1}^{(\mathbb{R},\leq)},\dots,\Psi_{n}(F)\in\mathbf{C}_{n}^{(\mathbb{R},\leq)}

Similarly an $\epsilon$ -interleaving between $F,G\in\mathbf{C}_{0}^{(\mathbb{R},\leq)}$ is mapped to $\epsilon$ -interleavings between $\Psi_{1}(F),\Psi_{1}(G)$ , $\Psi_{2}(F),\Psi_{2}(G)$ , et cetera. As a consequence we can define a sequence of interleaving distances $d_{0}\geq d_{1}\geq\dots\geq d_{n}$ as follows:

d_{i}(F,G)=d_{\mathbf{C}_{i}}(\Psi_{i}(F),\Psi_{i}(G))

where $d_{\mathbf{C}_{i}}$ is the interleaving distance in category $\mathbf{C}_{i}$ .

Furthermore, the bottleneck distance neglects the underlying category and is defined only via the persistence diagram.

Definition 9.

Let $F,G$ be two tame ${(\mathbb{R},\leq)}$ -indexed diagrams in $\mathbf{R}$ and ${\cal D}F,{\cal D}G$ their persistence diagrams. The bottleneck distance between the persistence diagrams is defined as

d({\cal D}F,{\cal D}G)=\inf_{\beta\in{\cal B}}\sup_{p\in{\cal D}(F)}\|p-\beta(p)\|_{\infty},

where ${\cal B}$ is the collection of all bijections between ${\cal D}F$ and ${\cal D}G$ .

We now prove that under mild hypotheses ( $\mathbf{C}_{n}$ admits finite colimits) the chain of decreasing distances can be continued to include the bottleneck distance

d_{0}(F,G)\geq d_{1}(F,G)\geq\dots\geq d_{n}(F,G)\geq d({\cal D}F,{\cal D}G)

and find examples of ranked categories that achieve the equality $d_{n}(F,G)=d({\cal D}F,{\cal D}G)$ . In particular, this chain of inequalities grants stability in the classical sense: as noted in remark 3, given two filtering functions that differ less than $\epsilon$ , the associated ${(\mathbb{R},\leq)}$ -indexed diagrams are $\epsilon$ -interleaved.

To prove inequalities between interleaving and bottleneck distance, we will generalize [8, Lm. 4.5] to the case of persistence function on an arbitrary category and [8, Lm. 4.6, 4.7] from the category of vector spaces to an arbitrary category with finite colimits.

Lemma 3 (Box lemma).

Let $F,G$ be two tame ${(\mathbb{R},\leq)}$ -indexed diagrams that are $\epsilon$ -interleaved. Given $\alpha<\beta<\gamma<\delta$ let $\square$ denote the region $(\alpha,\beta]\times(\gamma,\delta]$ and $\square_{\epsilon}$ the region $(\alpha-\epsilon,\beta+\epsilon]\times(\gamma-\epsilon,\delta+\epsilon]$ . Then the sum of the multiplicities of the points of ${\cal D}F$ contained in $\square$ is smaller or equal to the sum of the multiplicities of the points of ${\cal D}G$ contained in $\square_{\epsilon}$ .

Proof.

As in [8, Lm. 4.5] we notice that, if $\beta+\epsilon>\gamma-\epsilon$ , then $\square_{\epsilon}$ intersects the diagonal and so the total multiplicity of ${\cal D}G$ intersected with the diagonal is $\infty$ , so we can assume $\beta+\epsilon\leq\gamma-\epsilon$ .

As $F$ and $G$ are $\epsilon$ -interleaved, we have the commutative diagram:

from which we can consider the sequence of morphisms

G(\alpha-\epsilon)\to F(\alpha)\to F(\beta)\to G(\beta+\epsilon)\to G(\gamma-\epsilon)\to F(\gamma)\to F(\delta)\to G(\delta+\epsilon)

Let us first assume that $\alpha,\beta,\gamma,\delta$ are all right-regular values for $F$ and $\alpha-\epsilon,\beta+\epsilon,\gamma-\epsilon,\delta+\epsilon$ are all right-regular values for $G$ . Then by proposition 10, we can compute the sum of the multiplicities of the points of ${\cal D}F$ and ${\cal D}G$ using the categorical persistence function $p$ at the corners of the respective regions. Therefore we simply need to prove:

		$\displaystyle p(G(\beta+\epsilon\leq\gamma-\epsilon))-p(G(\alpha-\epsilon\leq\gamma-\epsilon))-p(G(\beta+\epsilon\leq\delta+\epsilon))+p(G(\alpha-\epsilon\leq\delta+\epsilon))\geq$
		$\displaystyle p(F(\beta\leq\gamma))-p(F(\alpha\leq\gamma))-p(F(\beta\leq\delta))+p(F(\alpha\leq\delta))$

The inequality can be proven by repeatedly applying lemma 2. A smaller diagram, not including $F(\delta)$ and $G(\delta+\epsilon)$ , can be used to prove the case $\delta=+\infty$ .

If some of $\alpha,\beta,\gamma,\delta$ is not right-regular for $F$ or some of $\alpha-\epsilon,\beta+\epsilon,\gamma-\epsilon,\delta+\epsilon$ is not right-regular for $G$ , we can simply prove the inequality for $\alpha^{\prime},\beta^{\prime},\gamma^{\prime},\delta^{\prime}=\alpha+h,\beta+h,\gamma+h,\delta+h$ , where $h$ is such that $\alpha^{\prime},\beta^{\prime},\gamma^{\prime},\delta^{\prime}$ are right-regular points for $F$ and $\alpha^{\prime}-\epsilon,\beta^{\prime}+\epsilon,\gamma^{\prime}-\epsilon,\delta^{\prime}+\epsilon$ are right-regular for $G$ . Taking the limit for $h\to 0^{+}$ ends the proof. ∎

Lemma 4 (Interpolation lemma).

Let $\mathbf{C}$ be a category with finite colimits. If $F,G\in\mathbf{C}^{(\mathbb{R},\leq)}$ are $\epsilon$ -interleaved, there exists an interpolation $\tilde{H}_{s}$ for all $s\in[0,\epsilon]$ such that: $F$ and $\tilde{H}_{s}$ are $s$ -interleaved, $G$ and $\tilde{H}_{s}$ are $(\epsilon-s)$ -interleaved, $\tilde{H}_{s}$ and $\tilde{H}_{s^{\prime}}$ are $|s-s^{\prime}|$ -interleaved.

Proof.

The proof follows the construction of [8], but in the more general setting of categories with finite colimits. We start by defining ${\epsilon}_{1}=s$ and ${\epsilon}_{2}={\epsilon}-s$ . Then $H_{s}=FT_{-{\epsilon}_{1}}\amalg GT_{-{\epsilon}_{2}}$ . We have a natural transformation

F\xrightarrow{\iota^{F}}H_{s}T_{{\epsilon}_{1}}=F\amalg GT_{{\epsilon}_{1}-{\epsilon}_{2}}

given by the coproduct inclusion as well as a natural transformation

H_{s}=FT_{-{\epsilon}_{1}}\amalg GT_{-{\epsilon}_{2}}\xrightarrow{\pi^{F}}FT_{{\epsilon}_{1}}

which is defined as $F\eta_{2{\epsilon}_{1}}T_{-{\epsilon}_{1}}$ on the first term of the coproduct and as $\phi^{G}T_{-{\epsilon}_{2}}$ on the second term of the coproduct.

For this to be an interleaving, we need to prove that $(\pi^{F}T_{{\epsilon}_{1}})\iota^{F}=F\eta_{2{\epsilon}_{1}}$ (going from $F$ to $H_{s}T_{{\epsilon}_{1}}$ and then to $FT_{2e\_1}$ versus going from $F$ to $FT_{2{\epsilon}_{1}}$ directly) and that $\iota^{F}T_{{\epsilon}_{1}}\pi^{F}=H_{s}\eta_{2{\epsilon}_{1}}$ (going from $H_{s}$ to $FT_{{\epsilon}_{1}}$ and then to $H_{s}T_{2{\epsilon}_{1}}$ versus going from $H_{s}$ to $H_{s}T_{2{\epsilon}_{1}}$ directly).

We have $(\pi^{F}T_{{\epsilon}_{1}})\iota^{F}=F\eta_{2{\epsilon}_{1}}$ as the left hand side is the composition:

F\to F\amalg GT_{{\epsilon}_{1}-{\epsilon}_{2}}\to FT_{2{\epsilon}_{1}}

where the first morphism is the coproduct inclusion and the second morphism is $F\eta_{2{\epsilon}_{1}}$ on the first component of the coproduct.

As remarked by [8, Appendix A], however, $l^{F}=\iota^{F}T_{{\epsilon}_{1}}\pi^{F}$ and $d^{F}=H_{s}\eta_{2{\epsilon}_{1}}$ are not equal in general. Similarly, the $d^{G}$ and $l^{G}$ morphisms defined symmetrically are also not equal in general. $\tilde{H}_{s}$ is defined by coequalizing both $d^{F}T_{-2{\epsilon}_{1}}$ with $l^{F}T_{-2{\epsilon}_{1}}$ and $d^{G}T_{-2{\epsilon}_{2}}$ with $l^{G}T_{-2{\epsilon}_{2}}$ . This would of course satisfy all the desired interleaving properties between $F$ , $G$ and $H_{s}$ but we need to show that the existing natural transformations $H_{s}\to FT_{{\epsilon}_{1}}$ and $H_{s}\to GT_{{\epsilon}_{2}}$ pass to the coequalizer (i.e. induce natural transformations $\tilde{H}_{s}\to FT_{{\epsilon}_{1}}$ and $\tilde{H}_{s}\to GT_{{\epsilon}_{2}}$ ). As everything is symmetric, we only need to prove it for the map $H_{s}\to FT_{{\epsilon}_{1}}$ .

We start by proving that the transformation $H_{s}\to FT_{{\epsilon}_{1}}$ passes to the coequalizer of $d^{F}T_{-2{\epsilon}_{1}}$ and $l^{F}T_{-2{\epsilon}_{1}}$ . We observe that

H_{s}T_{-2{\epsilon}_{1}}\to FT_{-{\epsilon}_{1}}\to H_{s}\to FT_{{\epsilon}_{1}}

is the same as the more direct map

H_{s}T_{-2{\epsilon}_{1}}\to H_{s}\to FT_{{\epsilon}_{1}}

as both the blue parallelogram and the green rightmost triangle are commutative in the following diagram:

therefore

	$\displaystyle H_{s}T_{-2{\epsilon}_{1}}\to FT_{-{\epsilon}_{1}}\to H_{s}\to FT_{{\epsilon}_{1}}$	$\displaystyle=H_{s}T_{-2{\epsilon}_{1}}\to FT_{-{\epsilon}_{1}}\to FT_{{\epsilon}_{1}}$
		$\displaystyle=H_{s}T_{-2{\epsilon}_{1}}\to H_{s}\to FT_{{\epsilon}_{1}}$

Proving that the transformation $H_{s}\to FT_{{\epsilon}_{1}}$ passes to the coequalizer of $d^{G}T_{-2{\epsilon}_{2}}$ and $l^{G}T_{-2{\epsilon}_{2}}$ is slightly trickier. We need to prove that:

H_{s}T_{-2{\epsilon}_{2}}\to GT_{-{\epsilon}_{2}}\to H_{s}\to FT_{{\epsilon}_{1}}=H_{s}T_{-2{\epsilon}_{2}}\to H_{s}\to FT_{{\epsilon}_{1}}

As $H_{s}T_{-2{\epsilon}_{2}}=FT_{-{\epsilon}_{1}-2{\epsilon}_{2}}\amalg GT_{-3{\epsilon}_{2}}$ we can prove the above equality on the two components separately. We consider the diagram:

As the blue bottom parallelogram and the green bottom-left triangle are commutative, we have:

	$\displaystyle GT_{-3{\epsilon}_{2}}\to H_{s}T_{-2{\epsilon}_{2}}\to GT_{-{\epsilon}_{2}}\to H_{s}\to FT_{{\epsilon}_{1}}$	$\displaystyle=GT_{-3{\epsilon}_{2}}\to GT_{-{\epsilon}_{2}}\to H_{s}\to FT_{{\epsilon}_{1}}$
		$\displaystyle=GT_{-3{\epsilon}_{2}}\to H_{s}T_{-2{\epsilon}_{2}}\to H_{s}\to FT_{{\epsilon}_{1}}$

As a consequence of the interleaving between $F$ and $G$ , the large inverted teal triangle is also commutative and so is the top red trapezoid. Consequently, we have:

	$\displaystyle FT_{-{\epsilon}_{1}-2{\epsilon}_{2}}\to H_{s}T_{-2{\epsilon}_{2}}\to GT_{-{\epsilon}_{2}}\to H_{s}\to FT_{{\epsilon}_{1}}$	$\displaystyle=FT_{-{\epsilon}_{1}-2{\epsilon}_{2}}\to GT_{-{\epsilon}_{2}}\to FT_{{\epsilon}_{1}}$
		$\displaystyle=FT_{-{\epsilon}_{1}-2{\epsilon}_{2}}\to FT_{{\epsilon}_{1}}$
		$\displaystyle=FT_{-{\epsilon}_{1}-2{\epsilon}_{2}}\to H_{s}T_{-2{\epsilon}_{2}}\to H_{s}\to FT_{{\epsilon}_{1}}$

so, necessarily

H_{s}T_{-2{\epsilon}_{2}}\to GT_{-{\epsilon}_{2}}\to H_{s}\to FT_{{\epsilon}_{1}}=H_{s}T_{-2{\epsilon}_{2}}\to H_{s}\to FT_{{\epsilon}_{1}}

Proving that morphisms of the type $H_{s}\to H_{s^{\prime}}T_{|s-s^{\prime}|}$ also pass to the coequalizer is a similar exercise in diagram chasing. ∎

The following result is a generalization, in our setting, of [8, Thm. 4.4]. Given lemmas 3 and 4, which are the equivalent of [8, Lm. 4.5, 4.6, 4.7], the proof of the following result is identical to the proof of [8, Thm. 4.4]: we reproduce it here with slight changes to adjust for differences in notation.

Theorem 2.

Let $\mathbf{R}$ be a category with finite colimits and $p$ be a categorical persistence function. If $F1,F2$ are two tame ${(\mathbb{R},\leq)}$ -indexed diagrams in $\mathbf{R}$ , then

d_{\mathbf{R}}(F1,F2)\geq d({\cal D}F1,{\cal D}F2).

Proof.

The proof is analogous to [8, Thm. 4.4]. Let us assume that $F,G$ are $\epsilon$ -interleaved. We can construct $\tilde{H}_{s}$ as in lemma 4. We define:

\delta(s)=\frac{1}{2}\min\left\{||p-q||_{\infty},\;p\in{\cal D}\tilde{H}_{s}\setminus\Delta,\;q\in{\cal D}\tilde{H}_{s}\setminus\{p\}\right\}

We say that $\tilde{H}_{s^{\prime}}$ is very close to $\tilde{H}_{s}$ if $|s-s^{\prime}|<\delta(s)$ . In such case, by lemma 3, as $\tilde{H}_{s}$ and $\tilde{H}_{s^{\prime}}$ are $|s-s^{\prime}|$ interleaved, any off-diagonal point of ${\cal D}\tilde{H}_{s}$ admits exactly one point of ${\cal D}\tilde{H}_{s^{\prime}}$ within $l^{\infty}$ distance $|s-s^{\prime}|$ . By compactness, we can find a sequence $0=s_{0}<s_{1}<\dots<s_{n}<s_{n+1}=\epsilon$ such that for $i=0,\dots,n$ either $\tilde{H}_{s_{i}}$ is very close to $\tilde{H}_{s_{i+1}}$ or vice versa. From the Easy Bijection Lemma [9], it follows that $d({\cal D}\tilde{H}_{s_{i}},{\cal D}\tilde{H}_{s_{i+1}})\leq s_{i+1}-s_{i}$ . By applying repeatedly the triangle inequality we obtain that $d({\cal D}F,{\cal D}G)\leq\epsilon$ . ∎

Even though the interleaving distance is, under mild assumptions, larger than the bottleneck distance, the opposite is not true with such generality. In the rest of this section we will show a class of categories and rank functions for which the converse holds.

Definition 10.

A ranked category $(\mathbf{R},r)$ is tight if, for any tame ${(\mathbb{R},\leq)}$ -indexed diagrams $F$ and $G$ , the following equality holds:

d_{\mathbf{R}}(F,G)=d({\cal D}F,{\cal D}G)

Theorem 3.

Let $\mathbf{D}$ be a semisimple Abelian category with only one simple object up to isomorphism, equipped with the rank $length$ . Then the interleaving and bottleneck distances coincide on tame ${(\mathbb{R},\leq)}$ -indexed diagrams, that is to say $(\mathbf{D},length)$ is tight.

Proof.

Given $F,G$ two ${(\mathbb{R},\leq)}$ -indexed diagrams, we know already $d_{\mathbf{D}}(F,G)\leq d({\cal D}F,{\cal D}G)$ because of theorem 2. To prove the inequality, let us call $S$ the only (up to isomorphism) simple object in $\mathbf{D}$ . As $F$ and $G$ are tame, by theorem 1, they are also of finite type and we can therefore write:

\displaystyle F\simeq\bigoplus_{k\in{\cal D}F}\chi_{I_{k},S}

and

\displaystyle G\simeq\bigoplus_{k\in{\cal D}G}\chi_{I_{k},S}

where $S$ is a representative of the unique isomorphism class of simple objects in $\mathbf{D}$ . We take $I_{k}$ to be the empty interval if $k$ lies on the diagonal of the persistence diagram.

Given $\epsilon>d({\cal D}F,{\cal D}G)$ , let us take a bijection of persistence diagrams $\psi:{\cal D}F\to{\cal D}G$ which sends each point to a point of distance $<\epsilon$ . The interleaving map $\phi^{F}:F\to GT_{\epsilon}$ will send $\chi_{I_{k},S}$ into $\chi_{I_{\psi(k),S}}T_{\epsilon}$ . ∎

theorem 3 is more general than the usual result (which considers $\mathbf{D}=\mathbf{FinVec}_{\mathbb{K}}$ ), as it includes modules over non-commutative division rings, which are a semisimple category with essentially one simple object. This will be important in the follow up to make general theorems about multicolored persistence in semisimple categories.

Having, up to isomorphism, only one simple object is a necessary assumption. As a counter-example, given a semisimple Abelian category $\mathbf{D}$ with at least two non-isomorphic simple objects $O_{1}$ and $O_{2}$ , $(\mathbf{D},length)$ as in proposition 6 is not tight. If we take two constant ${(\mathbb{R},\leq)}$ -indexed diagrams: $u\mapsto O_{1}$ and $u\mapsto O_{2}$ , their interleaving distance is $\infty$ and their bottleneck distance is $0$ . To recover the equality, we will use the concept of coloring.

4 Multicolored persistence

The aim of this section is to find a suitable way to still use persistence diagrams to compute the interleaving distance (or find tighter bounds for it) even in categories with many non-isomorphic indecomposable objects. We will do so by defining multicolored persistence diagrams, where each color encodes the isomorphism class of an indecomposable persistence module.

We start by introducing the concept of coloring of ranked categories.

Definition 11.

Given an index set $\Gamma$ , we say that a ranked category $(\mathbf{R},r)$ is $\Gamma$ -colorable if there exist ranked categories $(\mathbf{Q}_{\gamma},r_{\gamma})$ for $\gamma\in\Gamma$ and image-preserving functors ${\cal C}_{\gamma}:\mathbf{R}\to\mathbf{Q}_{\gamma}$ such that

1.

the induced functor ${\cal C}:\mathbf{R}\to\prod_{\gamma\in\Gamma}\mathbf{Q}_{\gamma}$ is fully faithful;
2.

for each $X\in{\textnormal{Obj}}(\mathbf{R})$ , $r_{\gamma}(X)$ is $0$ for all but finitely many $\gamma\in\Gamma$ and:

$r(X)=\sum_{\gamma\in\Gamma}r_{\gamma}({\cal C}_{\gamma}(X))$ (2)

We call such ${\cal C}$ a $\Gamma$ -coloring and we say that $(\mathbf{R},r)$ is ${\cal C}$ -colored.

The fully faithful condition may sound quite abstract, in practice what we are asking is that given $X,Y\in\textnormal{Obj}(\mathbf{R})$ the natural map of sets:

\textnormal{Hom}(X,Y)\to\prod_{\gamma\in\Gamma}\textnormal{Hom}({\cal C}_{\gamma}(X),{\cal C}_{\gamma}(Y))

is bijective.

Note that in an Abelian category $\mathbf{C}$ of finite length, equipped with the rank function $length$ , we have a coloring given by the block decomposition into indecomposable categories $\mathbf{C}_{\gamma}$ (see [14, Sect. 1]). Consequently eq. 2 follows from the additivity of $length$ .

4.1 Multicolored persistence diagrams

In what follows, we will show how, given $(\mathbf{R},r)$ a $\mathcal{C}$ -colored ranked category, it is possible to construct a multicolored persistence diagram. First we will need a simple lemma:

Lemma 5.

Let $(\mathbf{R},r)$ be a $\mathcal{C}$ -colored ranked category. Given $F\in\mathbf{R}^{(\mathbb{R},\leq)}$ , if $F$ is constant on an interval $I$ with respect to $r$ , then $F$ is also constant on $I$ with respect to all colored components $r_{\gamma}$ . As a consequence, if $F$ is tame with respect to $r$ , then $F$ is tame with respect to $r_{\gamma}$ , for all $\gamma\in\Gamma$ .

Proof.

Let $I\subseteq{\mathbb{R}}$ be an interval. Given $u\leq v\in I$ we know that $r(F(u))=r(im(F(u\leq v)))$ , i.e.:

\sum_{\gamma\in\Gamma}r_{\gamma}(F(u))=\sum_{\gamma\in\Gamma}r_{\gamma}(im(F(u\leq v)))

Of course, for any $\gamma$ , we have $r_{\gamma}(F(u))\geq r_{\gamma}(im(F(u\leq v)))$ . If for some $\overline{\gamma}$ we had a strict inequality $r_{\overline{\gamma}}(F(u))>r_{\overline{\gamma}}(im(F(u\leq v)))$ , then we would have a strict inequality:

\sum_{\gamma\in\Gamma}r_{\gamma}(F(u))>\sum_{\gamma\in\Gamma}r_{\gamma}(im(F(u\leq v)))

which is absurd. $r_{\gamma}(im(F(u\leq v)))=r_{\gamma}(F(v))$ is proved in the same way. ∎

As a consequence, given a $\cal C$ -colored ranked category $(\mathbf{R},r)$ and a ${(\mathbb{R},\leq)}$ -indexed diagram $F$ , we can draw its multicolored persistence diagram by superimposing the persistence diagrams associated to each colored component, see fig. 3. Let $(\mathbf{R},r)$ be a $\cal C$ -colored ranked category. The multicolored bottleneck distance between two multicolored persistence diagrams is computed just like the normal bottleneck distance, but only accepting bijections that preserve the color of cornerpoints. We denote it by $d_{\cal C}$ .

Definition 12.

Let $\cal C$ be a coloring on a ranked category $(\mathbf{R},r)$ . We say that $\cal C$ is tight if for any tame ${(\mathbb{R},\leq)}$ -indexed diagrams $F,G$ the following equality holds:

d_{\mathbf{R}}(F,G)=d_{\cal C}({\cal D}F,{\cal D}G)

The multicolored bottleneck distance is greater or equal than the normal bottleneck distance, as the minimum is calculated across a smaller set of possible bijections. First, it is natural to ask whether the multicolored bottleneck distance is still bounded by the interleaving distance.

Figure 1:

H_{1}

and multicolored simplicial complexes. Coloring the vertices of a simplicial complex allows one to create a compact poset representation of all possible interaction between colored components evaluated through a rank function. Here, we consider a two-class coloring, namely orange

o

and blue

b

. In each panel, the leftmost object is a multicolored simplicial complex, in the center the poset obtained by considering colors and their interactions:

(\left\{\{b\},\{o\},\{b,o\}\right\},\subseteq)

. Finally, the diagram obtained by computing the first homology group for each element of

\left\{\{b\},\{o\},\{b,o\}\right\}

. Observe how the cycle generated by the orange component propagates to

\{b,o\}

in Panel (a), whilst it disappears from

\{b,o\}

in Panel (b), because of the central blue vertex.

Theorem 4.

Let ${\cal C}:\mathbf{R}\to\prod_{\gamma\in\Gamma}\mathbf{Q}_{\gamma}$ be a $\Gamma$ -coloring of a ranked category $(\mathbf{R},r)$ with components $(\mathbf{Q}_{\gamma},r_{\gamma})$ . If, for all $\gamma\in\Gamma$ , the category $\mathbf{Q}_{\gamma}$ admits finite colimits, then the multicolored bottleneck distance is bounded by the interleaving distance, i.e.

d_{\mathbf{R}}(F,G)\geq d_{\cal C}({\cal D}F,{\cal D}G)

Furthermore, if all $(\mathbf{Q}_{\gamma},r_{\gamma})$ are tight, then ${\cal C}$ is a tight coloring in the sense of definition 12.

Proof.

The functor ${\cal C}$ is fully faithful by definition 11, hence $F$ and $G$ are ${\epsilon}$ -interleaved in $\mathbf{R}$ if and only if ${\cal C}_{\gamma}F$ and ${\cal C}_{\gamma}G$ are $\epsilon$ -interleaved in $\mathbf{Q}_{\gamma}$ for all $\gamma$ . Therefore:

d_{\mathbf{R}}(F,G)=\sup_{\gamma\in\Gamma}\;d_{\mathbf{Q}_{\gamma}}({\cal C}_{\gamma}F,{\cal C}_{\gamma}G)

Similarly:

d_{\cal C}({\cal D}F,{\cal D}G)=\sup_{\gamma\in\Gamma}\;d({\cal D(C}_{\gamma}F),{\cal D(C}_{\gamma}G))

As all $\mathbf{Q}_{\gamma}$ have finite colimits, thanks to theorem 2, we have element-wise inequalities

d_{\mathbf{Q}_{\gamma}}({\cal C}_{\gamma}F,{\cal C}_{\gamma}G)\geq d({\cal D(C}_{\gamma}F),{\cal D(C}_{\gamma}G))

so, necessarily

d_{\mathbf{R}}(F,G)\geq d_{\cal C}({\cal D}F,{\cal D}G)

Similarly, if all $(\mathbf{Q}_{\gamma},r_{\gamma})$ are tight, we have element-wise equalities:

d_{\mathbf{Q}_{\gamma}}({\cal C}_{\gamma}F,{\cal C}_{\gamma}G)=d({\cal D(C}_{\gamma}F),{\cal D(C}_{\gamma}G))

and thus

d_{\mathbf{R}}(F,G)=d_{\cal C}({\cal D}F,{\cal D}G)

∎

Given an Abelian semisimple category $\mathbf{C}$ , let $\Gamma$ be a maximal set of non-isomorphic simple objects of $\mathbf{C}$ and, for each $\gamma\in\Gamma$ , $\mathbf{C}_{\gamma}$ the full subcategory spanned by objects isomorphic to $\bigoplus_{i=1}^{n}\gamma$ for $n\in\mathbb{N}$ . As in the case of finite group representations [21], objects in $\mathbf{C}$ can be canonically decomposed as a direct sum of components in the various $\mathbf{C}_{\gamma}$ . This decomposition induces a natural tight coloring ${\cal C}:\mathbf{C}\to\prod_{\gamma\in\Gamma}\mathbf{C}_{\gamma}$ on $(\mathbf{C},length)$ .

Theorem 5.

Given $\mathbf{C}$ an Abelian semisimple category, ${\cal C}$ is a tight coloring on $(\mathbf{C},length)$ .

Proof.

By theorem 4 we only need to prove that, for all $\gamma\in\Gamma$ , the ranked category $(\mathbf{C}_{\gamma},length)$ is tight. However the category $\mathbf{C}_{\gamma}$ is semisimple and has only one simple object $\gamma$ up to isomorphism so, by theorem 3 it is tight. ∎

We have two examples in mind: groups and posets.

4.2 Persistent homology on simplicial complexes with a group action

Figure 2:

H_{1}

multicolored persistence in

\mathbf{Top}^{\mathbb{Z}_{2}}

. We consider the action of

\mathbb{Z}_{2}

on the space

X

represented in Panel (a) and generating the quotient highlighted in green. Note how the dashed loop lying on the

(y,z)

-plane is fixed by the action of group. We consider the filtration induced by the height function

h:X\rightarrow\mathbb{R}

. In Panel (b) cycles are labelled according to the group action. The same labeling is reported in the persistence diagram of Panel (c).

If $G$ is a finite group whose cardinality is not a multiple of the characteristic of $\mathbb{K}$ , then the category of $G$ -representations in $\mathbf{FinVec}_{\mathbb{K}}$ is semisimple. The homology functor induces a map $H_{n}:\mathbf{FinSimp}^{G}\to\mathbf{FinVec}_{\mathbb{K}}^{G}$ which allows us to define a categorical persistence function on finite simplicial complexes with a $G$ -action.

If a filtering function $f:X\to\mathbb{R}$ is $G$ -invariant, i.e. for all $x\in X,g\in G$ , $f(x)=f(gx)$ , then the sublevels of $f$ form a ${(\mathbb{R},\leq)}$ -indexed diagram in $\mathbf{FinVec}_{\mathbb{K}}^{G}$ . In practice it may well happen that the filtration and the group action are not compatible and the condition $f(x)=f(gx)$ is not always respected. In this case, one can consider an adjusted filtration such as:

\overline{f}(x):=\frac{1}{|G|}\sum_{g\in G}f(gx)

Application: Vietoris-Rips filtration under a group action

The above construction also applies on simiplicial complexes arising from point cloud data. Let $G$ be a finite group and $(X,d)$ a finite metric space with a distance-preserving $G$ -action. The Vietoris-Rips filtration [6] on $(X,d)$ is $G$ -invariant and therefore induces a ${(\mathbb{R},\leq)}$ -indexed diagram in $\mathbf{FinSimp}^{G}$ . Again, if the group action is not distance preserving, we can define an adjusted distance $\overline{d}(x,y):=\frac{1}{|G|}\sum_{g\in G}d(g\cdot x_{i},g\cdot x_{j})$ .

4.3 Persistent homology on labeled point clouds

Let $(P,\preceq)$ be a finite poset. We can consider the category $\mathbf{FinSimp}^{(P,\preceq)}$ , i.e. $(P,\preceq)$ -indexed diagrams of finite simplicial complexes. We have a chain of functors:

\mathbf{FinSimp}^{(P,\preceq)}\xrightarrow{H_{k}}\mathbf{FinVec}_{\mathbb{K}}^{(P,\preceq)}\xrightarrow{Q}\mathbf{FinVec}_{\mathbb{K}}^{|P|}

where we define $Q$ as follows:

p\mapsto coker\left(\textstyle\bigoplus_{i\precneqq p}F(i)\to F(p)\right)

That is to say $Q(F)$ maps $p$ to $F(p)$ quotiented by the images of $F(i)$ with $i$ strictly smaller than $p$ . As $\mathbf{FinVec}_{\mathbb{K}}^{|P|}$ is an Abelian semisimple category, the results of section 4.1 hold.

Figure 3: Multicolored persistence. We consider the colored weighted graph depicted in Panel (a), obtained by considering pairwise distances of points in a finite metric space, and the Vietoris-Rips filtration induced by the weight function defined on the edges. The multicolored persistence diagram in Panel (b) is obtained by considering the persistence of the cycles in the filtration along with their color, as depicted in Panel (c). Panels (d) and (e) are

{(\mathbb{R},\leq)}

-indexed diagrams in

\mathbf{FinVec}^{(P,\preceq)}

and

\mathbf{FinVec}^{|P|}

, respectively. Note how the indecomposable components of the diagram in Panel (e) are the ones described in Section 3.3.

Application: Vietoris-Rips filtration with labeled data

Let $(X,d,l)$ be a finite metric space with a labeling function $l:X\to\{l_{1},\dots,l_{n}\}$ from $X$ to a discrete set of labels. Let $X_{1},\dots,X_{n}$ be the subdatasets corresponding to the various labels, i.e. $X_{i}=l^{-1}(l_{i})$ . We wish to answer the following question: how do the homologies of the various $X_{i}$ interact with one another? Let $(P_{n},\subseteq)$ be the poset of non-empty subsets of $\{1,\dots,n\}$ ordered by inclusion. We have a functor $(P_{n},\subseteq)\to\mathbf{Met}$ sending $r\subseteq\{1,\dots,n\}$ to $\cup_{i\in r}X_{i}$ . By applying the Vietoris Rips construction we obtain a $(P_{n},\subseteq)$ -indexed diagram of finite simplicial complexes. This allows us to build a multicolored persistence diagram from a labeled dataset keeping into account whether a persistent cycle originates from a single subdataset or a union. See fig. 3.

5 Conclusion

Topological persistence and persistent homology allow for a deeper understanding of the high-dimensional organization of data [7, 20, 2]. Notably, persistence diagrams provide an encompassing view on the topological and geometrical properties of a given dataset, both as a whole and at sample level. The main limitation of these methods is their innate confinement to the category of topological spaces. In [4], we described a first generalization of persistence to concrete categories, extending the persistence paradigm to the analysis of objects such as weighted graphs and quivers, without need of auxiliary topological constructions. However, the classical persistence homology can not be deduced naturally from this generalization. Specifically, whereas the coherent sampling technique defines a persistence function from a set-valued functor (e.g. the connected components), higher homology functors are naturally vector space-valued.

The proposed framework further generalizes both the classical and the concrete category-based persistence. We captured the essential properties of the cardinality function in $\mathbf{FinSet}$ and the dimension function in $\mathbf{FinVec}$ upon which the theory of size and persistent Betti numbers is built. This led us to the definition of ranked category: a regular category equipped with an integer-valued rank function defined on its objects. We provide strategies to build such functions as fiber-wise rank functions. As special cases of fiber-wise ranks we recover both the cardinality of sets and dimension of vector spaces, as well as the length function in the general case of Abelian categories of finite length. Finally, we show how categorical persistence functions can be built from rank functions, generalizing the construction of coherent sampling introduced in [4].

We provide definitions and more general proofs of the main results in classical and concrete category-based persistence. We define cornerpoints, their multiplicity and thus introduce a general paradigm to build persistence diagrams. We describe the structure of persistence modules and characterize their irreducible components in the semisimple case. These results allow us to define and discuss the interleaving and bottleneck distances, proving the stability of persistence diagrams in our framework. As finite dimensional vector spaces are an Abelian, semisimple category with essentially one simple object, we determine which of these hypotheses are needed for the classical results to hold in the generalized framework.

Our definitions are, to a large extent, preserved by functors. In particular, given two regular categories and a regular functor between them, a rank function on the target category induces a rank function on the source category. The same, without the regularity assumption, holds for any categorical persistence function. ${(\mathbb{R},\leq)}$ -indexed diagrams, as well as $\epsilon$ -interleavings between them, are preserved by arbitrary functors. As a general strategy, we apply functors to move from ${(\mathbb{R},\leq)}$ -indexed diagrams in arbitrary categories to ${(\mathbb{R},\leq)}$ -indexed diagrams in categories where the interleaving distance and the bottleneck distance are equal. In particular, this allows one to define chains of inequalities of interleaving distances in coarser and coarser categories. We observe how, in our setting, the generalized definition of filtration gets freer than the classical one, by not requiring the functions between sublevels to be monomorphisms.

The target categories of choice in the classical approach to persistence ( $\mathbf{FinSet}$ or $\mathbf{FinVec}$ ) offer a clear correspondence between classes of isomorphism of objects and natural numbers, namely cardinality and dimension. To be able to deal with richer categories, we develop the concept of coloring, which allows us to recover the equality between interleaving and multicolored bottleneck distance.

Finally, we discuss and exemplify via toy examples several applications. In the Abelian semisimple case, we explicitly study the multicolored persistence and build the associated persistence diagram in the case of filtered simplicial complexes or point clouds with a group action. As much of the interest in persistent homology comes from its applications on real world data, we explore applications to point cloud data, where the extra structure is given by labels. Such datasets are routinely used in the training and testing of machine learning models on classification problems. Multicolored persistence naturally defines a topological notion of similarity of two datasets that keeps into account the labeling information. We speculate that such measure of similarity may be used to qualitatively assess the performance of machine learning models on classification problems.

References

[1] Michael F. Atiyah. On the Krull-Schmidt theorem with application to sheaves. Bulletin de la Société mathématique de France, 79:307–317, 1956.
[2] Woong Bae, Jaejun Yoo, and Jong Chul Ye. Beyond deep residual learning for image restoration: Persistent homology-guided manifold simplification. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops, pages 145–153, 2017.
[3] John C. Baez and James Dolan. Categorification. arXiv:math/9802029, February 1998. arXiv: math/9802029.
[4] Mattia G. Bergomi, Massimo Ferri, Pietro Vertechi, and Lorenzo Zuffi. Beyond topological persistence: Starting from networks. arXiv:1901.08051 [math], January 2019. arXiv: 1901.08051.
[5] Peter Bubenik and Jonathan A. Scott. Categorification of Persistent Homology. Discrete & Computational Geometry, 51(3):600–627, April 2014.
[6] Gunnar Carlsson. Topology and data. Bulletin of the American Mathematical Society, 46(2):255–308, 2009.
[7] Gunnar Carlsson, Tigran Ishkhanov, Vin De Silva, and Afra Zomorodian. On the local behavior of spaces of natural images. International journal of computer vision, 76(1):1–12, 2008.
[8] Frédéric Chazal, David Cohen-Steiner, Marc Glisse, Leonidas J. Guibas, and Steve Y. Oudot. Proximity of persistence modules and their diagrams. In Proceedings of the 25th annual symposium on Computational geometry - SCG ’09, page 237, Aarhus, Denmark, 2009. ACM Press.
[9] David Cohen-Steiner, Herbert Edelsbrunner, and John Harer. Stability of Persistence Diagrams. Discrete & Computational Geometry, 37(1):103–120, January 2007.
[10] Barbara Di Fabio and Claudia Landi. A Mayer–Vietoris Formula for Persistent Homology with an Application to Shape Recognition in the Presence of Occlusions. Foundations of Computational Mathematics, 11(5):499–527, October 2011.
[11] Michele d’Amico, Patrizio Frosini, and Claudia Landi. Natural Pseudo-Distance and Optimal Matching between Reduced Size Functions. Acta Applicandae Mathematicae, 109(2):527–554, February 2010.
[12] H. Edelsbrunner, D. Letscher, and A. Zomorodian. Topological persistence and simplification. In Proceedings 41st Annual Symposium on Foundations of Computer Science, pages 454–463, November 2000.
[13] Herbert Edelsbrunner and John Harer. Persistent homology-a survey. Contemporary mathematics, 453:257–282, 2008.
[14] Pavel Etingof, editor. Tensor categories. Number 205 in Mathematical surveys and monographs. American Math. Soc, Providence, RI, 2015. OCLC: 924601171.
[15] Massimo Ferri. Persistent topology for natural data analysis - A survey. arXiv:1706.00411 [math], June 2017. arXiv: 1706.00411.
[16] Patrizio Frosini. Measuring shapes by size functions. In Intelligent Robots and Computer Vision X: Algorithms and Techniques, volume 1607, pages 122–134. International Society for Optics and Photonics, 1992.
[17] Patrizio Frosini and Claudia Landi. Size Functions and Formal Series. Applicable Algebra in Engineering, Communication and Computing, 12(4):327–349, August 2001.
[18] Peter Gabriel. Unzerlegbare Darstellungen I. manuscripta mathematica, 6(1):71–103, March 1972.
[19] Steve Oudot. Persistence Theory: From Quiver Representations to Data Analysis, volume 209 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, Rhode Island, December 2015.
[20] Talha Qaiser, Korsuk Sirinukunwattana, Kazuaki Nakane, Yee-Wah Tsang, David Epstein, and Nasir Rajpoot. Persistent homology for fast tumor segmentation in whole slide histology images. Procedia Computer Science, 90:119–124, 2016.
[21] Jean-Pierre Serre, Leonard L Scott, and Springer Science+Business Media. Linear representations of finite groups. Springer, New York, 2014. OCLC: 883522602.

Appendix A Basic definitions and results

The aim of this section is to provide basic definitions of category theory to the unfamiliar reader.

A.1 Properties of morphisms

Definition A.1.1 (Epimorphism).

Consider $X,Y\in{\textnormal{Obj}}(\mathbf{C})$ . $f:X\to Y$ is an epimorphism if given the following diagram

if $g\circ f=h\circ f$ then $g=h$ .

Example A.1.1 (Epimorphism).

Let $X,Y\in{\textnormal{Obj}}(\mathbf{Set})$ and $f:X\rightarrow Y$ , then $f$ is an epimorphism if and only if it is surjective.

Definition A.1.2 (Monomorphism).

Consider $X,Y\in{\textnormal{Obj}}(\mathbf{C})$ . $f:X\to Y$ is a monomorphism if given the following diagram

if $f\circ g=f\circ h$ then $g=h$ .

Example A.1.2 (Monomorphism).

Let $X,Y\in{\textnormal{Obj}}(\mathbf{Set})$ and $f:X\rightarrow Y$ , then $f$ is a monomorphism if and only if it is injective.

A.2 Universal objects: limits and colimits

Many interesting objects can be defined in terms of universal properties. We will describe examples from two groups: limits (there are universal arrows to them) and colimits of diagrams (there are universal arrows from them).

Definition A.2.1 (Terminal object).

An object pt in a category $\mathbf{C}$ is called terminal if there exists a unique morphism $x\xrightarrow{!}{\textnormal{pt}}$ for any object $x\in\mathbf{C}$ . If it exists, the terminal object is unique, up to unique isomorphism. For instance, the point space pt is terminal in Top.

Definition A.2.2 (Initial object).

An object $\emptyset$ in a category $\mathbf{C}$ is initial if for any object $x\in\mathbf{C}$ there exists a unique morphism $\emptyset\xrightarrow{!}x$ .

Definition A.2.3 (Zero object and pointed category).

An object which is both initial and terminal is said zero object. A category $\mathbf{C}$ equipped with a zero object is said pointed.

Example A.2.1 (Zero object).

The trivial group $1$ is the zero object in $\mathbf{Grp}$ . Indeed $1\hookrightarrow G\twoheadrightarrow G/G=1$ , for every $G\in\mathbf{Grp}$ . In the category of $\mathbf{Vec}_{\mathbb{K}}$ of vector spaces on the field $\mathbb{K}$ , the zero object is the $0$ -dimensional vector space.

Definition A.2.4 (Product).

Let $X,Y$ be objects of a category $\mathbf{C}$ . The product of $X$ and $Y$ is the object $P$ , along with morphisms $\pi_{X}:Z\to X$ and $\pi_{Y}:Z\to Y$ , such that given another such $P^{\prime},\pi^{\prime}_{X},\pi^{\prime}_{y}$ , we have a unique morphism $P^{\prime}\to P$ that makes the following diagram commute:

We denote the product $X\times Y$ .

Definition A.2.5 (Coproduct).

Let $X,Y$ be objects of a category $\mathbf{C}$ . The coproduct of $X$ and $Y$ is the object $C$ , along with morphisms $\iota_{X}:X\to C$ and $\iota_{Y}:Y\to C$ , such that given another such $C^{\prime},\iota^{\prime}_{X},\iota^{\prime}_{Y}$ , we have a unique morphism $C\to C^{\prime}$ that makes the following diagram commute:

We denote the coproduct $X\amalg Y$ .

Example A.2.2 (Product and coproduct).

Let $X,Y\in{\textnormal{Obj}}(\mathbf{Set})$ . The product $X\times Y$ is simply the cartesian product. The coproduct $X\amalg Y$ is the disjoint union of $X$ and $Y$ .

Definition A.2.6 (Equalizer).

Let $X,Y$ be objects of $\mathbf{C}$ and consider two morphisms $X\xrightarrow{f}Y$ , $X\xrightarrow{g}Y$ . An object $Q$ , together with a morphism $Q\xrightarrow{q}Y$ is an equalizer if $f\circ q=g\circ q$ . Moreover, the pair $(Q,q)$ must be universal, i.e. given another coequalizer $(Q^{\prime},q^{\prime})$ , there exists a unique morphism $Q^{\prime}\xrightarrow{u}Q$ such that the following diagrams commutes.

Thus, equalizers are unique up to isomorphism. Moreover, every equalizer is a monomorphism.

Example A.2.3 (Equalizer).

Let $A,B\in{\textnormal{Obj}}(\mathbf{Set})$ and $f,g:A\rightarrow B$ , then the equalizer is

\{a\in A\;|\;f(a)=g(a)\}

Definition A.2.7 (Coequalizer).

Let $X,Y$ be objects of $\mathbf{C}$ and consider two morphisms $X\xrightarrow{f}Y$ , $X\xrightarrow{g}Y$ . An object $Q$ , together with a morphism $Y\xrightarrow{q}Q$ is a coequalizer if $q\circ f=q\circ g$ . Moreover, the pair $(Q,q)$ must be universal, i.e. given another coequalizer $(Q^{\prime},q^{\prime})$ , there exists a unique morphism $Q\xrightarrow{u}Q^{\prime}$ such that the following diagrams commutes.

Thus, coequalizers are unique up to isomorphism. Moreover, every coequalizer is an epimorphism.

Example A.2.4 (Coequalizer).

Let $A,B\in{\textnormal{Obj}}(\mathbf{Set})$ and $f,g:A\rightarrow B$ , then the coequalizer is the quotient of $B$ with $\sim$ , such that $f(x)\sim g(x)$ for every $x\in A$ .

Definition A.2.8 (Finitely (co)complete category).

A category $\mathbf{C}$ is finitely complete if it has equalizers, a terimal object and binary products. Analogously, a category $\mathbf{C}$ is finitely cocomplete if it has coequalizers, an initial object and binary coproducts.

Definition A.2.9 (Pullback).

Let $X,Y$ and $Z$ be objects of a category $\mathbf{C}$ , and $X\xrightarrow{f}Z$ , $Y\xrightarrow{g}Z$ morphisms. An object $P$ and the morphisms $P\xrightarrow{p_{1}}X$ , $P\xrightarrow{p_{2}}Y$ is a pullback if the following diagram

commutes and, given another such $P^{\prime},p_{1}^{\prime},p_{2}^{\prime}$ we have a unique morphism $P^{\prime}\xrightarrow{u}P$ that makes the following diagram commute:

That is to say, the pullback is universal with respect to the diagram, and thus unique up to isomorphism. We denote it $X\times_{Z}Y$ .

Remark A.2.1.

The pullback $X\times_{Z}Y$ is the equalizer of the natural maps $Z\rightrightarrows X\times Y$ .

Example A.2.5 (Pullback).

Given three sets $X,Y$ and $Z$ and functions $X\xrightarrow{f}Z$ , $Y\xrightarrow{g}Z$ , the coproduct $X\times_{Z}Y$ is the subset of the cartesian product:

X\times_{Z}Y=\{(x,y)\;|\;x\in X,\;y\in Y\text{ and }f(x)=g(y)\}

Example A.2.6 (Fiber).

In the category of sets, let pt be the terminal object. Let $f:X\rightarrow Y$ be a map between sets and $y\in Y$ . The fiber over $y$ is $f^{-1}(y)\subset X$ realised by the pullback

A.3 Regular, Abelian and semisimple categories

Definition A.3.1 (Regular epimorphism).

An epimorphism that is the coequalizer of a parallel pair of morphism.

Definition A.3.2 (Regular category).

A category $\mathbf{R}$ is regular if the following conditions hold:

1.

$\mathbf{R}$ is finitely complete.
2.

Given $X\xrightarrow{f}Y$ a morphism and its pullback $(P,p_{1},p_{2})$ , then the coequalizer of $p_{1}$ and $p_{2}$ exists.
3.

Given the pullback

if $f$ is a regular epimorphism, so is $g$ .

We will introduce some preparatory concepts to the definition of Abelian category.

Kernels and cokernels

Let $\mathbf{C}$ be a category and $\xi:X\to Y$ a morphism. If for every object $Z$ and morphisms $g,h:Z\to X$ , we have $\xi g=\xi h$ , then $\xi$ is said a (left) zero morphism. If $\mathbf{C}$ is pointed, i.e. it has a zero object $0$ , then given two objects $X,Y$ there exists a unique zero morphism $\xi:X\to Y$ given by the composition $X\to 0\to Y$ .

Definition A.3.3 (Kernel).

Let $\mathbf{C}$ be a category with zero morphism $\xi$ and $f:X\to Y$ a morphism. The kernel of $f$ is defined as the equalizer of $\xi$ and $f$ .

Definition A.3.4 (Cokernel).

Let $\mathbf{C}$ be a category with zero morphism $\xi$ and $f:X\to Y$ a morphism. The cokernel of $f$ is defined as the coequalizer of $\xi$ and $f$ .

Definition A.3.5 (Abelian category).

A category $\mathbf{C}$ is abelian if

1.

it is pointed, i.e. $\mathbf{C}$ has a zero objet;
2.

has binary products and binary coproducts;
3.

every morphism has kernel and cokernel;
4.

each monomorphism is a kernel and each epimorphism is a cokernel.

In an Abelian category, the binary product and binary coproduct coincide and are sometimes called biproduct. We will sometimes simply call it sum, in analogy with the sum of vector spaces.

Definition A.3.6 (Simple object).

Let $\mathbf{C}$ be an Abelian category. An object $X\in{\textnormal{Obj}}(\mathbf{C})$ is simple if its only subobjects are $0$ and $X$ .

Lemma A.3.1 (Schur Lemma).

Given $S,S^{\prime}$ simple objects in an Abelian category, morphisms from $S$ to $S^{\prime}$ are either zero or invertible.

Definition A.3.7 (Semisimple category).

An Abelian category is semisimple if all its objects are semisimple, i.e. each object can be written as a finite sum of simple objects.

Rank-based persistence

Abstract

Keywords

AMS subject classification

1 Introduction

2 Rank functions in regular categories

Definition 1.

Proposition 1.

Proof.

Proposition 2.

Proof.

2.1 Fiber-wise rank functions

Definition 2.

Proposition 3.

Proof.

Proposition 4.

Proposition 5.

Proof.

Examples of fiber-wise rank functions

Proposition 6.

Proof.

Remark 1.

3 Categorical persistence

3.1 Categorical persistence functions

Definition 3.

Proposition 7.

Proof.

Remark 2.

Proposition 8.

Proof.

Proposition 9.

Remark 3 ((ℝ,≤){(\mathbb{R},\leq)}-indexed diagrams).

3.2 Persistence diagrams

Definition 4.

Lemma 1.

Proof.

Lemma 2.

Proof.

Definition 5.

Remark 4.

Remark 5 (Cornerpoints at infinity).

Definition 6.

Proposition 10.

Proof.

3.3 Indecomposable persistence modules

Definition 7.

Proposition 11.

Proof.

Theorem 1.

Proof.

3.4 Interleaving and bottleneck distances

Definition 8.

Definition 9.

Lemma 3 (Box lemma).

Proof.

Lemma 4 (Interpolation lemma).

Proof.

Theorem 2.

Proof.

Definition 10.

Theorem 3.

Proof.

4 Multicolored persistence

Definition 11.

4.1 Multicolored persistence diagrams

Lemma 5.

Proof.

Definition 12.

Theorem 4.

Proof.

Theorem 5.

Proof.

4.2 Persistent homology on simplicial complexes with a group action

Application: Vietoris-Rips filtration under a group action

4.3 Persistent homology on labeled point clouds

Application: Vietoris-Rips filtration with labeled data

5 Conclusion

References

Appendix A Basic definitions and results

A.1 Properties of morphisms

Remark 3 ( ${(\mathbb{R},\leq)}$ -indexed diagrams).