A Theory of Sub-Barcodes

Let $\mathrm{rk}m$ denote the rank of a linear map $m$ defined as the dimension of its image, $\mathrm{im}m$. The rank invariant ${\mathrm{rank}}_M$ of a persistence module $M:ℝ\to \mathrm{𝐯𝐞𝐜}$ is a function from ordered pairs in $ℝ$ to the natural numbers defined as ${\mathrm{rank}}_M(s\le t):=\mathrm{rk}{M}_{s\le t}$. It is straightforward to extend this invariant to homomorphisms $F:M\to N$ by letting ${\mathrm{rank}}_F(s\le t):=\mathrm{rk}(F_t\circ M_{s\le t})$. In the following, we consider the rank invariant for a persistence module $M$ to be the rank invariant of its identity homomorphism, i.e., ${\mathrm{rank}}_M:={\mathrm{rank}}_{{\mathrm{𝟣}}_M}$.

A basic fact from linear algebra is that, if a linear map $g$ factors through a second linear map $f$, then $\mathrm{rk}(g)\le \mathrm{rk}(f)$. It follows immediately that, if there is a factorization $F\to G$ of persistence module homomorphisms, then for all $s\le t$,

This puts a partial order on rank invariants that we call the sub-rank relation and denote by ${\mathrm{rank}}_G\le {\mathrm{rank}}_F$.

In light of the sub-barcode theorem, the rank invariant is the same type of invariant as sub-barcodes. It puts a partial order on morphisms induced by factorizations. However, although the barcode can be constructed from the rank invariant, the natural ordering of rank invariants is a weaker invariant than sub-barcodes as expressed in the following.

Although not expressed in these terms, Bauer and Lesnick’s theory of induced matchings [3] shows that sub-barcode matchings arise from certain homomorphisms. The induced matchings in that work are matchings between the bars that do not (necessarily) satisfy the inclusion requirement of a sub-barcode matching. They showed that for any homomorphism $F:M\to N$, there is a partial bijective function (a matching) between the bars with the property that every bar of $\mathrm{𝖡𝖺𝗋}(F)$ is the intersection of the intervals of the matched bars from $\mathrm{𝖡𝖺𝗋}(M)$ to $\mathrm{𝖡𝖺𝗋}(N)$. These are constructed from the pair of canonical (functorial) matchings $\mathrm{𝖡𝖺𝗋}(M)\to \mathrm{𝖡𝖺𝗋}(F)\to \mathrm{𝖡𝖺𝗋}(N)$ induced by the epi-mono factorization of $F$ through its image. Translated into the vocabulary of sub-barcodes, this result implies that $\mathrm{𝖡𝖺𝗋}(F)⊑\mathrm{𝖡𝖺𝗋}(M)$ and $\mathrm{𝖡𝖺𝗋}(F)⊑\mathrm{𝖡𝖺𝗋}(N)$.

More generally, if $F$ is a monomorphism (all maps $F_t$ are injective), then $\mathrm{𝖡𝖺𝗋}(M)⊑\mathrm{𝖡𝖺𝗋}(N)$. This is because the induced matching of a monomorphism matches every bar, in addition to the property that, if $[a,b]$ is matched to $[c,d]$, then $a\ge c$ and $b=d$; thus, a submodule relation between persistence modules implies a sub-barcode relation between the barcodes.

If $F$ is an epimorphism (all maps $F_t$ are surjective), then the induced matching is surjective, and if $[a,b]$ is matched to $[c,d]$, then $a=c$ and $d\le b$. So, reversing this induced matching, we get $\mathrm{𝖡𝖺𝗋}(N)⊑\mathrm{𝖡𝖺𝗋}(M)$. We use these matchings in the proof of the Sub-Barcode Theorem below.

The most direct way to use a Delaunay triangulation to estimate the persistence diagram of a set of points is to extend the function from the vertex set to the simplices, setting the value at the simplex be the maximum value at its vertices. This corresponds to the piecewise linear extension of the function to the geometric realization of the complex (see Section 2.5, Morozov [20]). Unfortunately, this can fail badly in the absence of strong sampling guarantees; Figure 5 shows an example where the piecewise linear extension introduces spurious features. Thus, the problem with some samples is not only that we can miss features, but that we may hallucinate them as well.

The key to using a discretization is to use an image filtration (see Cohen-Steiner et al. [12], Bauer [4]) capturing both an upper and lower bound. The following theorem states that we can compute a sub-barcode for any Lipschitz function by filtering the Delaunay triangulation by upper and lower bounds given on the input values and the radius of the Voronoi cells.

We have assumed thus far that we have access to function values at all points in the sample. This resembles a supervised learning problem. If instead we only have function values at a subset $P\subset S$, we can still use the points of $S$ to improve our approximation. We call this semi-supervised TDA.

The most common guarantees in PH are derived from interleavings, and thus yield bottleneck distance bounds on the resulting barcodes. In this section, we combine those results with the Lipschitz extension sub-barcode and the Delaunay filtration above to get a guaranteed approximation. Throughout, we assume that $S$ is a sample of $X$, and that we only have function values $f_P:P\to ℝ$ for $P\subset S$. The algorithm extends ${\check{f}}_P$ and ${\widehat{f}}_P$ to the points of $S$ and then use the Delaunay filtration from the previous subsection.

In the following, we say that $S$ is an $\epsilon$-sample of $X$ if every point of $X$ is within $\epsilon$ of a point in $S$. Equivalently, the radius of every Voronoi cell ${\mathrm{Vor}}_S(s)$ is at most $\epsilon$.

In general, we would like to have tight approximations to the sub-barcode of Lipschitz extensions without requiring any sampling assumptions. One way to get a better bound is to manually add points to reduce the radii of the cells. Another approach would be to consider the barycentric subdivision. This makes sense because it can be understood as assigning function values to Delaunay simplices individually rather than inducing the values from the function on the vertices. In this section, we show how to define such constructions in a way that applies to a much more general class of functions.

For each sample $s\in S$, knowing the value of $f(s)$ implies an upper bound and a lower bound on $f$. Thus far, these bounds came from the assumption that $f$ is Lipschitz. Similar upper and lower bounds can be defined for other classes of functions. We only assume that these bounds are distance monotone. That is, the upper bound ${\check{f}}_s$ for a point $s$ satisfies the condition that if $\mathrm{d}(x,s)\le \mathrm{d}(y,s)$, then ${\check{f}}_s(x)\le {\check{f}}_s(y)$. For the lower bound ${\widehat{f}}_s$ at $s$ values decrease with distance, i.e., if $\mathrm{d}(x,s)\le \mathrm{d}(y,s)$, then ${\widehat{f}}_s(x)\ge {\widehat{f}}_s(y)$. We call $\{{\check{f}}_s\}$ and $\{{\widehat{f}}_s\}$ a family of pointwise distance monotone bounds. As before, we let ${\check{f}}_S(x):={\min }_{s\in S}{\check{f}}_s(x)$ and ${\widehat{f}}_S(x):={\max }_{s\in S}{\widehat{f}}_s(x)$.

Although the term baryentric subdivision implies that subdivision happen at the barycenters of the cells, we define this operation instead as a combinatorial operation on simplicial complexes. For any simplicial complex $K$, we define $\mathrm{𝖻𝖺𝗋𝗒}K$ to be the simplicial complex with a vertex for each simplex in $K$ and a simplex for each ordered subset of simplices (the ordering is by inclusion). For any function $g:K\to ℝ$, we can extend it to a filtration $G$ on $\mathrm{𝖻𝖺𝗋𝗒}K$, as ${\sigma }_0\hookrightarrow \mathrm{\cdots }\hookrightarrow {\sigma }_k$ is in $G(t)$ if and only if $g({\sigma }_i)\le t$ for all $i\in \{0,\mathrm{\dots },k\}$. Proof of the following theorem may be found in the full version [10].

Given a barcode $B$, an $\epsilon$-smoothing is a new barcode defined by eliminating bars of length at most $2\epsilon$, and replacing all other bars $[b,d]$ with a $[b+\epsilon ,d-\epsilon ]$; that is, we trim $\epsilon$ from the beginning and the end of each bar. The idea of a smoothed barcode naturally arises in the literature on the stability of persistence modules [7, 5, 18]. It is clear from the definition that the smoothed barcode is a sub-barcode of the original. This relationship can be expressed clearly as arising from a factorization as follows.

Let ${\delta }_{-}$ and ${\delta }_{+}$ be order-preserving maps $ℝ\to ℝ$ with the property that, for all $t\in ℝ$, we have ${\delta }_{-}(t)\le t\le {\delta }_{+}(t)$. Order preserving maps between posets are functors, so the pointwise order relations on ${\delta }_{-}$ and ${\delta }_{+}$ correspond to natural transformations

So, for any persistence module $M:ℝ\to \mathrm{𝐯𝐞𝐜}$, composition with $M$ yields the following factorization.

Letting $\epsilon ={\epsilon }_1\circ {\epsilon }_0$, we can view $M\epsilon$ (or equivalently, its image) as the smoothed persistence module. The factorization induces the sub-barcode matching in the obvious way:

From this perspective, an interleaving of persistence modules may be viewed as a pair of compatible factorizations rather than a pair of compatible (shifted) homomorphisms. In fact, the pair $({\delta }_{-},{\delta }_{+})$ corresponds to an adjunction with counit ${\epsilon }_0$ and unit ${\epsilon }_1$ (see [14]).

Within the literature, there are several different categorifications of persistence barcodes (or equivalently persistence diagrams). Here, we identify a natural way to define a category of barcodes that plays nicely with our treatment of sub-barcodes.

First, recall that unlike much of the prior work, we do not regard barcodes as multisets. Instead, we define a barcode to be a function from a set to the intervals. In computer programming terms, we have an “is a” versus “has a” distinction; in the multiset view, each bar is an interval. In our view, each bar has an interval.

A standard categorical approach to construct a category ${\int }_{𝐂}F$ from a (pseudo)functor $𝐂\to \mathrm{𝐂𝐚𝐭}$ is the Grothendieck construction. Let $F:{𝐂}^{\mathrm{𝗈𝗉}}\to \mathrm{𝐂𝐚𝐭}$ be a functor from a category $𝐂$ to the category $\mathrm{𝐂𝐚𝐭}$ of (small) categories. For the purposes of this work, the (covariant) Grothendieck construction yields a category ${\int }_{𝐂}F$ with objects given by pairs $(C,x)$ for each $C\in 𝐂$ and $x\in F(C)$, and arrows $(f,h):(C,x)\to (C^{\prime },x^{\prime })$ for each pair of arrows $f:C\to C^{\prime }$ in $𝐂$ and $h:x\to F\left[f\right](x^{\prime })$ in $F(C)$.

Let $[-,ℐ]:\mathrm{𝐒𝐞𝐭}\to \mathrm{𝐂𝐚𝐭}$ be the (pseudo)functor that takes a set $X$ and returns the category ${ℐ}^X=[X,ℐ]$ of functors $X\to ℐ$. Then the category $\mathrm{𝐁𝐚𝐫}$ of barcodes described in Section 3 is a contravariant Grothendieck construction

The objects of $\mathrm{𝐁𝐚𝐫}$ are pairs $(\underset{¯}{B},B:\underset{¯}{B}\to ℐ)$ – i.e. barcodes – and a morphism of $\mathrm{𝐁𝐚𝐫}$ $(\underset{¯}{A},A)\to (\underset{¯}{B},B)$ is a function $\varphi :\underset{¯}{A}\to \underset{¯}{B}$ such that for all $\alpha \in \underset{¯}{A}$, we have that $A(\alpha )\subseteq B(\varphi (\alpha ))$. To see this as a Grothendieck construction, it suffices to observe that the barwise inclusion ordering is a natural transformation $A\Rightarrow B\varphi$ in $[\underset{¯}{A},ℐ]$.

The condition on morphisms ensures that a bar $\alpha$ can only map to a bar $\beta$ when $A(\alpha )\subseteq B(\beta )$. Thus, a injective morphism is exactly a sub-barcode matching. These injective morphisms are the monomorphsisms in this category and thus sub-barcodes are subobjects in this category.

The rank functor was previously constructed directly from a persistence module, or more generally, a factorization of persistence module homomorphisms. In this section, we show how the rank functor can also be constructed from a barcode. This is already well-known; the novelty here is that we show how the rank functor can be factored through the category of barcodes. This gives the more abstract proof that sub-barcodes are more discriminating than ranks.

For any category $𝐂$, there is a functor $L:{\int }_{\mathrm{𝐒𝐞𝐭}}[-,𝐂]\to [{𝐂}^{\mathrm{𝗈𝗉}},\mathrm{𝐒𝐞𝐭}]$ given for $A:\underset{¯}{A}\to 𝐂$ by

The morphisms $L(A)(c\to c^{\prime })$ are inclusions $L(A)(c^{\prime })\subseteq L(A)(c)$. For $(f,\epsilon ):A\to B$ in ${\int }_{\mathrm{𝐒𝐞𝐭}}[-,𝐂]$, it is easy to check that $f$ gives a natural transformation $LA\Rightarrow LB$.

For the special case where $𝐂=ℐ$, this is a functor from barcodes to presheaves of intervals. The intuitive meaning is that, for a barcode $B$, the presheaf $LB$ maps an interval $J$ to the set of bars in $B$ that contain all of $J$. All morphisms in the image of $L$ are inclusions, and so, for $J\supseteq I$, we have $LB(J)\subseteq LB(I)$ and thus $|LB(J)|\le |LB(I)|$. Here the vertical bars indicate set cardinality which is a functor $\mathrm{𝖼𝖺𝗋𝖽}$ from the poset of finite sets with inclusions to the poset $\mathbb{N}$. Thus, we have a functor $\mathrm{𝖼𝖺𝗋𝖽}\circ L:\mathrm{𝐁𝐚𝐫}\to {\mathrm{𝐒𝐞𝐭}}^{{ℐ}^{\mathrm{𝗈𝗉}}}$.

It is now an easy exercise to show that $\mathrm{rank}=\mathrm{𝖼𝖺𝗋𝖽}\circ L\circ \mathrm{𝖡𝖺𝗋}$. All morphisms in the functor category $[{ℐ}^{op},\mathbb{N}]={\mathbb{N}}^{{ℐ}^{\mathrm{𝗈𝗉}}}$ are monomorphisms, so clearly a sub-barcode relation (a monomorphism of barcodes) yields a subrank relation (a monomorphism of rank invariants). The other direction doesn’t hold. The most natural way to define a barcode from the rank invariant does not give a functor to barcodes. The example is given in the proof of Theorem 6.