Generalized persistence diagrams

Abstract

We generalize the persistence diagram of Cohen-Steiner, Edelsbrunner, and Harer to the setting of constructible persistence modules valued in a symmetric monoidal category. We call this the type ${\mathcal {A}}$ persistence diagram of a persistence module. If the category is also abelian, then we define a second type ${\mathcal {B}}$ persistence diagram. In addition, we show that both diagrams are stable to all sufficiently small perturbations of the module. The type ${\mathcal {B}}$ persistence diagram carries less information than the type ${\mathcal {A}}$ persistence diagram, but it enjoys a stronger stability theorem.

1 Introduction

Let $f : {\mathbb M}\rightarrow {\mathbb R}$ be a Morse function on a compact manifold ${\mathbb M}$. The function f filters ${\mathbb M}$ by sublevel sets ${\mathbb M}_{f \le r} = \{ x \in {\mathbb M}\; | \; f(x) \le r \}.$ Apply homology with coefficients in a field and we call the resulting object ${\mathsf {F}}$ a constructible persistence module of vector spaces. The persistence diagram and the barcode are two invariants of a persistence module obtained as follows.

• By Images: Edelsbrunner et al. (2002) define the persistent homology group ${\mathsf {F}}_s^t$, for $s < t$, as the image of ${\mathsf {F}}(s < t)$. Cohen-Steiner et al. (2007) define the persistence diagram of ${\mathsf {F}}$ as a finite set of points in the plane above the diagonal satisfying the following property. For each $s < t$, the number of points in the upper-left quadrant defined by (s, t) is the rank of ${\mathsf {F}}_s^t$.

• By Indecomposables: The module ${\mathsf {F}}$ is isomorphic to a finite direct sum of indecomposable persistence modules ${\mathsf {F}} \cong {\mathsf {F}}_1 \oplus \cdots \oplus {\mathsf {F}}_n.$ Any two ways of writing ${\mathsf {F}}$ as a sum of indecomposables are the same up to a reordering of the indecomposables. Furthermore, each indecomposable ${\mathsf {F}}_i$ is an interval persistence module. That is, there are a pair of values $r < t$, where t may be infinite, such that $F_i(s)$ is a copy of the field for all values $r \le s < t$ and zero elsewhere.¹ Zomorodian and Carlsson (2005) define the barcode of ${\mathsf {F}}$ as its list of indecomposables. See also Gunnar Carlsson and Vin de Silva (2010).

A barcode translates to a persistence diagram by plotting the left endpoint versus the right endpoint of each interval persistence module. A persistence diagram translates to a barcode by turning each point (s, t) in to an interval persistence module starting at s and ending at t. In this way, the persistence diagram is equivalent to a barcode. However, the two definitions are very different in philosophy.

Suppose the homology of each sublevel set ${\mathbb M}_{f \le r}$ is calculated using integer coefficients. Then the resulting object ${\mathsf {F}}$ is a constructible persistence module of finitely generated abelian groups. However, an indecomposable persistence module of finitely generated abelian groups need not look anything like an interval persistence module. For example, the module in Fig. 4 is indecomposable. Indecomposables are hard to interpret especially under perturbations to the module.

We generalize the persistence diagram of Cohen-Steiner, Edelsbrunner, and Harer to the setting of constructible persistence modules ${\mathsf {F}}$ valued in a symmetric monoidal category ${\mathsf {C}}$ with images. The category of sets, the category of vector spaces, and the category of finitely generated abelian groups are examples of such categories. We call this diagram the type ${\mathcal {A}}$ persistence diagram of ${\mathsf {F}}$. If ${\mathsf {C}}$ is also abelian, then we define a second type ${\mathcal {B}}$ persistence diagram of ${\mathsf {F}}$. The category of vector spaces and the category of abelian groups are examples of abelian categories. The type ${\mathcal {B}}$ persistence diagram of ${\mathsf {F}}$ may contain less information than the type ${\mathcal {A}}$ persistence diagram of ${\mathsf {F}}$. However, the advantage of a type ${\mathcal {B}}$ diagram is a stronger statement of stability. Depending on ${\mathsf {C}}$, our persistence diagrams may not be a complete invariant of a persistence module.

Persistence is motivated by data analysis and data is noisy. A small perturbation to a persistence module should not result in a drastic change to its persistence diagram. We use the standard interleaving distance to measure differences between persistence modules (Chazal et al. 2009). We define a new metric we call erosion distance to measure differences between persistence diagrams. In Theorem 8.2, we show that if the interleaving distance between two constructible persistence modules valued in an abelian category ${\mathsf {C}}$ is $\varepsilon$, then the erosion distance between their type ${\mathcal {B}}$ persistence diagrams is at most $\varepsilon$. We call this continuity of type ${\mathcal {B}}$ persistence diagrams. If ${\mathsf {C}}$ is simply a symmetric monoidal category, then Theorem 8.1 is a weaker one-way statement of continuity for type ${\mathcal {A}}$ persistence diagrams. We call this semicontinuity of type ${\mathcal {A}}$ persistence diagrams. These theorems show that the information contained in both diagrams is stable to all sufficiently small perturbations of the module.

Cohen-Steiner, Edelsbrunner, and Harer define a stronger metric on the set of persistence diagrams they call bottleneck distance. They show that for two Morse functions $f ,g : {\mathbb M}\rightarrow {\mathbb R}$, the bottleneck distance between their persistence diagrams is at most $\max |f-g|$. They do this by looking at the 1-parameter family of persistence modules obtained from the linear interpolation $h : {\mathbb M}\times [0,1] \rightarrow {\mathbb R}$ taking $h_0 = f$ to $h_1 = g$. Using the Box Lemma, which is a local statement of stability, they track each point in the persistence diagram of $h_0$ all the way to the persistence diagram of $h_1$. Theorem 8.1 resembles the Box Lemma and assuming ${\mathsf {C}}$ has colimits, there is a way to construct a 1-parameter 1-Lipschitz family of persistence modules between any two interleaved persistence modules (Peter Bubenik et al. 2017). This suggests that bottleneck stability might extend to type ${\mathcal {A}}$ persistence diagrams. We leave the issue of bottleneck stability for future investigations.

2 Persistence modules

Let $({\mathsf {C}}, \Box )$ be an essentially small symmetric monoidal category with images. By essentially small, we mean that the collection of isomorphism classes of objects in ${\mathsf {C}}$ is a set. A symmetric monoidal category is, roughly speaking, a category ${\mathsf {C}}$ with a binary operation $\Box$ on its objects and an identity object $e \in {\mathsf {C}}$ satisfying the following properties:

• (Symmetry) $a \Box b \cong b \Box a$, for all objects $a, b \in {\mathsf {C}}$

• (Associativity) $a \Box (b \Box c) \cong (a \Box b) \Box c$, for all objects $a,b,c \in {\mathsf {C}}$

• (Identity) $a \Box e \cong a$, for all objects $a \in {\mathsf {C}}$.

See Weibel (2013, page 114) for a precise definition of a symmetric monoidal category. By images, we mean that for every morphism $f : a \rightarrow b$, there is a monomorphism $h : z \rightarrow b$ and a morphism $g : a \rightarrow z$ such that $f = h \circ g$. Furthermore, for a monomorphim $h' : z' \rightarrow b$ and a morphism $g' : a \rightarrow z'$ such that $f = h' \circ g'$, there is a unique morphism $u : z \rightarrow z'$ such that the following diagram commutes:

See Mitchell (1965, page 12) for a discussion of images.

Definition 2.1

A persistence module is a functor ${\mathsf {F}} : ({\mathbb R}, \le ) \rightarrow {\mathsf {C}}$ out of the poset of real numbers.

Let $S = \{s_1< \cdots < s_n \}$ be a finite set of real numbers. Let $e \in {\mathsf {C}}$ be an identity object.

Definition 2.2

A persistence module ${\mathsf {F}}$ is S-constructible if

• for $p \le q < s_1$, ${\mathsf {F}}(p \le q)$ is the identity on e

• for $s_i \le p \le q < s_{i+1}$, ${\mathsf {F}}(p \le q)$ is an isomorphism

• for $s_n \le p \le q$, ${\mathsf {F}}(p \le q)$ is an isomorphism.

We say ${\mathsf {F}}$ is constructible if there is a finite set S such that ${\mathsf {F}}$ is S-constructible. If ${\mathsf {F}}$ is S-constructible then it is also T-constructible for any $T \supseteq S$.

We draw examples from the following five essentially small symmetric monoidal categories with images.

Example 2.1

Let ${\mathsf {FinSet}}$ be the category of finite sets. ${\mathsf {FinSet}}$ is a symmetric monoidal category under finite colimits (disjoint unions). A constructible persistence module valued in this category is often called a merge tree (Morozov et al. 2013).

The following four categories have more structure: they are abelian (see Weibel 2013, page 124) and Krull-Schmidt (see Appendix). In short, an abelian category is a category that behaves like the category of abelian groups. Finite products and coproducts are the same. Every morphism has a kernel and a cokernel. Every monomorphism is the kernel of some morphism, and every epimorphism is the cokernel of some morphism. The symmetric monoidal operation $\Box$ is the direct sum $\oplus$.

Example 2.2

Let ${\mathsf {Vec}}$ be the category of finite dimensional $\mathsf {k}$-vector spaces, for some fixed field $\mathsf {k}$. Each vector space $a \in {\mathsf {Vec}}$ is isomorphic to $\mathsf {k}_1 \oplus \mathsf {k}_2 \oplus \cdots \oplus \mathsf {k}_n$, where n is the dimension of a. Note that every short exact sequence $0 \rightarrow a \rightarrow b \rightarrow c \rightarrow 0$ splits. That is, $b \cong a \oplus c$.

Example 2.3

Let ${\mathsf {Ab}}$ be the category of finitely generated abelian groups. An indecomposable of ${\mathsf {Ab}}$ is isomorphic to the infinite cyclic group ${\mathbb Z}$ or to a primary cyclic group ${{\mathbb Z}}/{p^m {\mathbb Z}}$, for a prime p and a positive integer m. By the fundamental theorem of finitely generated abelian groups, each object is uniquely isomorphic to

$$\begin{aligned} {\mathbb Z}^n \oplus \frac{{\mathbb Z}}{p_1^{m_1} {\mathbb Z}} \oplus \frac{{\mathbb Z}}{p_2^{m_2}{\mathbb Z}} \oplus \cdots \oplus \frac{{\mathbb Z}}{p_k^{m_k}{\mathbb Z}}, \end{aligned}$$

for some $n \ge 0$ and primary cyclic groups ${{\mathbb Z}}/{ p_i^{m_i} {\mathbb Z}}$. Not every short exact sequence in this category splits. Consider the following short exact sequence

Of course ${{\mathbb Z}}/{ 4 {\mathbb Z}}$ is not isomorphic to ${{\mathbb Z}}/{ 2 {\mathbb Z}} \oplus {{\mathbb Z}}/{ 2 {\mathbb Z}}$. A finitely generated abelian group is simple iff it is isomorphic to ${{\mathbb Z}}/{ p {\mathbb Z}}$ for p prime. That is, ${{\mathbb Z}}/{ p {\mathbb Z}}$ has no subgroups other than 0 and itself.

Example 2.4

Let ${\mathsf {FinAb}}$ be the category of finite abelian groups. An indecomposable of ${\mathsf {FinAb}}$ is isomorphic to a primary cyclic group ${\mathbb Z}/ p^m {\mathbb Z}$, for prime p and a positive integer m. By the fundamental theorem of finitely generated abelian groups, each object is uniquely isomorphic to

$$\begin{aligned} \frac{{\mathbb Z}}{p_1^{m_1} {\mathbb Z}} \oplus \frac{{\mathbb Z}}{p_2^{m_2}{\mathbb Z}} \oplus \cdots \oplus \frac{{\mathbb Z}}{p_k^{m_k}{\mathbb Z}}. \end{aligned}$$

As shown in the previous example, not every short exact sequence in this category splits.

Example 2.5

Let ${\mathsf {Rep}}({\mathbb N})$ be the category of functors from the commutative monoid of natural numbers ${\mathbb N}= \{0, 1, \ldots \}$ to ${\mathsf {Vec}}$. We think of ${\mathbb N}$ as a category with a single object and an endomorphism for each $n \in {\mathbb N}$ where $n \circ m$ is $n+m$. A functor in ${\mathsf {Rep}}({\mathbb N})$ is completely determined by where it sends 1. ${\mathsf {Rep}}({\mathbb N})$ is therefore equivalent to the category whose objects are endomorphisms $A : a \rightarrow a$ in ${\mathsf {Vec}}$ and whose morphisms $f : A \rightarrow B$ are maps $\hat{f} : a \rightarrow b$ such that the following diagram commutes:

We represent each object of ${\mathsf {Rep}}({\mathbb N})$ by a square matrix of elements in $\mathsf {k}$. Suppose $\mathsf {k}$ is algebraically closed. Then such a matrix decomposes into a Jordan normal form

$$\begin{aligned} \begin{pmatrix} J_1 & & \\ & \ddots & \\ & & J_n \end{pmatrix} \end{aligned}$$

where each Jordan block is of the form

$$\begin{aligned} J_i = \begin{pmatrix} \lambda _i & 1 & & \\ & \lambda _i & \ddots & \\ & & \ddots & 1 \\ & & & \lambda _i \end{pmatrix}. \end{aligned}$$

The indecomposables of ${\mathsf {Rep}}({\mathbb N})$ are Jordan blocks. An object of ${\mathsf {Rep}}({\mathbb N})$ is simple iff its a Jordan block of dimension one.

Not every short exact sequence in ${\mathsf {Rep}}({\mathbb N})$ splits. Let $A : \mathsf {k}\rightarrow \mathsf {k}$ be given by $(\lambda )$, let $B : k^2 \rightarrow k^2$ be given by $\begin{pmatrix} \lambda & 1 \\ 0 & \lambda \end{pmatrix}$, and let $f : A \rightarrow B$ be given by $\hat{f}(x) = (x,0)$. The quotient $C = B / \mathrm {im}f$ is isomorphic to A. This gives us a short exact sequence

that does not split because B is not isomorphic to $(\lambda ) \oplus (\lambda ) = \begin{pmatrix} \lambda & 0 \\ 0 & \lambda \end{pmatrix}$.

Let ${\mathsf {PMod}}({\mathsf {C}})$ be the full subcategory of the functor category $\left[ ({\mathbb R}, \le ), {\mathsf {C}}\right]$ consisting of constructible persistence modules. Henceforth, all persistence modules are constructible.

3 Interleaving distance

There is a natural distance between persistence modules. For $\varepsilon \in {\mathbb R}$, let

$$\begin{aligned} \mathsf {Shift}^\varepsilon : ({\mathbb R}, \le ) \rightarrow ({\mathbb R}, \le ) \end{aligned}$$

be the poset map that sends r to $r+\varepsilon$. If ${\mathsf {F}} \in {\mathsf {PMod}}$ is S-constructible, then ${\mathsf {F}} \circ \mathsf {Shift}^\varepsilon$ is $(S+\varepsilon )$-constructible. Thus $\mathsf {Shift}^\varepsilon$ gives rise to a functor

$$\begin{aligned} \Delta ^\varepsilon : {\mathsf {PMod}}({\mathsf {C}}) \rightarrow {\mathsf {PMod}}({\mathsf {C}}). \end{aligned}$$

For each $\varepsilon \ge 0$, there is a canonical morphism $\sigma ^\varepsilon _{\mathsf {F}} : {\mathsf {F}} \rightarrow \Delta ^\varepsilon ({\mathsf {F}})$ given by $\sigma ^\varepsilon _{\mathsf {F}}(r) = {\mathsf {F}}(r \le r+ \varepsilon )$.

Definition 3.1

Two modules ${\mathsf {F}}, {\mathsf {G}} \in {\mathsf {PMod}}({\mathsf {C}})$ are $\varepsilon$-interleaved if there are morphisms $\phi : {\mathsf {F}} \rightarrow \Delta ^\varepsilon ({\mathsf {G}})$ and $\psi : {\mathsf {G}} \rightarrow \Delta ^\varepsilon ({\mathsf {F}})$ such that $\sigma ^{2\varepsilon }_{\mathsf {F}} = \Delta ^\varepsilon (\psi ) \circ \phi$ and $\sigma ^{2\varepsilon }_{\mathsf {G}} = \Delta ^\varepsilon (\phi ) \circ \psi$.

Any two persistence modules ${\mathsf {F}}$ an ${\mathsf {G}}$ are constructible with respect to a common set $T = \{ t_1< \cdots < t_m \}$. Both ${\mathsf {F}}$ and ${\mathsf {G}}$ are therefore constant over the half-open intervals $[t_i, t_{i+1})$ and $[t_m, \infty )$. As a consequence, if there is an interleaving between ${\mathsf {F}}$ and ${\mathsf {G}}$, then there is a minimum interleaving between ${\mathsf {F}}$ and ${\mathsf {G}}$.

Definition 3.2

The interleaving distance $\mathsf {d}_I({\mathsf {F}}, {\mathsf {G}})$ between two persistence modules is the minimum over all $\varepsilon \ge 0$ such that ${\mathsf {F}}$ and ${\mathsf {G}}$ are $\varepsilon$-interleaved. If ${\mathsf {F}}$ and ${\mathsf {G}}$ are not interleaved, let $\mathsf {d}_I({\mathsf {F}}, {\mathsf {G}}) = \infty$.

Example 3.1

Let $f : {\mathbb M}\rightarrow {\mathbb R}$ be a Morse function on a compact manifold ${\mathbb M}$. The function f filters ${\mathbb M}$ by sublevel sets ${\mathbb M}_{f \le r}$. Apply homology with coefficients in $\mathsf {k}$ and the resulting object is in ${\mathsf {PMod}}({\mathsf {Vec}})$. Apply homology with integer coefficients and the resulting object is in ${\mathsf {PMod}}({\mathsf {Ab}})$. Apply homology with coefficients in a finite abelian group G and the resulting object is in ${\mathsf {PMod}}({\mathsf {FinAb}})$. Suppose $\varepsilon > |f-g|$. Then ${\mathbb M}_{f \le r} \subseteq {\mathbb M}_{g \le r+\varepsilon } \subseteq {\mathbb M}_{f \le r + 2 \varepsilon }$ implying, by functoriality of homology, an $\varepsilon$-interleaving between the two persistence modules.

Remark 3.1

The idea of interleavings appears in Cohen-Steiner et al. (2007) but it is not named until (Chazal et al. 2009). Since then, interleavings have been abstracted to other settings (Morozov et al. 2013; Peter Bubenik and Jonathan Scott 2014; Justin Curry 2014; Peter Bubenik et al. 2015; Lesnick 2015; De Silva et al. 2016).

4 Persistence diagrams

We now generalize the persistence diagram of Cohen-Steiner, Edelsbrunner, and Harer.

Definition 4.1

Define $({\mathsf {Dgm}}, \supseteq )$ as the poset of all half-open intervals $[q,r) \subset {\mathbb R}$, for $q < r$, and all half-infinite intervals $[q, \infty ) \subset {\mathbb R}$. The poset relation is the containment relation.

Let $S = \{ s_1< \cdots < s_n \}$ be a finite set of real numbers and ${\mathcal {G}}$ an abelian group. In the setting of Cohen-Steiner, Edelsbrunner, and Harer, the group ${\mathcal {G}}$ is the integers. From this we shall construct the persistence diagram.

Definition 4.2

A map $X : {\mathsf {Dgm}}\rightarrow {\mathcal {G}}$ is S-constructible if for every $J \supseteq I$ such that $J \cap S = I \cap S$, $X(I) = X(J)$. We say a map $X : {\mathsf {Dgm}}\rightarrow {\mathcal {G}}$ is constructible if it is S-constructible for some set S.

In the setting of Cohen-Steiner, Edelsbrunner, and Harer, X is the rank function.

Definition 4.3

A map $Y : {\mathsf {Dgm}}\rightarrow {\mathcal {G}}$ is S-finite if $Y(I) \ne e$ implies $I = [s_i,s_j)$ or $I = [s_i,\infty )$. We say a map $Y : {\mathsf {Dgm}}\rightarrow {\mathcal {G}}$ is finite if it is T-finite for some set T.

Definition 4.4

A persistence diagram is a finite map $Y : {\mathsf {Dgm}}\rightarrow {\mathcal {G}}$.

We visualize the poset ${\mathsf {Dgm}}$ as the set of points in the extended plane ${\mathbb R}\times {\mathbb R}\cup \{\infty \}$ above the diagonal. We visualize a persistence diagram Y by marking each $I \in {\mathsf {Dgm}}$ for which $Y(I) \ne [e]$ with the group element Y(I). See Figs. 2, 3, 4, 5, and 6.

Theorem 4.1

(Möbius Inversion Formula) For any S-constructible map $X : {\mathsf {Dgm}}\rightarrow {\mathcal {G}}$, there is an S-finite map $Y : {\mathsf {Dgm}}\rightarrow {\mathcal {G}}$ satisfying the Möbius inversion formula

$$\begin{aligned} X(I) = \sum _{J \in {\mathsf {Dgm}}: J \supseteq I} Y(J), \end{aligned}$$

for each $I \in {\mathsf {Dgm}}$.

Proof

Let $S = \{ s_1< \cdots < s_n \}$. Define

$$\begin{aligned} Y\left( [s_i,s_j)\right)= X\left( [s_i,s_j)\right) - X\left( [s_i,s_{j+1})\right) + X\left( [s_{i-1},s_{j+1})\right) - X\left( [s_{i-1},s_j)\right) \end{aligned}$$

(1)

$$\begin{aligned} Y\left( [s_i,\infty )\right)= X\left( [s_i,\infty )\right) - X\left( [s_{i-1},\infty )\right) . \end{aligned}$$

(2)

Here we interpret $s_0$ as any value less than $s_1$ and $s_{n+1}$ as any value greater than $s_{n}$. Define $Y(I) = e$ for all other $I \in {\mathsf {Dgm}}$. Let us check that Y satisfies the Möbius inversion formula. Fix an interval $I \in {\mathsf {Dgm}}$. Suppose $I = [s_i,s_j)$. We have

$$\begin{aligned} \sum _{J \in {\mathsf {Dgm}}: J \supseteq I} Y(J)&= \sum _{k = j}^{n} \sum _{h=1}^{i} Y\left( [s_h,s_k)\right) + \sum _{h=1}^{i} Y\left( [s_h,\infty )\right) \\&= \sum _{k = j}^{n} \sum _{h=1}^{i} \left[ X\left( [s_h,s_k)\right) - X\left( [s_h,s_{k+1})\right) \right. \\&\quad \left. + X\left( [s_{h-1},s_{k+1})\right) - X\left( [s_{h-1},s_k)\right) \right] \\&\quad + \sum _{h=1}^{i} \left[ X\left( [s_h,\infty )\right) - X\left( [s_{h-1},\infty )\right) \right] \\&= \sum _{k=j}^{n} \left[ X\left( [s_i,s_k)\right) - X\left( [s_i, s_{k+1})\right) \right] + X\left( [s_i,\infty )\right) \\&= X\left( [s_i,s_j)\right) . \end{aligned}$$

Suppose I is of the form $[s_i,\infty )$. We have

$$\begin{aligned} \sum _{J \in {\mathsf {Dgm}}: J \supseteq I} Y(J)&= \sum _{h=1}^{i} Y \left( [s_h,\infty ) \right) \\&= \sum _{h=1}^{i} \left[ X\left( [s_h,\infty )\right) - X\left( [s_{h-1},\infty )\right) \right] \\&= X\left( [s_i,\infty )\right) . \end{aligned}$$

Suppose I is not of the form $[s_i,s_j)$. Then there is an $I' \in {\mathsf {Dgm}}$ of the form $[s_i,s_j)$ or $[s_i, \infty )$ such that $I' \cap S = I \cap S$. We have

$$\begin{aligned} \sum _{J \in {\mathsf {Dgm}}: J \supseteq I} Y(J) = \sum _{J \in {\mathsf {Dgm}}: J \supseteq I'} Y(J) = X\left( I'\right) = X(I). \end{aligned}$$

$\square$

The persistence diagram Y of Cohen-Steiner, Edelsbrunner, and Harer is the Möbius inversion of the rank function X.

Remark 4.1

The Möbius inversion formula applies to any constructible map from a poset to an abelian group. See Rota (1964), Bender and Goldman (1975) and Leinster (2012). This suggests a notion of a persistence diagram for constructible persistence modules not just over $({\mathbb R}, \le )$ but over more general posets. See Peter Bubenik and Jonathan Scott (2014) and Peter Bubenik et al. (2015).

5 Erosion distance

The interleaving distance suggests a natural metric between persistence diagrams. But first, we need a notion of a morphism between persistence diagrams.

Let $({\mathcal {G}}, \preceq )$ be an abelian group with a translation invariant partial ordering on its elements. That is if $a \preceq b$, then $a+c \preceq b+c$ for any $c \in {\mathcal {G}}$. Let $e \in {\mathcal {G}}$ be the additive identity.

Definition 5.1

Let $Y_1, Y_2 : {\mathsf {Dgm}}\rightarrow ({\mathcal {G}}, \preceq )$ be two persistence diagrams. A morphism $Y_1 \rightarrow Y_2$ of persistence diagrams is the relation

$$\begin{aligned} \sum _{J \in {\mathsf {Dgm}}: J \supseteq I} Y_1(J) \preceq \sum _{J \in {\mathsf {Dgm}}: J \supseteq I} Y_2(J), \end{aligned}$$

for each $I \in {\mathsf {Dgm}}$. Let ${\mathsf {PDgm}}({\mathcal {G}})$ be the poset of persistence diagrams valued in $({\mathcal {G}}, \preceq )$.

For any $\varepsilon \ge 0$, let ${\mathsf {Grow}}^\varepsilon : {\mathsf {Dgm}}\rightarrow {\mathsf {Dgm}}$ be the poset map that sends each [p, q) to $[p-\varepsilon ,q+\varepsilon )$ and each $[p,\infty )$ to $[p-\varepsilon , \infty )$. For a morphism $Y_1 \rightarrow Y_2$ in ${\mathsf {PDgm}}({\mathcal {G}})$, we have $Y_1 \circ {\mathsf {Grow}}^\varepsilon \rightarrow Y_2 \circ {\mathsf {Grow}}^\varepsilon$. Thus ${\mathsf {Grow}}^\varepsilon$ gives rise to a functor

$$\begin{aligned} \nabla ^\varepsilon : {\mathsf {PDgm}}({\mathcal {G}}) \rightarrow {\mathsf {PDgm}}({\mathcal {G}}) \end{aligned}$$

given by precomposition with ${\mathsf {Grow}}^\varepsilon$. For each $\varepsilon \ge 0$, we have $\nabla ^\varepsilon (Y) \rightarrow Y$. The persistence diagram $\nabla ^\varepsilon (Y)$ is visualized as the persistence diagram Y with all its points shifted towards the diagonal by a distance $\sqrt{2} \varepsilon$. See Fig. 1.

Fig. 1

The $\varepsilon$-erosion $\nabla ^\varepsilon (Y)$ (circle) of a persistence diagram Y (dots) slides each point of Y to the lower-right corner of the square of side length $2\varepsilon$ centered at that point. Points close to the diagonal disappear into the diagonal. Note that $\nabla ^\varepsilon (Y) \rightarrow Y$

Definition 5.2

An $\varepsilon$-erosion between two persistence diagrams $Y_1, Y_2, \in {\mathsf {PDgm}}({\mathcal {G}})$ is a pair of morphisms $\nabla ^\varepsilon (Y_2) \rightarrow Y_1$ and $\nabla ^\varepsilon (Y_1) \rightarrow Y_2$.

Any two persistence diagrams are finite with respect to a common set $T = \{t_1< \cdots < t_n\}$. As a consequence, if there is an $\varepsilon$-erosion between $Y_1$ and $Y_2$, then there is a minimum $\varepsilon$ for which there is an $\varepsilon$-erosion.

Definition 5.3

The erosion distance $\mathsf {d}_E(Y_1, Y_2)$ is the minimum over all $\varepsilon \ge 0$ such that there is an $\varepsilon$-erosion between $Y_1$ and $Y_2$. If there is no $\varepsilon$-erosion, let $\mathsf {d}_E(Y_1,Y_2) = \infty$.

Proposition 5.1

Let $X : {\mathsf {Dgm}}\rightarrow {\mathcal {G}}$ be a constructible map and let $Y : {\mathsf {Dgm}}\rightarrow {\mathcal {G}}$ be a finite map that satisfies the Möbius inversion formula

$$\begin{aligned} X(I) = \sum _{J \in {\mathsf {Dgm}}: J \supseteq I} Y(J), \end{aligned}$$

for each $I \in {\mathsf {Dgm}}$. Then

$$\begin{aligned} X \circ {\mathsf {Grow}}^\varepsilon (I) = \sum _{J \in {\mathsf {Dgm}}: J \supseteq I} \nabla ^\varepsilon (Y)(J), \end{aligned}$$

for each $I \in {\mathsf {Dgm}}$. In other words, ${\mathsf {Grow}}^\varepsilon$ commutes with the Möbius inversion formula.

Proof

We have

$$\begin{aligned} \sum _{J \in {\mathsf {Dgm}}: J \supseteq I} \nabla ^\varepsilon (Y)(J)&=\sum _{J \in {\mathsf {Dgm}}: J \supseteq I} Y \circ {\mathsf {Grow}}^\varepsilon (J) \\&= X \circ {\mathsf {Grow}}^\varepsilon (I) \end{aligned}$$

$\square$

Remark 5.1

The erosion distance first appears in Edelsbrunner et al. (2011) which is an early attempt to develop a theory of persistence for maps from a surface to the Euclidean plane.

6 Grothendieck groups

We are interested in two abelian groups: the Grothendieck group ${\mathcal {A}}$ of an essentially small symmetric monoidal category and the Grothendieck group ${\mathcal {B}}$ of an essentially small abelian category. See Weibel (2013) for an introduction to the two Grothendieck groups. Note that every abelian category is a symmetric monoidal category under the direct sum $\oplus$ and the additivity identity is the zero object.

6.1 Symmetric monoidal category

Let ${\mathsf {C}}$ be an essentially small monoidal category. The set ${\mathcal {I}}({\mathsf {C}})$ of isomorphism classes in ${\mathsf {C}}$ is a commutative monoid under $\Box$. We write the isomorphism class of an object $a \in {\mathsf {C}}$ as $[a] \in {\mathcal {I}}({\mathsf {C}})$, the binary operation in ${\mathcal {I}}({\mathsf {C}})$ as $[a] + [b] = [a \Box b]$, and the additive identity of ${\mathcal {I}}({\mathsf {C}})$ as [e].

Definition 6.1.1

The Grothendieck group ${\mathcal {A}}({\mathsf {C}})$ of ${\mathsf {C}}$ is the group completion of the commutative monoid ${\mathcal {I}}({\mathsf {C}})$.

Explicitly, an element of ${\mathcal {A}}({\mathsf {C}})$ is of the form $[a] - [b]$ with addition coordinatewise, and $[a] = [c]$ iff $[a] + [d] = [c] + [d]$, for some element $[d] \in {\mathcal {I}}({\mathsf {C}})$. If ${\mathsf {C}}$ is additive and Krull-Schmidt (see Appendix), then each object in ${\mathsf {C}}$ is isomorphic to a unique direct sum of indecomposables. This means ${\mathcal {A}}({\mathsf {C}})$ is the free abelian group generated by the set of isomorphism classes of indecomposables. The Grothendieck group ${\mathcal {A}}({\mathsf {C}})$ has a natural translation-invariant partial ordering. We define $[a] \preceq [b]$ iff $[b]-[a] \in {\mathcal {I}}({\mathsf {C}})$. If $[a] \preceq [b]$, then $[a]+[c] \preceq [b]+[c]$ for any $[c] \in {\mathcal {A}}({\mathsf {C}})$. See Weibel (2013, page 72) for an introduction to translation-invariant partial orderings on Grothendieck groups.

Example 6.1.1

Every finite set is a finite disjoint union of the singleton set. We have

$$\begin{aligned} {\mathcal {A}}({\mathsf {FinSet}}) \cong {\mathbb Z}. \end{aligned}$$

Example 6.1.2

Every finite dimensional vector space is isomorphic to a finite direct sum of $\mathsf {k}$. We have

$$\begin{aligned} {\mathcal {A}}({\mathsf {Vec}}) \cong {\mathbb Z}. \end{aligned}$$

Example 6.1.3

An indecomposable of ${\mathsf {Ab}}$ is the free cyclic group or a primary cyclic group. We have

$$\begin{aligned} {\mathcal {A}}({\mathsf {Ab}}) \cong {\mathbb Z}\oplus \bigoplus _{(m,p)} {\mathbb Z}, \end{aligned}$$

over all primes p and positive integers m.

Example 6.1.4

An indecomposable of ${\mathsf {FinAb}}$ is a primary cyclic group. We have

$$\begin{aligned} {\mathcal {A}}({\mathsf {FinAb}}) \cong \bigoplus _{(m,p)} {\mathbb Z}\end{aligned}$$

over all primes p and positive integers m.

Example 6.1.5

An indecomposable of ${\mathsf {Rep}}({\mathbb N})$ is a Jordan block. We have

$$\begin{aligned} {\mathcal {A}}\left( {\mathsf {Rep}}({\mathbb N}) \right) \cong \bigoplus _{(m,\lambda )} {\mathbb Z}, \end{aligned}$$

over all positive integers m and elements $\lambda$ in the field $\mathsf {k}$.

6.2 Abelian category

Suppose ${\mathsf {C}}$ is an essentially small abelian category. We say two elements [b] and $[a] + [c]$ in ${\mathcal {A}}({\mathsf {C}})$ are related, written $[b] \sim [a] + [c]$, if there is a short exact sequence $0 \rightarrow a \rightarrow b \rightarrow c \rightarrow 0$.

Definition 6.2.1

The Grothendieck group ${\mathcal {B}}({\mathsf {C}})$ of ${\mathsf {C}}$ is the quotient group ${\mathcal {A}}({\mathsf {C}}) / \sim$. That is, ${\mathcal {B}}({\mathsf {C}})$ is the abelian group with one generator for each isomorphism classes [a] in ${\mathsf {C}}$ and one relation $[b] \sim [a] + [c]$ for each short exact sequence $0 \rightarrow a \rightarrow b \rightarrow c \rightarrow 0$.

Let $\pi : {\mathcal {A}}({\mathsf {C}}) \rightarrow {\mathcal {B}}({\mathsf {C}})$ be the quotient map. Note that $\pi \left( {\mathcal {I}}({\mathsf {C}}) \right)$ is a commutative monoid that generates ${\mathcal {B}}({\mathsf {C}})$. This allows us to define a translation-invariant partial ordering on ${\mathcal {B}}({\mathsf {C}})$ as follows. We define $[a] \preceq [b]$ iff $[b] - [a] \in \pi \left( {\mathcal {I}}({\mathsf {C}}) \right)$. If $[a] \preceq [b]$, then $[a] + [c] \preceq [b] + [c]$ for any $[c] \in {\mathcal {B}}({\mathsf {C}})$. The quotient map $\pi$ is a poset map.

Example 6.2.1

Every short exact sequence in ${\mathsf {Vec}}$ splits. We have

$$\begin{aligned} {\mathcal {B}}({\mathsf {Vec}}) \cong {\mathbb Z}. \end{aligned}$$

The quotient map $\pi : {\mathcal {A}}({\mathsf {Vec}}) \rightarrow {\mathcal {B}}({\mathsf {Vec}})$ is the identity.

Example 6.2.2

Every primary cyclic group ${{\mathbb Z}}/{p^m {\mathbb Z}}$ fits into a short exact sequence

$$\begin{aligned} 0 \rightarrow {\mathbb Z}\rightarrow {\mathbb Z}\rightarrow \frac{{\mathbb Z}}{p^m {\mathbb Z}} \rightarrow 0. \end{aligned}$$

This means $[{\mathbb Z}] \sim [{\mathbb Z}] + \left[ \frac{{\mathbb Z}}{p^m {\mathbb Z}} \right]$ and therefore $0 \sim \left[ \frac{{\mathbb Z}}{p^m {\mathbb Z}}\right]$. We have

$$\begin{aligned} {\mathcal {B}}({\mathsf {Ab}}) \cong {\mathbb Z}. \end{aligned}$$

The quotient map $\pi : {\mathcal {A}}({\mathsf {Ab}}) \rightarrow {\mathcal {B}}({\mathsf {Ab}})$ forgets the torsion part of every finitely generated abelian group.

Example 6.2.3

Every primary cyclic group ${{\mathbb Z}}/{p^m {\mathbb Z}}$ fits into a short exact sequence

$$\begin{aligned} 0 \rightarrow \frac{{\mathbb Z}}{p {\mathbb Z}} \rightarrow \frac{{\mathbb Z}}{p^m {\mathbb Z}} \rightarrow \frac{{\mathbb Z}}{p^{m-1} {\mathbb Z}} \rightarrow 0. \end{aligned}$$

This means

$$\begin{aligned} \left[ \frac{{\mathbb Z}}{p^m {\mathbb Z}} \right] \sim m \left[ \frac{{\mathbb Z}}{p {\mathbb Z}} \right] . \end{aligned}$$

Furthermore, $\frac{{\mathbb Z}}{p {\mathbb Z}}$ is a simple object so it can not be broken by a short exact sequence. We have

$$\begin{aligned} {\mathcal {B}}({\mathsf {FinAb}}) \cong \bigoplus _{p} {\mathbb Z}\end{aligned}$$

over all p prime. The quotient map $\pi : {\mathcal {A}}({\mathsf {FinAb}}) \rightarrow {\mathcal {B}}({\mathsf {FinAb}})$ takes each primary cyclic group $\left[ \frac{{\mathbb Z}}{p^m {\mathbb Z}} \right]$ to m in the p factor of ${\mathcal {B}}({\mathsf {FinAb}})$.

Example 6.2.4

Every Jordan block fits into a short exact sequence. For example,

$$\begin{aligned} 0 \rightarrow (\lambda ) \rightarrow \begin{pmatrix} \lambda & 1 & 0 \\ 0 & \lambda & 1 \\ 0 & 0 & \lambda \end{pmatrix} \rightarrow \begin{pmatrix} \lambda & 1 \\ 0 & \lambda \end{pmatrix} \rightarrow 0 \end{aligned}$$

and

$$\begin{aligned} 0 \rightarrow (\lambda ) \rightarrow \begin{pmatrix} \lambda & 1 \\ 0 & \lambda \end{pmatrix} \rightarrow (\lambda ) \rightarrow 0. \end{aligned}$$

This means

$$\begin{aligned} \begin{pmatrix} \lambda & 1 & 0 \\ 0 & \lambda & 1 \\ 0 & 0 & \lambda \end{pmatrix} \sim 3 (\lambda ). \end{aligned}$$

Furthermore, each one-dimensional Jordan block $(\lambda )$ is simple so it can not be broken by a short exact sequence. We have

$$\begin{aligned} {\mathcal {B}}\left( {\mathsf {Rep}}({\mathbb N}) \right) \cong \bigoplus _{\lambda \in \mathsf {k}} {\mathbb Z}. \end{aligned}$$

The quotient map $\pi : {\mathcal {A}}\left( {\mathsf {Rep}}({\mathbb N})\right) \rightarrow {\mathcal {B}}\left( {\mathsf {Rep}}({\mathbb N})\right)$ takes each Jordan block of dimension $m \in {\mathbb N}$ with eigenvalue $\lambda \in \mathsf {k}$ to m in the $\lambda$ factor of ${\mathcal {B}}\left( {\mathsf {Rep}}({\mathbb N}) \right)$.

7 Diagram of a module

Fix an essentially small symmetric monoidal category ${\mathsf {C}}$ with images. We now assign to each persistence module ${\mathsf {F}} \in {\mathsf {PMod}}({\mathsf {C}})$ a persistence diagram ${\mathsf {F}}_{\mathcal {A}}\in {\mathsf {PDgm}}\left( {\mathcal {A}}({\mathsf {C}}) \right)$. If ${\mathsf {C}}$ is also abelian, then we assign to ${\mathsf {F}}$ a second persistence diagram ${\mathsf {F}}_{\mathcal {B}}\in {\mathsf {PDgm}}\left( {\mathcal {B}}({\mathsf {C}}) \right)$.

We start by constructing a map

$$\begin{aligned} d {\mathsf {F}}_{\mathcal {I}}: {\mathsf {Dgm}}\rightarrow {\mathcal {I}}({\mathsf {C}}). \end{aligned}$$

Recall ${\mathcal {I}}({\mathsf {C}})$ is the commutative monoid of isomorphism classes of objects in ${\mathsf {C}}$. Suppose ${\mathsf {F}}$ is $S = \{ s_1< \cdots < s_n \}$-constructible. Then there is a $\delta > 0$ such that $s_{i-1} < s_i - \delta$, for each $1 < i \le n$. Choose a value $s' > s_n$. Define

$$\begin{aligned} d {\mathsf {F}}_{{\mathcal {I}}}(I) = {\left\{ \begin{array}{lll} \left[ \mathrm {im}\; {\mathsf {F}}(p< s_i - \delta ) \right] &\quad \text {for}\; I = [p, s_i) \\ \left[ \mathrm {im}\; {\mathsf {F}}(p< s') \right] &\quad \text {for}\; I = [p, \infty ) \\ \left[ \mathrm {im}\; {\mathsf {F}}(p < q) \right] &\quad\quad \text {for\, all \,other}\; I = [p,q). \end{array}\right. } \end{aligned}$$

Note that if ${\mathsf {F}}$ is also T-constructible, then $d {\mathsf {F}}_{\mathcal {I}}$ constructed using T is the same as $d {\mathsf {F}}_{\mathcal {I}}$ constructed using S. Now compose with the inclusion map ${\mathcal {I}}({\mathsf {C}}) \hookrightarrow {\mathcal {A}}({\mathsf {C}})$ and we have an S-constructible map

$$\begin{aligned} d{\mathsf {F}}_{\mathcal {A}}: {\mathsf {Dgm}}\rightarrow {\mathcal {A}}({\mathsf {C}}). \end{aligned}$$

Suppose ${\mathsf {C}}$ is abelian. Then by composing with the quotient map $\pi : {\mathcal {A}}({\mathsf {C}}) \rightarrow {\mathcal {B}}({\mathsf {C}})$, we have an S-constructible map

$$\begin{aligned} d{\mathsf {F}}_{\mathcal {B}}: {\mathsf {Dgm}}\rightarrow {\mathcal {B}}({\mathsf {C}}). \end{aligned}$$

Definition 7.1

The type ${\mathcal {A}}$ persistence diagram of ${\mathsf {F}}$ is the Möbius inversion

$$\begin{aligned} {\mathsf {F}}_{\mathcal {A}}: {\mathsf {Dgm}}\rightarrow {\mathcal {A}}({\mathsf {C}}) \end{aligned}$$

of $d{\mathsf {F}}_{\mathcal {A}}: {\mathsf {Dgm}}\rightarrow {\mathcal {A}}({\mathsf {C}})$.

Definition 7.2

The type ${\mathcal {B}}$ persistence diagram of ${\mathsf {F}}$ is the Möbius inversion

$$\begin{aligned} {\mathsf {F}}_{\mathcal {B}}: {\mathsf {Dgm}}\rightarrow {\mathcal {B}}({\mathsf {C}}) \end{aligned}$$

of $d{\mathsf {F}}_{\mathcal {B}}: {\mathsf {Dgm}}\rightarrow {\mathcal {B}}({\mathsf {C}})$.

Note that if ${\mathsf {F}}$ is S-constructible, then both ${\mathsf {F}}_{\mathcal {A}}$ and ${\mathsf {F}}_{\mathcal {B}}$ are S-finite persistence diagrams.

Proposition 7.1

(Positivity) For each $I \in {\mathsf {Dgm}}$, $[e] \preceq {\mathsf {F}}_{\mathcal {B}}(I)$.

Proof

Suppose ${\mathsf {F}}$ is $S = \{ s_1< \cdots < s_n \}$-constructible. We need only show the inequality for intervals I of the form $[s_i,s_j)$ and $[s_i, \infty )$. For all other I, ${\mathsf {F}}_{\mathcal {B}}(I) = [e]$.

Suppose $I = [s_i,s_j)$. Consider the following subdiagram of ${\mathsf {F}}$, for a sufficiently small $\delta > 0$:

Here we interpret $s_0$ as any value less than $s_1$ and $s_{n+1}$ as any value greater than $s_{n}$. By Eq. 1,

$$\begin{aligned} {\mathsf {F}}_{\mathcal {B}}\left( [s_i,s_j) \right) = d{\mathsf {F}}_{\mathcal {B}}\left( [s_i,s_{j}) \right) - d {\mathsf {F}}_{\mathcal {B}}\left( [s_i,s_{j+1}) \right) + d{\mathsf {F}}_{\mathcal {B}}\left( [s_{i-1},s_{j+1}) \right) - d{\mathsf {F}}_{\mathcal {B}}\left( [s_{i-1},s_j) \right) \end{aligned}$$

Observe

$$\begin{aligned} d{\mathsf {F}}_{\mathcal {B}}\left( [s_i,s_{j}) \right) -&d {\mathsf {F}}_{\mathcal {B}}\left( [s_i,s_{j+1}) \right) = \left[ \mathrm {im}\ {\mathsf {F}}(s_i< s_j -\delta ) \right] \\ -&\quad\left[ \frac{\mathrm {im}\ {\mathsf {F}}(s_i< s_j -\delta )}{\mathrm {im}\ {\mathsf {F}}(s_{i}< s_j -\delta ) \cap \ker \ {\mathsf {F}}(s_j -\delta< s_{j+1}-\delta )} \right] \\&= \left[ \mathrm {im}\ {\mathsf {F}}(s_i< s_j -\delta ) \right] - \left[ \mathrm {im}\ {\mathsf {F}}(s_i< s_j -\delta ) \right] \\ +&\quad\left[ \mathrm {im}\ {\mathsf {F}}(s_i< s_j -\delta ) \cap \ker \ {\mathsf {F}}(s_j -\delta< s_{j+1}-\delta ) \right] \\&= \left[ \mathrm {im}\ {\mathsf {F}}(s_i< s_j -\delta ) \cap \ker \ {\mathsf {F}}(s_j -\delta < s_{j+1}-\delta ) \right] . \end{aligned}$$

Here the intersection is interpreted as the pullback of the two subobjects. By a similar argument,

$$\begin{aligned}&d{\mathsf {F}}_{\mathcal {B}}\left( [s_{i-1},s_{j+1}) \right) - d{\mathsf {F}}_{\mathcal {B}}\left( [s_{i-1},s_j) \right) \\&\quad = -\left[ \mathrm {im}\ {\mathsf {F}}(s_{i-1}< s_j -\delta ) \cap \ker \ {\mathsf {F}}(s_j -\delta < s_{j+1}-\delta ) \right] ~. \end{aligned}$$

Note that

$$\begin{aligned} \mathrm {im}\ {\mathsf {F}}(s_{i-1}< s_j -\delta ) \cap \ker \ {\mathsf {F}}(s_j -\delta < s_{j+1}-\delta ) \end{aligned}$$

is a subobject of

$$\begin{aligned} \mathrm {im}\ {\mathsf {F}}(s_i< s_j -\delta ) \cap \ker \ {\mathsf {F}}(s_j -\delta < s_{j+1}-\delta ). \end{aligned}$$

Therefore

$$\begin{aligned} {\mathsf {F}}_{\mathcal {B}}\left( [s_i,s_j) \right) = \left[ \frac{\mathrm {im}\ {\mathsf {F}}(s_i< s_j -\delta ) \cap \ker \ {\mathsf {F}}(s_j -\delta< s_{j+1}-\delta )}{\mathrm {im}\ {\mathsf {F}}(s_{i-1}< s_j -\delta ) \cap \ker \ {\mathsf {F}}(s_j -\delta < s_{j+1}-\delta )} \right] \succeq [e]. \end{aligned}$$

Suppose $I = [s_i,\infty )$. Then by a similar argument using Eq. 2, we have

$$\begin{aligned} {\mathsf {F}}_{\mathcal {B}}\left( [s_i,\infty ) \right) = \left[ \frac{\mathrm {im}\ {\mathsf {F}}(s_i< s_{n+1})}{\mathrm {im}\ {\mathsf {F}}(s_{i-1} < s_{n+1} ) } \right] \succeq [e]. \end{aligned}$$

$\square$

Example 7.1

See Fig. 2 for an example of a persistence module in ${\mathsf {PMod}}({\mathsf {FinSet}})$ and its type ${\mathcal {A}}$ persistence diagram. Note that ${\mathsf {FinSet}}$ is not an abelian category so it does not have a type ${\mathcal {B}}$ persistence diagram.

Fig. 2

Here we have an example of a persistence module in ${\mathsf {PMod}}({\mathsf {FinSet}})$ and its type ${\mathcal {A}}$ persistence diagram. The type ${\mathcal {B}}$ persistence diagram is not defined

Example 7.2

See Fig. 3 for an example of a persistence module in ${\mathsf {PMod}}({\mathsf {Vec}})$ and its type ${\mathcal {A}}$ and type ${\mathcal {B}}$ persistence diagrams. Note that the quotient map $\pi : {\mathcal {A}}({\mathsf {Vec}}) \rightarrow {\mathcal {B}}({\mathsf {Vec}})$ is an isomorphism and therefore the two diagrams are the same.

Fig. 3

Here we have an example of a persistence module in ${\mathsf {PMod}}({\mathsf {Vec}})$ and its type ${\mathcal {A}}$ and ${\mathcal {B}}$ persistence diagrams

Example 7.3

See Fig. 4 for an example of a persistence module in ${\mathsf {PMod}}({\mathsf {Ab}})$ and its type ${\mathcal {A}}$ persistence diagram. Note that the quotient map $\pi : {\mathcal {A}}({\mathsf {C}}) \rightarrow {\mathcal {B}}({\mathsf {C}})$ forgets torsion and therefore the type ${\mathcal {B}}$ persistence diagram is, for this example, zero.

Fig. 4

Here we have an example of a persistence module in ${\mathsf {PMod}}({\mathsf {Ab}})$ and its type ${\mathcal {A}}$ persistence diagram. The map from 4 to 6 is the quotient of ${{\mathbb Z}}/{4{\mathbb Z}}$ by the image of the previous map. The type ${\mathcal {B}}$ persistence diagram is zero

Example 7.4

See Fig. 5 for an example of a persistence module in ${\mathsf {PMod}}({\mathsf {FinAb}})$ and its type ${\mathcal {A}}$ and type ${\mathcal {B}}$ persistence diagrams.

Fig. 5

Here we have an example of a persistence module in ${\mathsf {PMod}}({\mathsf {FinAb}})$ and its type ${\mathcal {A}}$ and type ${\mathcal {B}}$ persistence diagrams. This is the same example module as in Fig. 4

Example 7.5

See Fig. 6 for an example of a persistence module in ${\mathsf {PMod}}\left( {\mathsf {Rep}}({\mathbb N}) \right)$ and its type ${\mathcal {A}}$ and type ${\mathcal {B}}$ persistence diagrams.

Fig. 6

Here we have an example of a persistence module in ${\mathsf {PMod}}({\mathsf {Ab}})$ and its type ${\mathcal {A}}$ and type ${\mathcal {B}}$ persistence diagrams. The map from 4 to 6 is the quotient by the image of f

8 Stability

We now relate the interleaving distance between persistence modules to the erosion distance between their persistence diagrams.

For the first theorem, we make a simplifying assumption on ${\mathsf {C}}$ that makes it possible to chase diagrams. We assume that ${\mathsf {C}}$ is concrete and that its images are concrete. That is, ${\mathsf {C}}$ embeds into the category ${\mathsf {Set}}$ and an image of a morphism in ${\mathsf {C}}$ is the image of the corresponding set map. Note that all our examples satisfy this criteria. By the Freyd–Mitchell embedding theorem (Weibel 1995, page 28), an essentially small abelian category ${\mathsf {C}}$ embeds into the category of R-modules, for some ring R, and the image of a morphism in ${\mathsf {C}}$ is the image under the corresponding set map. Therefore, all essentially small abelian categories satisfy our criteria.

Theorem 8.1

(Semicontinuity) Let ${\mathsf {C}}$ be an essentially small symmetric monoidal category with images. Consider an $S = \{s_1< \cdots < s_n \}$-constructible ${\mathsf {F}} \in {\mathsf {PMod}}({\mathsf {C}})$ and let

$$\begin{aligned} \rho = \frac{1}{4} \min _{1< i \le n } (s_{i} - s_{i-1}). \end{aligned}$$

Let ${\mathsf {G}} \in {\mathsf {PMod}}({\mathsf {C}})$ be any persistence module such that $\varepsilon = \mathsf {d}_I({\mathsf {F}}, {\mathsf {G}}) < \rho$. For each interval $[s_i,s_j)$,

$$ {\mathsf {F}}_{\mathcal {A}}\left( [s_i, s_j ) \right)=\sum\limits_{{J \in {\rm Dgm}:\, [s_{{i - 1}} + \varepsilon ,s_{{j + 1}} - \varepsilon ) \supseteq J \supseteq [s_{i} + \varepsilon ,s_{j} - \varepsilon )\,\,{\text{and}}\,\, s_{{i - 1}} + \varepsilon ,s_{{j + 1}} - \varepsilon \notin J}} {{G}_{{\mathcal{A}}} (J)} $$

If $i = 1$, then we interpret $s_0$ as any value less than $s_1$ and if $j = n$, then we interpret $s_{n+1}$ as any value greater than $s_n$. Similarly, for each interval $[s_i, \infty )$,

$$ {\mathsf {F}}_{\mathcal {A}}\left( [s_i, \infty ) \right) = \sum\limits_{{J \in {\rm Dgm}:\,[s_{{i - 1}} + \varepsilon ,\infty ) \supseteq J \supseteq [s_{i} + \varepsilon ,\infty )\,\,{\text{and}}\,\,s_{{i - 1}} + \varepsilon ~ \notin J}} {{G}_{{\mathcal{A}}} (J)} $$

Proof

Let $\phi : {\mathsf {F}} \rightarrow \Delta ^\varepsilon ({\mathsf {G}})$ and $\psi : {\mathsf {G}} \rightarrow \Delta ^\varepsilon ({\mathsf {F}})$ be an $\varepsilon$-interleaving. Consider the following commutative diagram:

(3)

By S-constructibility of ${\mathsf {F}}$, the two vertical compositions are isomorphisms. By a diagram chase, we see that

$$\begin{aligned} d {\mathsf {F}}_{\mathcal {A}}\left( [s_i, s_j) \right) = d {\mathsf {G}}_{\mathcal {A}}\left( [s_i + \varepsilon , s_j - \varepsilon ) \right) . \end{aligned}$$

Thus

$$\begin{aligned} {\mathsf {F}}_{\mathcal {A}}\left( [s_i,s_{j}) \right)= & d {\mathsf {F}}_{\mathcal {A}}\left( [s_i,s_{j}) \right) - d {\mathsf {F}}_{\mathcal {A}}\left( [s_i,s_{j+1}) \right) \\&\quad+ d {\mathsf {F}}_{\mathcal {A}}\left( [s_{i-1},s_{j+1}) \right) - d {\mathsf {F}}_{\mathcal {A}}\left( [s_{i-1},s_{j}) \right) \\= & d {\mathsf {G}}_{\mathcal {A}}\left( [s_i + \varepsilon ,s_{j} - \varepsilon ) \right) - d {\mathsf {G}}_{\mathcal {A}}\left( [s_i + \varepsilon , s_{j+1}-\varepsilon ) \right) \\&\quad+ d {\mathsf {G}}_{\mathcal {A}}\left( [s_{i-1}+\varepsilon ,s_{j+1} -\varepsilon ) \right) - d {\mathsf {G}}_{\mathcal {A}}\left( [s_{i-1} + \varepsilon ,s_{j} - \varepsilon ) \right) \\= &\sum\limits_{{J \in {\rm Dgm}:\,[s_{{i - 1}} + \varepsilon ,s_{{j + 1}} - \varepsilon ) \supseteq J \supseteq [s_{i} + \varepsilon ,s_{j} - \varepsilon )\,\,{\text{and}}\,\,s_{{i - 1}} + \varepsilon ,s_{{j + 1}} - \varepsilon \notin J}} {{G}_{{\mathcal{A}}} (J)}. \end{aligned}$$

The second claim for $[s_i,\infty )$ follows by a similar argument. $\square$

Semicontinuity is saying there is an open neighborhood of ${\mathsf {F}}$ in the metric space of persistence modules such that for each ${\mathsf {G}}$ in this open neighborhood, ${\mathsf {F}}_{\mathcal {A}}$ lives on in ${\mathsf {G}}_{\mathcal {A}}$. However, semicontinuity is unsatisfying in two interesting ways. First, the $\varepsilon$ must be smaller than $\rho$ which is half the injectivity radius of S in ${\mathbb R}$. Second, the claim is assymetric. The fundamental limitation here is that not all short exact sequences in ${\mathsf {C}}$ split.

Theorem 8.2

(Continuity) Let ${\mathsf {C}}$ be an essentially small, concrete, abelian category. For any two persistence modules ${\mathsf {F}}, {\mathsf {G}} \in {\mathsf {PMod}}({\mathsf {C}})$, we have

$$\begin{aligned} \mathsf {d}_E\left( {\mathsf {F}}_{\mathcal {B}}, {\mathsf {G}}_{\mathcal {B}}\right) \le \mathsf {d}_I({\mathsf {F}}, {\mathsf {G}}). \end{aligned}$$

Proof

Let $\varepsilon = \mathsf {d}_I({\mathsf {F}}, {\mathsf {G}})$. For each $I \in {\mathsf {Dgm}}$ such that ${\mathsf {F}}_{\mathcal {A}}(I) \ne [e]$, we must show

$$\begin{aligned} d {\mathsf {F}}_{\mathcal {A}}\circ {\mathsf {Grow}}^\varepsilon (I) \preceq d{\mathsf {G}}_{\mathcal {A}}(I) \end{aligned}$$

and for each $I \in {\mathsf {Dgm}}$ such that ${\mathsf {G}}_{\mathcal {B}}(I) \ne [e]$, we must show

$$\begin{aligned} d {\mathsf {G}}_{\mathcal {A}}\circ {\mathsf {Grow}}^\varepsilon (I) \preceq d{\mathsf {F}}_{\mathcal {A}}(I). \end{aligned}$$

We will prove the first inequality and the second inequality follows by simply interchanging the roles of ${\mathsf {F}}$ and ${\mathsf {G}}$ in the proof.

Suppose ${\mathsf {F}}$ is $S = \{s_1< \cdots < s_n \}$-constructible. By constructibility, it is sufficient to show the first inequality for I of the form $[s_i+\varepsilon , s_j-\varepsilon )$ and $[s_i+\varepsilon , \infty )$. Suppose $I = [s_i+\varepsilon ,s_j-\varepsilon )$. Let $\phi : {\mathsf {F}} \rightarrow \Delta ^\varepsilon ({\mathsf {G}})$ and $\psi : {\mathsf {G}} \rightarrow \Delta ^\varepsilon ({\mathsf {F}})$ be an $\varepsilon$-interleaving. Consider the following commutative diagram:

(4)

By commutativity,

$$\begin{aligned} \mathrm {im}\ {\mathsf {F}}(s_i< s_j - \delta ) \cong \frac{\mathrm {im}\ {\mathsf {G}}(s_i + \varepsilon< s_j - \varepsilon - \delta )}{ \mathrm {im}\ {\mathsf {G}}(s_i + \varepsilon < s_j - \varepsilon - \delta ) \cap \ker \; \psi (s_j-\varepsilon -\delta )}. \end{aligned}$$

Therefore

$$\begin{aligned} d {\mathsf {F}}_{\mathcal {B}}\left( [ s_i< s_j ) \right)&= d {\mathsf {G}}(s_i + \varepsilon< s_j - \varepsilon ) - [ \ker \ \psi (s_j-\varepsilon -\delta )] \\& \preceq d {\mathsf {G}}_{\mathcal {B}}\left( [s_i +\varepsilon < s_j - \varepsilon ) \right) \end{aligned}$$

This proves the claim. Suppose $I = [s_i,\infty )$. Then

$$\begin{aligned} d {\mathsf {F}}_{\mathcal {B}}\left( [ s_i< \infty ) \right) \preceq d {\mathsf {G}}_{\mathcal {B}}\left( [s_i +\varepsilon < \infty ) \right) . \end{aligned}$$

by a similar commutative diagram. $\square$

9 Concluding remarks

Torsion in data We hope our theory will allow for the study of torsion in data. For example, let $P \subset {\mathbb R}^n$ be a finite set of points. Let $f : {\mathbb R}^n \rightarrow {\mathbb R}$ be a function dependent on P, for example $f(x) = \min _{p \in P} || x - p ||_2$. Apply homology with integer coefficients to the sublevel set filtration induced by f and we have a constructible persistence module ${\mathsf {F}} \in {\mathsf {PMod}}({\mathsf {Ab}})$. Its type ${\mathcal {A}}$ persistence diagram is measuring torsion in data and semicontinuity applies. If continuity is required, then we may look at the type ${\mathcal {B}}$ persistence diagram of ${\mathsf {F}}$. However, the type ${\mathcal {B}}$ persistence diagram forgets all torsion. Perhaps a better approach is to apply homology with coefficients in a finite abelian group. Then the resulting persistence module is in ${\mathsf {PMod}}({\mathsf {FinAb}})$ and its type ${\mathcal {B}}$ diagram encodes simple torsion.

Time series The flexibility we offer in choosing ${\mathsf {C}}$ should allow for the encoding of more structure in data. Consider time series data. Suppose $P = \{ p_1, \ldots , p_{k} \}$ is a finite sequence of points in ${\mathbb R}^n$. There is more to P than its shape. The forward shift $p_i \rightarrow p_{i+1}$ along the sequence should induce dynamics on the shape of P at each scale. The algebraic object of study is not clear, but it will certainly have more structure than a vector space or an abelian group.

Non-constructible modules Suppose we are given an infinite set of points $P \subset {\mathbb R}^n$. Then the resulting persistence module, as constructed above, is not constructible. Is there a persistence diagram for a non-constructible persistence module?

This question is addressed by Chazal et al. (2016) for ${\mathsf {C}}= {\mathsf {Vec}}$. They define a persistence diagram for a non-constructible persistence module as a rectangular measure $\mu : {\mathsf {Rect}}\rightarrow {\mathbb N}$, where ${\mathsf {Rect}}$ is the poset of all pairs $J \supset I$ in ${\mathsf {Dgm}}$, satisfying a certain additivity condition. Our type ${\mathcal {B}}$ diagram should generalize to a rectangular measure. For ${\mathsf {C}}$ abelian, we may use an argument similar to the one in the proof of Proposition 7.1 to assign an element of ${\mathcal {B}}({\mathsf {C}})$ to each $J \supset I$ without making use of constructibility. Is this assignment a rectangular measure?

Appendix: Krull-Schmidt

We now provide a compact treatment of Krull-Schmidt categories. The following ideas are classical and may be found in many books, for example Anderson and Fuller (1992).

A category ${\mathsf {C}}$ is additive if all its hom-sets are abelian, composition is bilinear, and finite products and finite coproducts are the same. The (co)product of the empty set is the zero object of ${\mathsf {C}}$. Suppose ${\mathsf {C}}$ is additive.

Definition A.1

A non-zero object $a \in {\mathsf {C}}$ is indecomposable if it is not the direct sum of two non-zero objects.

Definition A.2

An additive category ${\mathsf {C}}$ is Krull-Schmidt if each object $a \in {\mathsf {C}}$ is isomorphic to a finite direct sum $a \cong a_1 \oplus a_2 \oplus \cdots \oplus a_n$ and each ring of endomorphisms ${\mathsf {End}}_{\mathsf {C}}(a_i)$ is local. That is, $0 \ne 1$ and if $f_1 + f_2 = 1$, then $f_1$ or $f_2$ is invertible.

Suppose ${\mathsf {C}}$ is Krull-Schmidt.

Proposition 9.1

An object $a \in {\mathsf {C}}$ is indecomposable iff its endomorphism ring ${\mathsf {End}}(a)$ is local.

Proof

Suppose $a \in {\mathsf {C}}$ is decomposable. That is, there is an isomorphism $i :a \rightarrow a_1 \oplus a_2$ such that $a_1,a_2 \ne 0$. Define $\pi _1 : a_1 \oplus a_2 \rightarrow a_1 \oplus a_2$ as the endomorphism that sends the first factor to zero and $\pi _2 : a_1 \oplus a_2 \rightarrow a_1 \oplus a_2$ as the endomorphism that sends the second factor to zero. Then the two maps $\rho _1, \rho _2 : a \rightarrow a$, where $\rho _1 = i^{-1} \circ \pi _1 \circ i$ and $\rho _2 = i^{-1} \circ \pi _2 \circ i$, are both non-isomorphisms in ${\mathsf {End}}_{\mathsf {C}}(a)$. However, $\rho _0 + \rho _1 :a \rightarrow a$ is an isomorphism. We have a contradiction of locality.

Suppose $a \in {\mathsf {C}}$ is indecomposable. Then, by definition of a Krull-Schmidt category, ${\mathsf {End}}_{\mathsf {C}}(a)$ is a local ring. $\square$

Proposition 9.2

Each object $a \in {\mathsf {C}}$ is isomorphic to a finite direct sum of indecomposables.

Proof

By definition of a Krull-Schmidt category, $a \cong a_1 \oplus a_2 \oplus \cdots \oplus a_n$ where each ${\mathsf {End}}_{\mathsf {C}}(a_i)$ is a local ring. By Proposition 9.1, each $a_i$ is indecomposable. $\square$

Theorem 9.1

(Krull-Schmidt) Suppose an object $c \in {\mathsf {C}}$ is isomorphic to $a_1 \oplus a_2 \oplus \cdots \oplus a_m$ and $b_1 \oplus b_2 \oplus \cdots \oplus b_n$, where each $a_i$ and $b_j$ are indecomposable. Then $m = n$, and there is a permutation $p: [m] \rightarrow [n]$ such that $a_i \cong b_{p(i)}$.

Proof

By definition of an additive category, we have canonical projections $\pi _i : \oplus _i a_i \rightarrow a_i$ and $\rho _j : \oplus _j b_j \rightarrow b_j$ and canonical inclusions $\mu _i : a_i \rightarrow \oplus _i a_i$ and $\nu _j : b_j \rightarrow \oplus _j b_j$. Furthermore $\mu _j \circ \pi _i$ and $\nu _j \circ \rho _i$ are the identity on $a_i$ and $b_i$, respectively, iff $i = j$. Let $f : a_1 \oplus a_2 \oplus \cdots \oplus a_m \rightarrow b_1 \oplus b_2 \oplus \cdots \oplus b_n$ be an isomorphism.

Define $h_j : a_1 \rightarrow a_1$ as $h_j = \pi _1 \circ f^{-1} \circ \nu _j \circ \rho _j \circ f \circ \mu _1$. Let $h = \sum _j h_j: a_1 \rightarrow a_1$. Observe h is an isomorphism. By locality, there is an index j such that $h_j$ is an isomorphism. This means $a_1 \cong b_j$ and we specify $p(1) = j$. Quotient by $a_1$ and $b_j$. Repeat. $\square$