# Parameterized Vietoris-Rips Filtrations via Covers ††thanks: BJN was
supported by the Defense Advanced Research Projects Agency (DARPA) under
Agreement No. HR00112190040

Bradley J. Nelson  Bradley J. Nelson
Department of Statistics
Committee on Computational and Applied Mathematics
University of Chicago
Chicago  IL 60637
<EMAIL_ADDRESS>

(Received: date / Accepted: date)

###### Abstract

A challenge in computational topology is to deal with large filtered geometric
complexes built from point cloud data such as Vietoris-Rips filtrations. This
has led to the development of schemes for parallel computation and compression
which restrict simplices to lie in open sets in a cover of the data. We extend
the method of acyclic carriers to the setting of persistent homology to give
detailed bounds on the relationship between Vietoris-Rips filtrations
restricted to covers and the full construction. We show how these complexes
can be used to study data over a base space and use our results to guide the
selection of covers of data. We demonstrate these techniques on a variety of
covers, and show the utility of this construction in investigating higher-
order homology of a model of high-dimensional image patches.

##  1 Introduction

A common task in computational topology is to construct a (filtered) geometric
complex from a set of points $\mathbf{X}$, possibly sampled from some larger
space $X\supseteq\mathbf{X}$, using a pairwise dissimilarity
$d:\mathbf{X}\times\mathbf{X}\to\mathbb{R}_{+}$ between points. Two major
applications include statistical recovery of homological features of the
larger space $X$, [6, 4] perhaps in the process of exploratory data analysis,
and generating features for machine learning tasks [3, 21]. One limitation of
geometric constructions is that they can produce very large combinatorial
representations of a space as simplicial complexes, typically growing in the
number of points $n$ and maximal simplex dimension $q$ as $O(n^{q+1})$ total
simplices. Another limitation is that one must consider the choice of
dissimilarity $d$. In general, a dissimilarity may be trusted locally (for
small values), but not globally (for large values) – a key motivation for
dimension reduction techniques such as locally linear embeddings [30] and
ISOMAP [34].

For example, if the points $\mathbf{X}$ are sampled near a low dimensional
manifold embedded in Euclidean space, we may choose the metric $d$ to either
be the Euclidean distance of the ambient space, or the intrinsic distance of
the manifold, perhaps approximated from the sampling. At small distances, the
choice of metric will not appear to matter much, but at large distances
differences between the two metrics will become much more apparent. These two
factors combine to make the calculation of persistent homology from samples
difficult even in dimensions as small as 2 or 3 – either a large number of
samples are required to cover a space without growing distance too large, or
we must use large non-local distances which are not trusted.

One way to make calculation of higher-dimensional homology of sampled point
clouds tractable is to incorporate the additional structure of a map $f:X\to
B$. In this setting, the space $X$ is said to be parameterized by $B$, which
is called the base space. A variety of tools in continuous topology have
developed, both in the context of homotopy theory which studies notions such
as base-space preserving maps[23] and fibrations [31], and in the context of
homology where the Leray and Leray-Serre spectral sequences can be used to
ease calculation [24]. Many ideas and results in the continuous setting rely
on an analysis of fibers of the map, $f^{-1}(b)$, which poses a difficulty in
the discrete setting where fibers will generally be empty. In this paper, we
consider an extension of parameterized spaces to the setting of filtered
complexes based not on fibers but on inverse images of sets $f^{-1}(U)$.
Generally, the map $f$ is not needed for the construction - we can simply take
any cover of the data (which coincides with $B=X$ and $f$ as the identity):

######  Definition 1.1.

A system of complexes over a cover $\mathfrak{U}$ is a collection of
(filtered) cell complexes $\\{\mathcal{X}^{T}(U)\\}_{U\in\mathfrak{U}}$ where
$\mathcal{X}^{T}(U)$ has $U$ as its 0-skeleton, and the restriction of
complexes to intersections of sets in the cover are compatible.

$\mathcal{X}^{T}(U_{i})|_{\cap U_{k}}=\mathcal{X}^{T}(U_{j})|_{\cap U_{k}}$
(1)

for all $U_{i},U_{j}\in\\{U_{k}\\}\subseteq\mathfrak{U}$.

######  Definition 1.2.

A cover complex $\mathcal{X}^{T}(\mathfrak{U})$ is the union of complexes in a
system of complexes.

$\mathcal{X}^{T}(\mathfrak{U})=\bigcup_{U\in\mathfrak{U}}\mathcal{X}^{T}(U)$
(2)

This definition of cover complex coincides with a similar definition which
appeared in an early pre-print of [18], but which was abandoned in subsequent
versions. The goal of [18], as well as associated literature [12, 9] is to
understand when a filtered nerve can effectively be used to approximate a
larger computation, a question which we will address for cover complexes in
section 3.3. In contrast, we will seek to use the actual cover complex in
computations in situations where the complex restricted to each set is not
necessarily close to acylic, which we will investigate in section 3.1 and
section 4.1. This has previously been investigated by Yoon [35] in the
calculation of persistent homology of Vietoris-Rips filtrations at small
scales in the setting where the nerve of the cover is contractible. These
complexes also contain similarities to the multiscale mapper construction
[15], which also uses inverse images of sets in covers, but applies this to
simplicial complexes generated using the mapper algorithm [33] which contracts
connected components in the inverse image of sets. We shall be interested in
higher-dimensional homology as well.

###  1.1 Geometric Complexes

In applied topology, there are a variety of constructions which allow for the
construction of simplicial complexes from a data set $\mathbf{X}$. These
complexes allow for the approximation of a larger space from which the data
was sampled. Common examples include the Vietoris-Rips complex, Čech complex,
Witness complex, and others – see [13] for a review of a variety of
constructions.

In this paper, we will focus on Vietoris-Rips complexes which are attractive
from a computational point of view because they allow for an easy
combinatorial description in arbitrary dimensions (as opposed to Čech or
$\alpha$-complexes), and do not require selection of landmarks as in Witness
complexes. The Vietoris-Rips complex uses a dissimilarity
$d:\mathbf{X}\times\mathbf{X}\to\mathbb{R}$ to determine whether simplices
should be included in the complex.

######  Definition 1.3.

Let $(\mathbf{X},d)$ be a dissimilarity space. We extend the dissimilarity to
tuples of points $x_{0},\dots,x_{k}\subseteq\mathbf{X}$ as

$d(x_{0},\dots,x_{k})=\max_{0\leq i<j\leq k}d(x_{i},x_{j})$ (3)

with $d(x)=d(x,x)=0$.

######  Definition 1.4.

Let $(\mathbf{X},d)$ be a dissimilarity space. The Vetoris-Rips complex
$\mathcal{R}(\mathbf{X};r)$ is the union of simplices

$\mathcal{R}(\mathbf{X};r)=\\{(x_{0},\dots,x_{k})\mid
x_{0},\dots,x_{k}\in\mathbf{X},d(x_{0},\dots,x_{k})\leq r\\}.$ (4)

We can use the same notation to refer to a filtration by letting the $r$
parameter vary.

Because the Rips filtration is a flag filtration, the simplex
$(x_{0},\dots,x_{k})$ appears at parameter $d(x_{0},\dots,x_{k})$. We can
restrict simplicies of this full complex to sets in a cover to obtain an
equivalent notion of cover complex:

######  Definition 1.5.

Let $\mathcal{X}^{T}$ be a filtered cell complex over a poset $T$, with vertex
set $\mathcal{X}^{T}_{0}=X$, and let $\mathfrak{U}$ be a cover of $X$. We
define the cover complex $\mathcal{X}^{T}(\mathfrak{U})$ to be the restriction
of $\mathcal{X}^{T}$ to cells whose 0-skeleton lies in some
$U\in\mathfrak{U}$.

This definition agrees with definition 1.2 where the system of complexes comes
from the restriction of the full filtered complex $\mathcal{X}^{T}$ to sets in
$\mathfrak{U}$. In section 4 we will specifically consider Vietoris-Rips cover
complexes, which we will denote $\mathcal{R}(\mathbf{X},\mathfrak{U};r)$.

###  1.2 Homology, Persistence, and Interleavings

We are primarily interested in obtaining the persistent homology of filtered
complexes, which can be used to describe the robust topological features in a
filtration. For additional background on homology, we recommend [20], and for
additional information on persistent homology and interleavings, we recommend
[28]. Given a filtration $\mathcal{X}^{T}$, the homology functor in dimension
$q$ produces a persistence vector space $H_{q}(\mathcal{X}^{T})$, where for
every filtration value $t\in T$ the complex $\mathcal{X}^{t}$ has an
associated vector space $H_{q}(\mathcal{X}^{t})$, and the inclusion maps
$\mathcal{X}^{s}\subseteq\mathcal{X}^{t}$ for $s\leq t$ have associated linear
maps $F_{q}^{s,t}:H_{q}(\mathcal{X}^{s})\to H_{q}(\mathcal{X}^{t})$, as
illustrated by the diagram:

${\mathcal{X}^{s}}$${\mathcal{X}^{t}}$${H_{q}(\mathcal{X}^{s})}$${H_{q}(\mathcal{X}^{t})}$$\scriptstyle{F_{q}^{s,t}}$
(5)

The dimension, $\dim H_{q}(\mathcal{X}^{t})$, can generally be interpreted to
count the number of $q$-dimensional “holes” in the space $\mathcal{X}^{t}$,
and the induced maps describe how holes relate to one another throughout the
filtration. We will generally consider our posets $T$ to be finite subsets of
the real numbers $\mathbb{R}$, for example, the critical values at which
simplices appear in a Vietoris-Rips filtration. In this case, the persistence
vector space $H_{q}(\mathcal{X}^{T})$ is described up to isomorphism by a
collection of interval indecomposables $\\{(b_{i},d_{i})\\}$, or persistence
barcode, which track the appearance (birth) and disappearance (death) of new
homological features throughout the filtration [36, 7]. In the context of
geometric filtrations, intervals with long lengths $|d_{i}-b_{i}|$ are
typically considered robust topological features, and those with short lengths
are typically considered topological noise.

We wish to be able to compare the persistent homology of different
filtrations, which is accomplished through the use of interleavings (cite). We
can consider persistence vector spaces abstractly as quiver representations
[17, 7] over the poset $T$, which we denote $V^{T}$ (forgetting that the
vector spaces and linear maps came from homology). In order to compare two
different persistence vector spaces, we must first have a notion of map
between them.

######  Definition 1.6.

Let $V^{S}$ and $W^{T}$ be persistence vector spaces, and $\alpha:S\to T$ be a
non-decreasing map. An $\alpha$-shift map is a collection of linear maps
$F^{\alpha}=\\{F^{s}:V^{s}\to W^{\alpha(s)}\\}_{s\in S}$ which commute with
the maps in $V^{S}$ and $W^{T}$

${V^{r}}$${V^{s}}$${W^{\alpha(r)}}$${W^{\alpha(s)}}$$\scriptstyle{F^{r}}$$\scriptstyle{F^{s}}$
(6)

We denote the self-shift map $I^{\alpha}:V^{S}\to V^{S}$ as the map that
simply follows the maps in the persistence vector space $I^{\alpha}:V^{s}\to
V^{\alpha(s)}$.

An interleaving is a pair of shift maps between persistence vector spaces:

######  Definition 1.7.

An $(\alpha,\beta)$-interleaving between $V^{S}$ and $W^{T}$ is a pair of
graded maps $F^{\alpha}:V^{S}\to W^{T},G^{\beta}:W^{T}\to V^{S}$ so so that
$G^{\beta}\circ F^{\alpha}\cong I^{\beta\circ\alpha}$ and $F^{\alpha}\circ
G^{\beta}\cong I^{\alpha\circ\beta}$.

If two persistence vector spaces are $(\alpha,\beta)$ interleaved, then any
vector $v\in V^{s}$ with image in $V^{\beta\circ\alpha(s)}$ must have a non-
zero image in $W^{\alpha(s)}$. This provides a way to compare interval
indecomposables in the context of persistent homology.

The interleaving distance [10] is a distance on persistence vector spaces
constructed by considering shift maps of the form $\epsilon:t\to t+\epsilon$.
The infimum over $\epsilon\geq 0$ that admits an $(\epsilon,\epsilon)$
interleaving of two persistence vector spaces is the in

$d_{I}(V^{S},W^{T})=\inf\\{\epsilon\geq 0\mid\exists(\epsilon,\epsilon)\text{
interleaving of }V^{S},W^{T}\\}$ (7)

In the case where more general shift maps $\alpha,\beta\geq\epsilon$, then an
$(\alpha,\beta)$-interleaving bounds the interleaving distance between
persistence vector spaces from above. In the case of single-parameter
persistence, the interleaving distance is equivalent to the bottleneck
distance on persistence diagrams [22].

Interleavings are often used to obtain stability results explaining how
perturbations of an input can affect output persistence vector spaces. An
early use application of interleavings was to Gromov-Hausdorff stability of
the persistent homology of Vietoris-Rips filtrations.

######  Theorem 1.8.

[11, 13] Let $(\mathbf{X},d_{X})$ and $(\mathbf{Y},d_{Y})$ be metric spaces
with

$d_{GH}((\mathbf{X},d_{X}),(\mathbf{Y},d_{Y}))\leq\epsilon.$

Then $H_{q}(\mathcal{R}((\mathbf{X},d_{X});r))$ and
$H_{q}(\mathcal{R}((\mathbf{Y},d_{Y});r))$ are
$(\epsilon,\epsilon)$-interleaved.

###  1.3 Outline/Contributions

In this paper, we develop the use of Vietoris-Rips cover complexes,
$\mathcal{R}(\mathbf{X},\mathfrak{U};r)$, with an eye to understanding
homological stability properties and their relationship to the full Vietoris-
Rips construction. In section 2 we develop a filtered version of the acyclic
carrier theorem which can be used to construct interleavings from initial
data. In section section 3, we build up local-to-global results including
Hausdorff stability of $H_{q}$ and a generalized Nerve theorem. In section
section 4 we characterize the relationship between
$H_{q}(\mathcal{R}(\mathbf{X};r))$ and
$H_{q}(\mathcal{R}(\mathbf{X},\mathfrak{U};r))$ in terms of interleavings.
Finally, in section 5 we demonstrate the use of Vietoris-Rips cover complexes
over base spaces, and target the computation of high-dimensional homology
groups of a fiber-bundle associated to high-dimensional image patches. Several
of these results were presented in preliminary form in the dissertation of the
author [27]. The present paper includes a simplified and focused exposition,
new results relating Vietoris-Rips cover complexes to sparse filtrations, and
additional computational examples.

##  2 Filtered Carriers and Interleavings

In this section, we introduce a notion of filtered carrier between complexes,
and use this to construct explicit interleavings between persistence vector
spaces. This generalizes the definition of carriers used in algebraic
topology. Historically, carriers were used to prove equivalence of various
homology theories – see [16, 26, 25] for additional background.

###  2.1 Filtered Maps and Carriers

We define filtered carriers for objects in a category filtered by partially-
ordered sets (posets) $S,T$ with initial objects. For our purposes, we
consider totally ordered $S,T\subseteq\mathbb{R}_{+}$ (with initial object 0),
but extensions to other partially ordered sets are possible, with additional
conditions, which allow for applications to generalized or multiparameter
persistence. In order to specialize these results to standard carriers in the
non-filtered setting, it suffices to consider the single element poset
$S=T=\\{0\\}$.

######  Definition 2.1.

A filtered object in a category over a poset $T$ is a collection of objects
$\mathcal{X}^{T}=\\{\mathcal{X}^{t}\\}_{t\in T}$ where
$\mathcal{X}^{t_{1}}\subseteq\mathcal{X}^{t_{2}}$ if $t_{1}\leq t_{2}$.

The types of filtered objects we will consider are filtered cell complexes and
filtered chain complexes.

######  Definition 2.2.

Let $\mathcal{X}^{S},\mathcal{Y}^{T}$ be filtered objects in a category over
posets $S,T$ respectively. Let $\alpha:S\to T$ be a non-decreasing map. An
$\alpha$-shift map $f^{\alpha}:\mathcal{X}^{S}\to\mathcal{Y}^{T}$ is a
collection of maps $f^{s}:\mathcal{X}^{s}\to\mathcal{Y}^{\alpha(s)}$ for each
$s\in S$ so that the following diagram commutes.

${\mathcal{X}^{s}}$${\mathcal{X}^{s^{\prime}}}$${\mathcal{Y}^{\alpha(s)}}$${\mathcal{Y}^{\alpha(s^{\prime})}}$$\scriptstyle{f^{s}}$$\scriptstyle{f^{s^{\prime}}}$
(8)

We are primarily interested in the categories of cell complexes and chain
complexes. If $\alpha,\beta:S\to T$ are non-decreasing maps and
$\alpha(s)\leq\beta(s)$ for all $s\in S$, then we can extend a filtered map
$f^{\alpha}$ to a filtered map $f^{\beta}$ by first applying $f^{\alpha}$ and
then shifting the filtration to $\beta$: $f^{\beta}=\iota^{\beta-\alpha}\circ
f^{\alpha}$. While the above definition can be applied to homotopies as well,
we want to give a specialized definition of a sort of filtered chain homotopy:

######  Definition 2.3.

Let $F^{\alpha}_{\ast},G^{\alpha}_{\ast}:C_{\ast}^{S}\to D_{\ast}^{T}$ be
$\alpha$-shift maps of chain complexes. We say $F^{\alpha},G^{\alpha}$ are
$\beta$-chain homotopic, where $\beta:T\to T$ is a non-decreasing map if there
exists a collection of maps $K^{s}_{q}:C_{q}^{s}\to
D_{q+1}^{\beta\circ\alpha(s)}$ $q=0,1,\dots$, and $s\in S$, so that

$\partial^{D}_{q+1}K_{q}^{s}+K_{q-1}^{s}\partial^{C}_{q}=\iota^{\beta}(G_{q}^{s}-F_{q}^{s})$
(9)

######  Definition 2.4.

A filtered carrier of chain complexes over a poset $T$, denoted
$\mathscr{C}^{T}:C_{\ast}^{S}\to D_{\ast}^{T}$ is an assignment of basis
vectors of $C_{\ast}^{S}$ to filtered sub-complexes of $D_{\ast}^{T}$. In
situations where $T$ is understood, we will drop the superscript, and simply
write $\mathscr{C}:C_{\ast}^{S}\to D^{T}_{\ast}$.

Note that while a basis element $x\in C_{\ast}^{S}$ may appear at parameter
$s\in S$, the carrier $\mathscr{C}^{T}(x)$ is filtered by $T$. We can also
define a filtered carrier of cell complexes
$\mathscr{C}^{T}:\mathcal{X}^{S}\to\mathcal{Y}^{T}$ by assigning cells of
$\mathcal{X}^{S}$ to sub-cell complexes of $\mathcal{Y}^{T}$. A (filtered)
carrier of cell complexes produces a (filtered) carrier of chain complexes by
application of the cellular chain functor.

We say the carrier $\mathscr{C}$ is _proper_ with respect to the filtered
bases $B_{\ast}^{S}$ of $C_{\ast}^{S}$ and $B_{\ast}^{T}$ of $D_{\ast}^{T}$ if
$\mathscr{C}(x)$ is generated by a sub-basis of $B_{\ast}^{T}$ for each $x$ in
the basis $B_{\ast}^{S}$. Note that carriers of cell complexes always produce
carriers of chain complexes that are proper with respect to the cell basis.

The term “carrier” comes from the utility of carrying a map:

######  Definition 2.5.

Let $\mathscr{C}^{T}:C^{S}_{\ast}\to D^{T}_{\ast}$ be a filtered carrier, and
$F^{\alpha}_{\ast}$ be an $\alpha$-shift chain map. We say that
$F^{\alpha}_{\ast}:C^{S}_{\ast}\to D^{T}_{\ast}$ is carried by
$\mathscr{C}^{T}$ if $F^{\alpha}(x)\in\mathscr{C}^{T}(x)$ at parameter
$\alpha(s)$ for all basis elements $x\in C^{s}_{\ast}$.

Again, there is an analogous definition for carriers of filtered cell
complexes and maps.

###  2.2 A Filtered Acyclic Carrier Theorem

Recall that a chain complex $C_{\ast}$ is acyclic if its reduced homology
$\tilde{H}_{q}(C_{\ast})=0$ for all $q\geq 0$. A carrier of chain complexes
$\mathscr{C}:C_{\ast}\to D_{\ast}$ is acyclic if $\mathscr{C}(x)$ is acyclic
for all basis elements $x\in C_{\ast}$. The primary utility of acyclic
carriers is in providing a tool to extend maps from initial data. For ordinary
(non-filtered) chain complexes, we have

######  Theorem 2.6.

(Acyclic carrier theorem) If $\mathscr{C}:C_{\ast}\to D_{\ast}$ is acyclic,
and $L_{\ast}\subset C_{\ast}$ is a sub-chain complex of $C_{\ast}$, then any
chain map $\hat{F}_{\ast}:L_{\ast}\to D_{\ast}$ can be extended to a chain map
$F_{\ast}:C_{\ast}\to D_{\ast}$. Furthermore, this extension is unique up to
chain homotopy.

Proofs can be found in [16, 25, 26]. In this section, we will extend theorem
2.6 to the filtered setting.

######  Definition 2.7.

We say a filtered chain complex $C_{\ast}^{T}$ is $\alpha$-acyclic if every
cycle in $C_{\ast}^{t}$ has a boundary in $C_{\ast}^{\alpha(t)}$.

This implies that any bar in the persistent homology $H_{q}(C_{\ast}^{T})$
that is born at $t\in T$ must die before parameter $\alpha(t)$.

######  Definition 2.8.

Let $C_{\ast}^{S},D_{\ast}^{T}$ be filtered chain complexes,
$\mathscr{C}^{T}:C_{\ast}^{S}\to D_{\ast}^{T}$ be a filtered carrier, and
$\alpha:S\to T$, $\beta:T\to T$ be non-decreasing maps. We say
$\mathscr{C}^{T}$ is $(\alpha,\beta)$-acyclic if $\mathscr{C}^{T}(x)$ is
$\beta$-acyclic after $t=\alpha(s)$ for all $x\in C_{\ast}^{s}$ and for all
$s\in S$. In the case where $\beta=\operatorname{id}$, then we just say
$\mathscr{C}^{T}$ is $\alpha$-acyclic.

A related definition for cell complexes is to say a carrier
$\mathscr{C}^{T}:\mathcal{X}^{S}\to\mathcal{Y}^{T}$ is $\alpha$-contractible
if $\mathscr{C}^{T}(x)$ is contractible at $t=\alpha(s)$. This is sufficient
to give an $\alpha$-acyclic carrier after application of the chain functor.

######  Theorem 2.9.

(Filtered acyclic carrier theorem) Let $\mathscr{C}^{T}:C_{\ast}^{S}\to
D_{\ast}^{T}$ be an $(\alpha,\beta)$-acyclic carrier of filtered chain
complexes, with $S$ a strict total order with an initial object $0\in S$. Let
$L_{\ast}^{S}\subseteq C_{\ast}^{S}$ be a filtered sub-complex generated by a
filtered sub-basis of $C_{\ast}^{S}$, and $\tilde{F}^{\alpha}:L_{\ast}^{S}\to
D_{\ast}^{T}$ be an $\alpha$-filtered chain map carried by $\mathscr{C}^{T}$.
Then $\tilde{F}^{\alpha}$ extends to a filtered chain map
$F^{\beta^{k}\circ\alpha}:C_{\ast}^{S}\to D_{\ast}^{T}$, where $k$ is the
maximal dimension of the chain map, and the extension is unique up to
$\beta$-chain homotopy.

###### Proof.

We will proceed by induction on the dimension $k$ of the map, and on the total
order on $S$. First, we start with $\tilde{F}^{0,\alpha(0)}_{0}:L_{0}^{0}\to
D_{0}^{\alpha(0)}$. From the acyclic carrier theorem, theorem 2.6, we can
extend to a chain map $F_{0}^{0,\alpha(0)}\to C_{0}^{0}\to D_{0}^{\alpha(0)}$.

Now, let $s>0$. Assume that we have extended $F^{\alpha}_{0}$ for all $r<s$ so
that if $r^{\prime}<r$,

$F^{r,\alpha(r)}_{0}\mid_{C_{\ast}^{r^{\prime}}}=F^{r^{\prime},\alpha(r^{\prime})}_{0}$
(10)

Note that this is satisfied trivially for $s=0$. Let $L_{0}^{\prime
S}=L^{S}_{0}\cup\bigcup_{r<s}C_{0}^{r}$, and $\tilde{F}^{\alpha}_{0}$ denote
the extended map up to all $r<s$. We can now apply theorem 2.6 again to extend
to $F^{s,\alpha(s)}$ to $C_{0}^{s}$. Because $S$ is a strict total order, eq.
10 continues to be satisfied because the function is extended on each basis
element exactly once. By induction, we can extend to a map of 0-chains
$F^{\alpha}:C_{0}^{S}\to D_{0}^{T}$.

Because the extension is not necessarily unique, suppose that $F_{0}^{\alpha}$
and $G_{0}^{\alpha}$ are both extensions of $\tilde{F}^{\alpha}_{0}$ carried
by $\mathscr{C}$. $\partial_{0}(F^{\alpha}_{0}-G^{\alpha}_{0})=0$, so can be
expressed as the boundary of $K_{0}^{\beta\circ\alpha}:C^{S}_{0}\to D^{T}_{1}$
after shifting by an additional factor of $\beta$. This gives a $\beta$
homotopy of 0-chain maps.

Now, we’ll extend to higher-dimensional chains for $s=0$. Assume that we have
extended to $F_{k}^{\beta^{k}\circ\alpha}:C_{k}^{S}\to D_{k}^{T}$. Again,
we’ll start with the initial object $0$ of $S$. We take $L^{\prime
0}_{\ast\leq k+1}=C_{\ast\leq k}^{0}\cup L_{\ast\leq k+1}^{0}$. We have
extended $F_{\ast\leq k}^{\beta^{k}\circ\alpha}:C_{\ast\leq k}^{0}\to
D_{\ast\leq k}^{\beta^{k}\circ\alpha(s)}$. Let $x\in B_{k+1}$ be a basis
element that we must extend at filtration parameter $s=0$. We need
$\partial_{k+1}F_{k+1}x=F_{k}\partial_{k+1}x$. The image of the boundary
$F_{k}\partial_{k+1}x$ lies in $D^{\beta^{k}\circ\alpha(0)}_{k}$, but since
$\mathscr{C}$ is $(\alpha,\beta)$-acyclic, the cycle need not have a boundary
until we increase the filtration parameter $T$ by another factor of $\beta$.
We can increase the grade on the map $F^{\beta^{k+1}\circ\alpha}$, taking
$F^{\beta^{k+1}\circ\alpha}x=\iota^{\beta}F^{\beta^{k}\circ\alpha}x$ for $x\in
L^{\prime 0}$, and then apply theorem 2.6 to extend the map for $x\in
C_{k+1}^{0}$.

Now, we’ll extend to higher dimensional chains for $s>0$. Assume that so far
we have satisfied for $r^{\prime}<r<s$

$F_{k+1}^{r,\beta^{k+1}\circ\alpha(r)}\mid_{C_{k}^{r^{\prime}}}=F_{k+1}^{r^{\prime},\beta^{k+1}\circ\alpha(r^{\prime})}$
(11)

and furthermore, that we have shifted the chain maps in lower dimensions via
$F^{\beta^{k+1}\circ\alpha}=\iota^{\beta}F^{\beta^{k}\circ\alpha}$. Let $x\in
B_{k+1}$ via a basis element that we must extend at filtration parameter $s$.
The image of the boundary $F_{k}\partial_{k+1}x$ lies in
$D_{k}^{\beta^{k}\circ\alpha(s)}$, and we have already shifted the grade to
$\beta^{k+1}\circ\alpha(s)$ at which point the cycle is a boundary of some
$y\in D_{k+1}^{\beta^{k+1}\circ\alpha(s)}$ in $\mathscr{C}(x)$. Thus, we can
extend the map via $F_{k+1}^{\beta^{k+1}\circ\alpha}x=y$. Again, because $S$
is a strict total order, the map is extended for every basis element exactly
once, so eq. 11 is satisfied.

Following a similar inductive argument, we can extend a $\beta$ homotopy of
extended chain maps $F^{\beta^{k}\circ\alpha}_{k}$,
$G^{\beta^{k}\circ\alpha}_{k}$ to a $\beta$ homotopy of
$F^{\beta^{k+1}\circ\alpha}_{k+1}$ and $G^{\beta^{k+1}\circ\alpha}_{k}$, still
incurring an additional shift of $\beta$.

By induction on $k$ and the strict total order of $S$, we conclude that we can
extend $\tilde{F}^{\alpha}$ to a shifted chain map
$F^{\beta^{k}\circ\alpha}:C^{S}_{\ast}\to D^{T}_{\ast}$, and that this chain
map is unique up to $\beta$-chain homotopy. ∎

######  Remark 2.10.

To compute induced maps in homology in dimension $k$, it is only necessary to
extend maps up to dimension $k$. In many cases, $\beta$ will be the identity
$\operatorname{id}$, in which case there is no additional penalty for
extending to higher-dimensional chains.

######  Remark 2.11.

In theorem 2.9 we used the strict total ordering on $S$ to extend the initial
map so that we guaranteed that eq. 10 is always satisfied. If $S$ is not a
strict total ordering, then additional restrictions on the extension are
needed to satisfy this condition.

######  Proposition 2.12.

Let $\mathscr{C}:C^{S}_{\ast}\to D^{T}_{\ast}$ be an $(\alpha,\beta)$-acyclic
carrier that is proper with respect to a $T$-filtered basis $B^{D}_{\ast}$ of
$D_{\ast}$. Then there exists a chain map $F^{\alpha}_{0}:C_{0}^{S}\to
D_{0}^{T}$ carried by $\mathscr{C}$ which preserves the canonical augmentation
$\epsilon:x\mapsto 1$ for basis elements $x\in C^{S}_{0}$.

###### Proof.

For each 0-dimensional basis element $x\in C_{0}^{S}$, we simply assign
$F^{\alpha}_{0}(x)=y$ for some basis element $y\in
B_{0}^{D}\mid_{\mathscr{C}(x)}$. Such a $y$ exists at level $\alpha(s)$ for
basis elements $x$ at parameter $s$ in $C_{0}^{s}$, so the map requires an
$\alpha$ shift. This map will preserve the augmentation of the chain complexes
because it sends 0-dimensional basis elements to 0-dimensional basis elements.
∎

Note that the map $F^{\alpha}_{0}$ in proposition 2.12 can then be extended to
$F^{\beta^{k}\circ\alpha}_{k}$ using theorem 2.9.

######  Proposition 2.13.

Suppose $F_{\ast}^{\alpha},G_{\ast}^{\alpha}:C_{\ast}^{S}\to D_{\ast}^{T}$ are
augmentation-preserving chain maps carried by an $(\alpha,\beta)$-acyclic
carrier $\mathscr{C}$. Then $F_{\ast}$ and $G_{\ast}$ are $\beta$-chain-
homotopic.

###### Proof.

For each basis element $x\in C_{0}$, $F_{0}(x),G_{0}(x)\in\mathscr{C}(x)$, and
because $F_{\ast}$ and $G_{\ast}$ are augmentation preserving, $\epsilon
x=\epsilon F(x)=\epsilon G(x)$, so $\epsilon\big{(}F(x)-G(x))=0$. Because
$\mathscr{C}$ is $\beta$-acyclic,
$\ker\epsilon=\operatorname{img}\partial_{1}$, so there must exist a 1-chain
$K(x)\in\mathscr{C}(x)$ at level $\beta\circ\alpha$ so that
$\partial_{1}K(x)=F(x)-G(x)$, which is a homotopy of zero-chains. We can then
apply theorem 2.9 theorem to extend this to a $\beta$-homotopy
$K_{\ast}:F_{\ast}\to G_{\ast}$. ∎

In the case where $\beta=\operatorname{id}$, then the two maps produce
isomorphic maps on homology.

###  2.3 Interleavings via Filtered Acyclic Carriers

We’ll now turn to examining the conditions under which interleavings can be
constructed from filtered carriers.

######  Proposition 2.14.

Let $\mathcal{X}^{S}$ and $\mathcal{Y}^{T}$ be filtered cell complexes, and
suppose that $\mathscr{C}:\mathcal{X}^{S}\to\mathcal{Y}^{T}$ is an
$\alpha$-acyclic carrier, $\mathscr{D}:\mathcal{Y}^{T}\to\mathcal{X}^{S}$ is a
$\beta$-acyclic carrier, $\mathscr{A}\supseteq\mathscr{D}\circ\mathscr{C}$ is
a $(\beta\circ\alpha)$-acyclic carrier that carries the inclusion map on
$\mathcal{Y}^{T}$, and $\mathscr{B}\supseteq\mathscr{C}\circ\mathscr{D}$ is
$(\alpha\circ\beta)$-acyclic and carries the inclusion map on
$\mathcal{X}^{S}$. Then $H_{q}(\mathcal{X}^{S})$ and $H_{q}(\mathcal{Y}^{T})$
are $(\alpha,\beta)$-interleaved for any $q=0,1,\dots$.

###### Proof.

First, we construct augmentation-preserving shift maps
$F^{\alpha}:C_{\ast}(\mathcal{X}^{s})\to C_{\ast}(\mathcal{Y}^{\alpha(s)})$
and $G^{\beta}:C_{\ast}(\mathcal{Y}^{t})\to C_{\ast}(X^{\beta(t)})$ using
proposition 2.12 and theorem 2.9. Now, note that $G^{\beta}\circ F^{\alpha}$
is augmentation preserving, and is carried by
$\mathscr{D}\circ\mathscr{C}\subseteq\mathscr{A}$ which also carries the
inclusion map, so by proposition 2.13 $G^{\beta}\circ F^{\alpha}\simeq
I^{\mathcal{X}}$. Similarly, $F^{\alpha}\circ G^{\beta}\simeq
I^{\mathcal{Y}}$. Thus, the maps $F^{\alpha}$ and $G^{\beta}$ give an
$(\alpha,\beta)$-interleaving on homology. ∎

In practice, more specific situations reduce the number of conditions that we
need to satisfy. Often, we will find it convenient to take
$\mathscr{A}=\mathscr{C}\circ\mathscr{D}$, and
$\mathscr{B}=\mathscr{D}\circ\mathscr{C}$ when we can show that the composites
are acyclic and carry inclusions.

######  Corollary 2.15.

Suppose $f^{\alpha}:\mathcal{X}^{s}\to\mathcal{Y}^{\alpha(s)}$ is a surjective
simplicial map for every $s\in S$, and suppose
$\mathscr{C}:\mathcal{Y}^{T}\to\mathcal{X}^{S}$, defined by
$\mathscr{C}(y)=\langle f^{-1}(y)\rangle$ be a $\beta$-acyclic carrier. Then
$H_{q}(\mathcal{X}^{S})$ and $H_{q}(\mathcal{Y}^{T})$ are
$(\alpha,\beta)$-interleaved for $q=0,1,\dots$.

###### Proof.

Because $f^{\alpha}$ is simplicial, the carrier $\mathscr{C}^{f}$ defined by
$\mathscr{C}^{f}(x)=\langle f(x)\rangle$ is an $\alpha$-acyclic carrier that
carries $f^{\alpha}$. Because $f^{\alpha}$ is a surjective simplicial map,
$\mathscr{C}(y)$ is nonempty and maps to proper sub-complexes of
$\mathcal{X}^{S}$ for each $y\in\mathcal{Y}^{T}$, so is a well-defined
filtered carrier. By definition, of $\mathscr{C}$, the composition
$\mathscr{C}\circ\mathscr{C}^{f}$ carries the inclusion map
$\iota^{\mathcal{X}}$. Additionally, $\mathscr{C}\circ f^{\alpha}$ is
$(\beta\circ\alpha)$-acyclic, because $\mathscr{C}$ is $\beta$-acyclic for the
simplex $f^{\alpha}(x)$ for each $x\in\mathcal{X}^{S}$. Because
$\mathscr{C}(y)=\langle f^{-1}(y)\rangle$,
$f^{\alpha}\circ\mathscr{C}(y)=\langle y\rangle$, which is a simplicial
carrier and thus acyclic. Note that $y\in f^{\alpha}\circ\mathscr{C}(y)$, so
$f^{\alpha}\circ\mathscr{C}$ carries $\iota^{\mathcal{Y}}$. We can now apply
the chain functor and proposition 2.14 to complete the proof. ∎

##  3 Cover Complexes

###  3.1 Local Stability

In classical topology, a situation of interest is to study spaces over a base
space. In particular, we consider surjective maps
$p:\mathcal{X}\to\mathcal{B}$, where $\mathcal{B}$ is called the base space.
Some problems of interest focus on maps over $\mathcal{B}$.

${\mathcal{X}}$${\mathcal{Y}}$${\mathcal{B}}$$\scriptstyle{f}$$\scriptstyle{p}$$\scriptstyle{q}$
(12)

######  Definition 3.1.

Let $\mathcal{X}^{S}(\mathfrak{U})$, $\mathcal{Y}^{T}(\mathfrak{U})$ be cover
complexes over a cover $\mathfrak{U}$. A system of carriers
$\mathscr{C}(\mathfrak{U}):\mathcal{X}^{S}(\mathfrak{U})\to\mathcal{Y}^{T}(\mathfrak{U})$
consists of carriers $\mathscr{C}(U):\mathcal{X}^{S}(U)\to\mathcal{Y}^{T}(U)$
for each $U\in\mathfrak{U}$. We say the system of carriers is compatible if
$\cap U_{k}\neq\emptyset$ implies $\mathscr{C}(U_{i})\mid_{\cap
U_{k}}=\mathscr{C}(U_{j})\mid_{\cap U_{k}}$ for all
$U_{i},U_{j}\in\\{U_{k}\\}$.

In general, $U\in\mathfrak{U}$ need not cover the same points in $X$ and $Y$
(denoting the vertex sets of $\mathcal{X}$, $\mathcal{Y}$ respectively). We
can alternatively think of it as an identification of sets in covers of each
vertex set, or a set in a cover of the disjoint union $X\sqcup Y$.

When the system of carriers is compatible, we can extend carriers defined on
sets of $\mathfrak{U}$ to intersections via $\mathscr{C}(\cap
U_{k})=\mathscr{C}(U_{i})\mid_{\cap U_{k}}$ for $U_{i}\in\\{U_{k}\\}$. We’ll
say a compatible system of carriers is $(\alpha,\beta)$-acyclic if
$\mathscr{C}(\cap U_{k})$ is $(\alpha,\beta)$-acyclic for all
$\\{U_{k}\\}\subset\mathfrak{U}$ where $\cap U_{k}\neq\emptyset$.

We can define a carrier
$\mathscr{C}_{\mathfrak{U}}:\mathcal{X}^{T}(\mathfrak{U})\to\mathcal{Y}^{S}(\mathfrak{U})$
from a compatible system of carriers via
$\mathscr{C}_{\mathfrak{U}}(x)=\mathscr{C}(\cap\\{U\ni x\\})(x)$. When a
compatible system of carriers $\mathscr{C}(\mathfrak{U})$ is
$(\alpha,\beta)$-acyclic, $\mathscr{C}_{\mathfrak{U}}$ is also
$(\alpha,\beta)$-acyclic through application of the definition. The advantage
of using a compatible system of carriers $\mathscr{C}(\mathfrak{U})$ instead
of the global carrier $\mathscr{C}_{\mathfrak{U}}$ is that we only need to
check conditions locally in the cover.

######  Proposition 3.2.

Let $\mathfrak{U}$ be a finite cover. Suppose
$\mathscr{C}(\mathfrak{U}):\mathcal{X}^{S}(\mathfrak{U})\to\mathcal{Y}^{T}(\mathfrak{U})$
is an $\alpha$-acyclic compatible system of carriers, and
$\mathscr{D}(\mathfrak{U}):\mathcal{Y}^{T}(\mathfrak{U})\to\mathcal{X}^{S}(\mathfrak{U})$
is a $\beta$-acyclic compatible system of carriers. Furthermore suppose that
for each $V=\cap U_{k}\neq\emptyset$, that $\mathscr{C}(V)\circ\mathscr{D}(V)$
is $(\alpha\circ\beta)$-acyclic and carries the identity, and
$\mathscr{D}(V)\circ\mathscr{C}(V)$ is $(\beta\circ\alpha)$-acyclic and
carries the identity. Then there exists an $(\alpha,\beta)$-interleaving of
$H_{q}(\mathcal{X}^{S})$ and $H_{q}(\mathcal{Y}^{T})$.

###### Proof.

This follows by constructing the global carriers
$\mathscr{C}_{\mathfrak{U}}:\mathcal{X}^{S}(\mathfrak{U})\to\mathcal{Y}^{T}(\mathfrak{U})$
and
$\mathscr{D}_{\mathfrak{U}}:\mathcal{Y}^{T}(\mathfrak{U})\to\mathcal{X}^{S}(\mathfrak{U})$,
and noting that because the composite
$\mathscr{C}_{\mathfrak{U}}\circ\mathscr{D}_{\mathfrak{U}}$ is
$(\alpha\circ\beta)$-acyclic locally and carries the identity locally, it
satisfies these properties globally. Similarly,
$\mathscr{D}_{\mathfrak{U}}\circ\mathscr{C}_{\mathfrak{U}}$ is
$(\beta\circ\alpha)$-acyclic and carries the identity. We can then apply
proposition 2.14 to obtain the result. ∎

The utility of proposition 3.2 is to show that if we have identified sub-
complexes of $\mathcal{X}^{S}$ and $\mathcal{Y}^{T}$ in a consistent way using
the cover that we can interleave the homology of the two filtrations.

###  3.2 Local Geometric Stability

Proposition 3.2 can be used to extend standard geometric stability results as
in [13] to cover complexes. We will focus on how cover complexes behave with
respect to perturbations of the data

Several of our results will use the refinement of the cover $\mathfrak{U}$, as

$\bar{\mathfrak{U}}=\big{\\{}\bigcap_{i\in I}U_{i}|\\{U_{i}\\}_{i\in
I}\subseteq\mathfrak{U}\big{\\}}$ (13)

######  Proposition 3.3.

$H_{\ast}(\mathcal{N}(\mathfrak{U}))\simeq
H_{\ast}(\mathcal{N}(\bar{\mathfrak{U}}))$.

###### Proof.

We define a carrier
$\mathscr{C}:\mathcal{N}(\mathfrak{U})\to\mathcal{N}(\bar{\mathfrak{U}})$ via

$\mathscr{C}(U_{0},\dots,U_{k})=\langle
V=\cap\\{U_{i}\\}\mid\\{U_{i}\\}\subseteq\\{U_{0},\dots,U_{k}\\}\rangle$ (14)

This carrier is acyclic because it forms a cone with the vertex
$V=\cap_{i=0}^{k}U_{i}$.

We define a carrier
$\mathscr{D}:\mathcal{N}(\bar{\mathfrak{U}})\to\mathcal{N}(\mathfrak{U})$ via

$\mathscr{C}(V_{0},\dots,V_{k})=\langle U\mid U\supset
V_{i}\in\\{V_{0},\dots,V_{k}\\}\rangle$ (15)

Note that if $(V_{0},\dots,V_{k})$ is a simplex in
$\mathcal{N}(\bar{\mathfrak{U}})$, there is a smallest set $V_{i_{0}}$ in the
simplex, and so $\mathscr{C}(V_{0},\dots,V_{k})=\mathscr{C}(V_{i_{0}})$. This
also implies that $\mathscr{C}$ is simplicial, thus acyclic.

Now, we have that $\mathscr{D}\circ\mathscr{C}(U_{0},\dots,U_{k})$ is a the
simplex $(U_{0},\dots,U_{k},U^{\prime}_{0},\dots)$ where the extra simplices
$U^{\prime}_{i}$ are added if $\cap_{i=0}^{k}U_{i}\subseteq U^{\prime}_{i}$,
which can appear for degenerate $\bar{\mathfrak{U}}$. This carrier is
simplicial, thus acyclic, and clearly carries the identity.

The composition $\mathscr{C}\circ\mathscr{D}$ is acyclic because
$\mathscr{C}\circ\mathscr{D}(V_{0},\dots,V_{k})$ forms a cone with the vertex
on the minimal element $V_{i_{0}}\in\\{V_{0},\dots,V_{k}\\}$. This composite
carrier also carries the identity map.

We can now apply proposition 2.14 to trivial filtrations on the Nerves to
obtain the result. ∎

######  Proposition 3.4.

Let $\mathbf{X},\mathbf{Y}$ be samples from a metric space $(X,d_{X})$, and
let $\mathfrak{U}$ be a cover of $\mathbf{X}$ and $\mathfrak{V}$ be a cover of
$\mathbf{Y}$. Suppose that for all $U\in\bar{\mathfrak{U}}$, there exists a
$V\in\bar{\mathfrak{V}}$ such that $d_{H}(U,V)\leq\epsilon$. Then
$\mathcal{R}(\mathbf{X},\mathfrak{U};r)$ and
$\mathcal{R}(\mathbf{Y},\mathfrak{V};r)$ are $2\epsilon$-interleaved.

###### Proof.

Let $U_{x}=\bigcap\\{U\in\mathfrak{U}\mid U\ni x\\}$. By assumption, there
exists some $V_{x}\in\bar{\mathfrak{V}}$ such that
$d_{H}(U_{x},V_{x})\leq\epsilon$, meaning there must exist some $y\in V_{x}$
so that $d_{X}(x,y)\leq\epsilon$. Let
$\Omega\subseteq\mathbf{X}\times\mathbf{Y}$ be the left-total relation
$\Omega(x)=\\{y\in V_{x}\mid d_{X}(x,y)\leq\epsilon\\}$. Then the induced
carrier
$\mathscr{C}_{\Omega}:\mathcal{R}(\mathbf{X},\mathfrak{U};r)\to\mathcal{R}(\mathbf{Y},\mathfrak{V};r)$
is $2\epsilon$-simplicial. Similarly, for $y\in\mathbf{Y}$, we take
$V_{y}=\bigcap_{V\ni y}V$ and $U_{y}\in\bar{\mathfrak{U}}$ the set that
satisfies $d_{H}(U_{y},V_{y})\leq\epsilon$. From the set using the right-total
relation $\Psi\subseteq\mathbf{X}\times\mathbf{Y}$, with $\Psi(y)=\\{x\in
U_{y}\mid d_{X}(x,y)\leq\epsilon\\}$, we obtain a $2\epsilon$-simplical
carrier
$\mathscr{D}_{\Psi}:\mathcal{R}(\mathbf{Y},\mathfrak{V};r)\to\mathcal{R}(\mathbf{X},\mathfrak{U};r)$.

Now, note that the composite carrier
$\mathscr{D}_{\Psi}\circ\mathscr{C}_{\Omega}$ need not carry the identity,
because $y\in V_{x}$ does not imply $x\in U_{y}$. However, $y\in V_{x}$
implies does imply that $V_{y}\subseteq V_{x}$ which combined with the
Hausdorff distance bound implies there must exist some $x^{\prime}\in
V_{y}\cap\mathbf{X}$ such that $d_{X}(x^{\prime},y)\leq\epsilon$, which
implies $d_{X}(x^{\prime},x)\leq 2\epsilon$ by triangle inequality. We can
define a left-total relation
$\Omega^{\prime}\subseteq\mathbf{X}\times\mathbf{X}$, with
$\Omega^{\prime}=\\{(x,x^{\prime})\mid d(x,x^{\prime})\leq
2\epsilon,x^{\prime}\in V_{x}\\}$, which is nonempty, and
$4\epsilon$-simplical by triangle inequality. Furthermore, the carrier
$\mathscr{A}_{\Omega^{\prime}}$ contains the composite
$\mathscr{D}_{\Psi}\circ\mathscr{C}_{\Omega}$ and carries the identity.
Similarly, we can define a relation
$\Psi^{\prime}\subset\mathbf{Y}\times\mathbf{Y}$ with
$\Psi^{\prime}=\\{(y,y^{\prime})\mid d_{X}(y,y^{\prime})\leq 2\epsilon\\}$
which produces a $4\epsilon$-simplicial carrier $\mathscr{B}_{\Psi^{\prime}}$
which contains the composite $\mathscr{C}_{\Omega}\circ\mathscr{D}_{\Psi}$ and
carries the identity.

We can now apply proposition 2.14 to obtain the result. ∎

######  Corollary 3.5.

Let $\mathbf{X},\mathbf{Y}$ be samples from a metric space $(X,d_{X})$, and
let $\mathfrak{W}$ be a cover of $\mathbf{X}\sqcup\mathbf{Y}$ such that
$d_{H}(W|_{\mathbf{X}},W|_{\mathbf{Y}})\leq\epsilon$ for all
$W\in\bar{\mathfrak{W}}$. Then $\mathcal{R}(\mathbf{X},\mathfrak{W};r)$ and
$\mathcal{R}(\mathbf{Y},\mathfrak{W};r)$ are $2\epsilon$-interleaved.

###### Proof.

We apply proposition 3.4 taking $\mathfrak{U}=\\{W\cap\mathbf{X}\mid
W\in\mathfrak{W}\\}$ and $\mathfrak{V}=\\{W\cap\mathbf{Y}\mid
W\in\mathfrak{W}\\}$. ∎

corollary 3.5 specializes to the standard stability bound [13] when
$\mathfrak{U}=\\{\mathbf{X}\\}$.

######  Comment 3.6.

The conditions of proposition 3.4 imply that
$\mathcal{N}(\mathfrak{U})\simeq\mathcal{N}(\mathfrak{V})$.

###  3.3 A Generalized Nerve Theorem

We’ll now prove a version of the Nerve theorem for cover complexes. This
result can be viewed as a special case of of the approximate nerve theorems in
[18, 9]. While our proof is narrower in scope than the aforementioned results,
the use of carriers will considerably simplify the proof, compared to [18]
which used the Mayer-Vietoris spectral sequence, and [9] which used a
construction using the blowup complex.

######  Theorem 3.7.

(Nerve Theorem [2]) Let $\mathfrak{U}$ be a cover of a paracompact space $X$,
where if $\cap U_{i}\neq\emptyset$, then $\cap U_{i}$ is contractible. Then
$\mathcal{N}(\mathfrak{U})\simeq X$.

A proof can be found in [20].

######  Theorem 3.8.

[an $\alpha$-Acyclic Nerve Theorem] Let $\mathfrak{U}$ be a cover of a vertex
set $X$, and let $\mathcal{X}^{T}(\mathfrak{U})$ be a simplicial cover
complex, with $T$ a strict order with initial object $0$. If
$\mathcal{X}^{T}(V)$ is $\alpha$-acyclic for every $V\in\bar{\mathfrak{U}}$,
then $H_{k}(\mathcal{N}(\mathfrak{U}))$ and
$H_{k}(\mathcal{X}^{T}(\mathfrak{U}))$ are
$(\alpha^{k+1},\operatorname{id})$-interleaved.

###### Proof.

We’ll construct an interleaving with $\mathcal{N}(\bar{\mathfrak{U}})$, which
has isomorphic homology to $\mathcal{N}(\mathfrak{U})$ by proposition 3.3.

We’ll first define a carrier
$\mathscr{D}:\mathcal{N}(\bar{\mathfrak{U}})\to\mathcal{X}^{T}$. We take
$\mathscr{D}(V)=\mathcal{X}^{T}(V)$, and
$\mathscr{D}(V_{0},\dots,V_{k})=\mathcal{X}^{T}(V_{0}\cup\dots\cup
V_{k})=\mathcal{X}^{T}(V_{i_{k}})$, where $V_{i_{k}}$ is the maximal set in
$\\{V_{0},\dots,V_{k}\\}$. This forms a $(0,\alpha)$-acylic carrier by
assumption, where $0$ denotes the map to the initial object of $T$.

Now, we define a carrier
$\mathscr{C}:\mathcal{X}^{T}(\mathfrak{U})\to\mathcal{N}(\bar{\mathfrak{U}})$.
We take

$\mathscr{C}(x_{0},\dots,x_{k})=\bigg{\langle}\bigg{\\{}\bigcap_{V\supseteq
S}V\bigg{\\}}_{S\subseteq\\{x_{0},\dots,x_{k}\\}}\bigg{\rangle}$ (16)

Let $V^{\prime}=\bigcap_{V\supseteq\\{x_{0},\dots,x_{k}\\}}V$. The carrier
above forms a cone with $V^{\prime}$, so is acyclic.

$\mathscr{D}\circ\mathscr{C}$ carries the identity because eq. 16 ensures that
some $V^{\prime}$ for which $\\{x_{0},\dots,x_{k}\\}\subseteq V^{\prime}$ is
included in $\mathscr{C}(x_{0},\dots,x_{k})$, and
$\mathscr{D}(V)\ni(x_{0},\dots,x_{k})$ for that $V$. Because all other sets in
eq. 16 are contained in $V^{\prime}$,
$\mathscr{D}\circ\mathscr{C}(x_{0},\dots,x_{k})=\mathscr{D}(V^{\prime})$,
which is $(0,\alpha)$-acyclic by assumption.

Any $(x_{0},\dots,x_{k})\in\mathscr{D}(V)$, implies
$\\{x_{0},\dots,x_{k}\\}\subseteq V$. Thus, every $V_{i}$ generating the
carrier in eq. 16 satisfies $V_{i}\subseteq\mathscr{C}(x_{0},\dots,x_{k})$. We
can define $\mathscr{A}(V)$ to be the star of $V$ inside
$\mathcal{N}(\bar{\mathfrak{U}})$. This carrier is acyclic because it forms a
cone with the vertex for $V$, and contains $\mathscr{C}\circ\mathscr{D}(V)$.
For $(V_{0},\dots,V_{k})\in\mathcal{N}(\bar{\mathfrak{U}})$, we take
$\mathscr{A}(V_{0},\dots,V_{k})=\mathscr{A}(V_{i_{k}})$, where $V_{i_{k}}$ is
the maximal set in the simplex. Again, this carrier is acyclic and carries the
identity.

We have now constructed carriers for maps in the following diagram

${\mathcal{X}^{T}(\mathfrak{U})}$${\mathcal{X}^{T}(\mathfrak{U})}$${\mathcal{N}(\bar{\mathfrak{U}})}$${\mathcal{N}(\bar{\mathfrak{U}})}$$\scriptstyle{\mathscr{C}}$$\scriptstyle{\mathscr{C}}$$\scriptstyle{\mathscr{A}}$$\scriptstyle{\mathscr{D}}$
(17)

We can now construct a map
$P_{\ast}:C_{\ast}(\mathcal{X}^{T}(\mathfrak{U}))\to
C_{\ast}(\mathcal{N}(\bar{\mathfrak{U}}))$ carried by $\mathscr{C}$ by
applying proposition 2.12. We can also construct maps
$F_{i}^{\alpha^{i}}:C_{i}(\mathcal{N}(\bar{\mathfrak{U}}))\to
C_{i}(\mathcal{X}^{\alpha^{i}(0)})$ using theorem 2.9, where
$\partial_{i}F_{i}^{\alpha^{i}}x=F_{i-1}^{\alpha^{i-1}}\partial_{i}x$, which
we need to construct for $i=0,\dots,k+1$. Because
$\mathscr{D}\circ\mathscr{C}$ carries the inclusion, we can construct a
homotopy, but only after increasing the grade by an extra factor of $\alpha$
in each dimension $i$, $I^{\alpha}F_{i}^{\alpha^{i}}\circ P_{i}\simeq
I^{\alpha^{i+1}}_{i}$. In order to compute induced maps on homology for
$H_{i}$, we only need to extend the chain homotopy up to dimension $i$. On
homology, we have
$\tilde{I}^{\alpha}\tilde{F}^{\alpha^{k}}_{k}{\tilde{P}_{k}}\cong\tilde{I}^{\alpha^{k+1}}_{k}$.

Finally, because $\mathscr{A}$ is acyclic and carries $P_{\ast}\circ F_{\ast}$
as well as the inclusion, we have $\tilde{P}_{k}\circ
I^{\alpha}\tilde{F}^{\alpha^{k}}\simeq I$, we have constructed a
$(\alpha^{k+1},\operatorname{id})$-interleaving. ∎

Note that for Vietoris-Rips cover complexes as well as other geometric
complexes, that there will be some parameter $t\in T$ at which
$\mathcal{X}^{T}(V)$ will be acyclic for all $V$, when $\mathcal{X}^{T}(V)$
forms the maximal simplex on its vertex set. At this point, the cover complex
and nerve are homotopic by the standard nerve theorem (theorem 3.7).

######  Corollary 3.9.

Let $\mathfrak{U}$ be a cover of $X$, where $\mathcal{X}^{T}(\mathfrak{U})$
satisfies the conditions of theorem 3.8. Then if $\mathcal{N}(\mathfrak{U})$
is acyclic, $H_{k}(\mathcal{X}^{T}(\mathfrak{U}))$ is
$(\alpha^{k+1})$-acyclic.

###### Proof.

This follows because if $\mathcal{N}(\mathfrak{U})$ is acyclic, then the
interleaving implies that $\mathcal{X}^{T}(\mathfrak{U})$ is
$\alpha^{k+1}$-acyclic. ∎

##  4 Rips-Cover Constructions

We now focus on Vietoris-Rips cover complexes, which we denote as
$\mathcal{R}(\mathbf{X},\mathfrak{U};r)$. We seek to answer the following
questions:

  1. 1.

For a fixed cover $\mathfrak{U}$, how sensitive is
$\mathcal{R}(\mathbf{X},\mathfrak{U};r)$ to perturbations of the underlying
data $X$?

  2. 2.

For a fixed dataset $\mathbf{X}$, how sensitive is
$\mathcal{R}(\mathbf{X},\mathfrak{U};r)$ to the choice of cover
$\mathfrak{U}$?

  3. 3.

How does $\mathcal{R}(\mathbf{X},\mathfrak{U};r)$ relate to the full Vietoris-
Rips complex $\mathcal{R}(\mathbf{X};r)$?

A related definition is the Rips system found in Yoon’s 2018 dissertation [35]
which is used for distributed computation of persistent homology of Rips
complexes via cellular (co)-sheaves. Yoon shows that if the Nerve is
1-dimensional, and the system covers the full Rips complex, that the Rips
system can be used to obtain the Homology of the full complex, and develops a
distributed algorithm for computation. We will consider more general
coverings, and characterize regimes where the cover complex and full complex
are interleaved, but not identical. Distribution schemes for computing
persistent homology of cover complexes in their full generality are beyond the
scope of this work.

###  4.1 Interleavings for Arbitrary Covers

We now turn to relating the persistent homology of
$\mathcal{R}(\mathbf{X},\mathfrak{U};r)$ to the persistent homology of
$\mathcal{R}(\mathbf{X};r)$. At large $r$ parameters, Vietoris-Rips complexes
become acyclic, so following theorem 3.8 that
$PH_{\ast}(\mathcal{R}(\mathbf{X},\mathfrak{U};r))$ will eventually converge
to $H_{\ast}(\mathcal{N}(\mathfrak{U}))$. This means that unless
$\mathcal{N}(\mathfrak{U})$ is acyclic,
$PH_{\ast}(\mathcal{R}(\mathbf{X},\mathfrak{U};r)$ and
$PH_{\ast}(\mathcal{R}(\mathbf{X};r))$ can not possibly interleave for
sufficiently large $r$ parameters. However, in situations where sets in the
cover have non-trivial structure, we would like to understand how this
structure relates to the full filtration $\mathcal{R}(\mathbf{X};r)$,
particularly for small values of $r$.

Because there are inclusions
$\mathcal{R}(\mathbf{X},\mathfrak{U};r)\hookrightarrow\mathcal{R}(\mathbf{X};r)$,
it suffices to study under what conditions we can extend a map $f^{\alpha}$ in
the diagram

${\mathcal{R}(\mathbf{X},\mathfrak{U};r)}$${\mathcal{R}(\mathbf{X},\mathfrak{U};\alpha(r))}$${\mathcal{R}(\mathbf{X};r)}$${\mathcal{R}(\mathbf{X};\alpha(r))}$$\scriptstyle{f^{\alpha}}$
(18)

We focus on a carrier
$\mathscr{C}:\mathcal{R}(\mathbf{X};r)\to\mathcal{R}(\mathbf{X},\mathfrak{U};r)$
generated from witness sets

$\mathbf{X}(x_{0},\dots,x_{k})=\\{y\in\mathbf{X}\mid d(y,x_{i})\leq
d(x_{0},\dots,x_{k})\ \forall i=0,\dots,k\\}$ (19)

and their union, denoted

$\bar{\mathbf{X}}(x_{0},\dots,x_{k})=\bigcup_{S\in\mathcal{P}(\\{x_{0},\dots,x_{k}\\})}\mathbf{X}(S)$
(20)

where $\mathcal{P}$ denotes the power set. We define the carrier
$\mathscr{C}:\mathcal{R}(\mathbf{X};r)\to\mathcal{R}(\mathbf{X},\mathfrak{U};r)$
via

$\mathscr{C}:(x_{0},\dots,x_{k})\mapsto\langle\bar{\mathbf{X}}(x_{0},\dots,x_{k})\rangle$
(21)

and let

$\bar{\mathfrak{U}}(x_{0},\dots,x_{k})=\\{V\cap\bar{\mathbf{X}}(x_{0},\dots,x_{k})\mid
V\in\bar{\mathfrak{U}},\bar{\mathbf{X}}(x_{0},\dots,x_{k})\cap
V\neq\emptyset\\}$ (22)

which covers $\mathscr{C}(x_{0},\dots,x_{k})$.

######  Definition 4.1.

We define three thresholds: $R_{1}\leq R_{2}\leq R_{3}$ which describe
different regimes of the non-decreasing map $\alpha$.

  1. 1.

Let $R_{1}$ be the largest value so that if $d(x_{0},\dots,x_{k})\leq R_{1}$
then there exists some $U\in\mathfrak{U}$ so that $x_{0},\dots,x_{k}\in U$.

  2. 2.

Let $R_{2}$ be the largest value so that if $d(x_{0},\dots,x_{k})\leq R_{2}$
then $\mathcal{N}(\bar{\mathfrak{U}}(x_{0},\dots,x_{k}))$ is acyclic and
$\mathbf{X}(x_{0},\dots,x_{k})\cap V)$ is non-empty for each
$V\in\bar{\mathfrak{U}}(x_{0},\dots,x_{k})$.

  3. 3.

Let $R_{3}$ be the largest value so that if $d(x_{0},\dots,x_{k})\leq R_{3}$
then $\mathcal{N}(\bar{\mathfrak{U}}(x_{0},\dots,x_{k}))$ is acyclic.

If we impose a mild condition that for any points $x,y\in\mathbf{X}$ with
$d(x,y)=0$ then $U\cap\\{x,y\\}$ is either $\\{x,y\\}$ or empty for all
$U\in\mathfrak{U}$, then $0\leq R_{1}$.

######  Theorem 4.2.

$H_{k}(\mathcal{R}(\mathbf{X},\mathfrak{U};r))$ and
$H_{k}(\mathcal{R}(\mathbf{X};r))$ are
$(\operatorname{id},\alpha)$-interleaved, where $\alpha(r)=r$ for $r\leq
R_{1}$, $\alpha(r)\leq 2r$ for $r\leq R_{2}$ and $\alpha(r)\leq 3r$ for $r\leq
R_{3}$. For $r>R_{3}$, an interleaving may not exist.

Proofs of each inequality are in proposition 4.3, proposition 4.7, and
proposition 4.8.

######  Proposition 4.3.

$\mathcal{R}(\mathbf{X},\mathfrak{U};r)=\mathcal{R}(\mathbf{X};r)$ for all
$r\leq R_{1}$.

###### Proof.

This follows because if $(x_{0},\dots,x_{k})\in\mathcal{R}(\mathbf{X};r)$,
then $d(x_{0},\dots,x_{k})\leq r\leq R_{1}$, so
$(x_{0},\dots,x_{k})\in\mathcal{R}(\mathbf{X},U;r)\subseteq\mathcal{R}(\mathbf{X},\mathfrak{U};r)$
for some $U\in\mathfrak{U}$. Thus
$\mathcal{R}(\mathbf{X};r)\subseteq\mathcal{R}(\mathbf{X},\mathfrak{U};r)$,
and we already know
$\mathcal{R}(\mathbf{X},\mathfrak{U};r)\subseteq\mathcal{R}(\mathbf{X};r)$,
giving equality. ∎

This mean that covers $\mathfrak{U}$ that encode some notion of locality
produce cover complexes which are identical to the full Rips complex at the
beginning of the filtration.

We now turn to the non-trivial interleavings. Let
$\iota:\mathcal{R}(\mathbf{X},\mathfrak{U};r)\to\mathcal{R}(\mathbf{X};r)$
denote the canonical inclusion, seen in eq. 18. Clearly,
$\mathscr{C}\circ\iota$ carries the inclusion
$\mathcal{R}(\mathbf{X},\mathfrak{U};r)\to\mathcal{R}(\mathbf{X},\mathfrak{U};\alpha(r))$.
However, the carrier $\iota\circ\mathscr{C}$ does not carry the inclusion for
any simplices in $\mathcal{R}(\mathbf{X};r)$ that are not in the cover complex
$\mathcal{R}(\mathbf{X},\mathfrak{U};r)$. We need to find another carrier
which does carry the inclusion which also contains this carrier. Consider
$\mathcal{D}:R(\mathbf{X};r)\to\mathcal{R}(\mathbf{X};r)$, defined as

$\mathscr{D}:(x_{0},\dots,x_{k})\mapsto\langle\bar{\mathbf{X}}(x_{0},\dots,x_{k})\rangle.$
(23)

The difference between $\mathscr{C}$ and $\mathscr{D}$, despite the similarity
of their definitions is that they map to different complexes. $\mathscr{C}$
maps to subcomplexes of $\mathcal{R}(\mathbf{X},\mathfrak{U};r)$, and
$\mathscr{D}$ maps to subcomplexes of $\mathcal{R}(\mathbf{X};r)$. Note that
$\mathscr{D}$ does carry $\iota\circ\mathscr{C}$.

If $\mathscr{D}$ is also $\alpha$-acyclic, we can apply proposition 2.14 to
construct the interleaving. The remainder of this section describes conditions
that will allow us to bound the non-decreasing map $\alpha$.

######  Lemma 4.4.

If $(\mathbf{X},d)$ is a metric space, then $\mathcal{D}$ is acyclic for
$\alpha:r\mapsto 2r$.

###### Proof.

Consider $\mathcal{D}(x_{0},\dots,x_{k})$, and let
$r=d_{X}(x_{0},\dots,x_{k})$. Without loss of generality, consider distances
to $x_{0}$. Let $y\in\mathcal{D}(x_{0},\dots,x_{k})$. By definition of
$\mathscr{D}$, either $d(y,x_{0})\leq r$, or $d(y,x_{i})\leq r$ for some
$x_{i}\in\\{x_{1},\dots,x_{k}\\}$. Because $d_{X}(x_{0},x_{i})\leq r$, by
triangle inequality, $d(y,x_{0})\leq 2r$. Because the Vietoris-Rips complex is
a flag complex, this implies $\mathcal{D}(x_{0},\dots,x_{k})$ forms a cone
with $x_{0}$ at parameter $2r$ and so is acyclic. ∎

The more difficult carrier to analyze is $\mathscr{C}$. We’ll consider the
restriction of the cover to the carrier. If
$\mathcal{N}(\bar{\mathfrak{U}}(x_{0},\dots,x_{k}))$ is acyclic for each
$(x_{0},\dots,x_{k})\in\mathcal{R}(\mathbf{X};r)$, and
$\mathcal{R}(\bar{\mathbf{X}}(x_{0},\dots,x_{k}),V;r)$ is
$\alpha$-contractible, then $\mathscr{C}$ is $\alpha$-acyclic by the Nerve
theorem.

######  Lemma 4.5.

Let $r=d_{X}(x_{0},\dots,x_{k})$. For each
$V\in\bar{\mathfrak{U}}(x_{0},\dots,x_{k})$, $\mathcal{R}(V;3r)$ is
contractible.

###### Proof.

Let $y,y^{\prime}\in V$. Then there are some
$x,x^{\prime}\in\\{x_{0},\dots,x_{k}\\}$ for which
$d(y,x),d(y^{\prime},x^{\prime})\leq r$. Because $d(x,x^{\prime})\leq r$, by
triangle inequality $d(y,y^{\prime})\leq 3r$. Thus, $\mathcal{R}(V;3r)$ forms
a simplex, so is contractible. ∎

In general, the bound in lemma 4.5 can be pessimistic. For instance,

######  Lemma 4.6.

Let $r\leq R_{2}$, so that for $d_{X}(x_{0},\dots,x_{k})\leq r$,
$\mathbf{X}(x_{0},\dots,x_{k})\cap V$ is non-empty for each
$V\in\bar{\mathfrak{U}}(x_{0},\dots,x_{k})$. Then $\mathcal{R}(V;2r)$ is
contractible.

###### Proof.

Fix $V\in\bar{\mathfrak{U}}$. By assumption, there is some $y\in V$ so that
$d(y,x_{i})\leq r$ for all $i=0,\dots,k$. For some other $y^{\prime}\in V$, we
have $d(y,x_{i})\leq r$ for some $i=0,\dots,k$. By triangle inequality,
$d(y,y^{\prime})\leq 2r$. Since this holds for all $y^{\prime}\in V$,
$\mathcal{R}(V;2r)$ forms a cone with $y$, and is thus contractible. ∎

We can now tie things together in the following propositions.

######  Proposition 4.7.

$H_{k}(\mathcal{R}(\mathbf{X},\mathfrak{U};r))$ and
$H_{k}(\mathcal{R}(\mathbf{X};r))$ are $(\operatorname{id},2r)$-interleaved
for $r\leq R_{2}$.

######  Proposition 4.8.

$H_{k}(\mathcal{R}(\mathbf{X},\mathfrak{U};r))$ and
$H_{k}(\mathcal{R}(\mathbf{X};r))$ are $(\operatorname{id},3r)$-interleaved
for $r\leq R_{3}$.

###### Proof.

We use the approximate nerve theorem, theorem 3.8, to show that $\mathcal{C}$
is acyclic under the conditions of proposition 4.7 and proposition 4.8. By
definition of $R_{3}$, the nerve
$\mathcal{N}(\bar{\mathfrak{U}}(x_{0},\dots,x_{k}))$ is acyclic in both
propositions. lemma 4.6 or lemma 4.5 ensures that each set in the nerve is
$2r$ or $3r$ acyclic respectively, so the whole carrier is $2r$ or $3r$
acyclic respectively. ∎

Note that the sets in the covers $\mathfrak{U}$ do not need to be acyclic at
the levels prescribed, but rather their restriction to points within a certain
distance of each simplex. This means there can be a variety of non-trivial
structure in each set in the cover.

###  4.2 Sparse Filtrations via Covers

Theorem 4.2 can be applied to any cover $\mathfrak{U}$ of a data set
$\mathbf{X}$, and to a certain extent can guide the selection of a cover
$\mathfrak{U}$ that increases $R_{1},R_{2}$, and $R_{3}$ as much as possible:

  1. 1.

$R_{1}$ is determined by the threshold at which for all $x\in\mathbf{X}$,
there exists some set $\mathfrak{U}$ which contains all its $R_{1}$-nearest
neighbors.

  2. 2.

To maximize $R_{2}$, we want to ensure that the cover $\mathfrak{U}$ contains
witnesses to simplices. This may require sets covering large distances in
sparse regions.

  3. 3.

To maximize $R_{3}$, we want to make
$\mathcal{N}(\bar{\mathfrak{U}}(x_{0},\dots,x_{k}))$ acyclic for all simplices
$(x_{0},\dots,x_{k})$. This requires sufficient overlap of sets in cover.

If the goal is to construct a cover that gives an interleaving for all
filtration values, a practical approach is to construct a sparse filtration,
as originally proposed by Sheehy [32]. We consider a variant of this approach
using a Vietoris-Rips cover complex which is amenable to a straightforward
analysis. Another, more geometric, approach based on persistent nerves is
studied in [8]. The key differences between the approach here and [32, 8] are
that the Vietoris-Rips cover complexes are not generally flag complexes, and
that we do not consider re-weighting of edges to tighten the interleaving.

Consider a nested sequence of greedily chosen landmark sets
$\mathbf{L}_{0}\subset\mathbf{L}_{1}\subset\dots\subset\mathbf{L}_{n}=\mathbf{X}$,
so $\mathbf{L}_{i}=\mathbf{L}_{i-1}\cup\\{x_{i}\\}$ where $x_{0}$ can be
chosen arbitrarily, and $x_{i}\in\mathbf{X}$ is a point that realizes the
Hausdorff distance $d_{H}(\mathbf{L}_{i-1},\mathbf{X})$. Let
$\lambda_{i}=d_{H}(\mathbf{L}_{i-1},\mathbf{X})$, with $\lambda_{0}=\infty$,
and let $c>1$ be a fixed constant. We construct a cover $\mathfrak{U}$ of the
data set $\mathbf{X}$ by associating a set $U_{x}$ to each element
$x\in\mathbf{X}$

$U_{x}=\bigcup_{i=1}^{n}\\{\ell\in\mathbf{L}_{i}\mid d(\ell,x)\leq
c\lambda_{i}\\}.$ (24)

Each set is non empty because $x\in\mathbf{L}_{n}$ and $d(x,x)=0$ implies
$x\in U_{x}$. Furthermore, the Nerve of the cover $\mathcal{N}(\mathfrak{U})$
is acyclic, as the single point $x_{0}$ contained in $\mathbf{L}_{0}$ is
contained in every set, every intersection of sets in $\mathfrak{U}$ is non-
empty.

######  Lemma 4.9.

Let $x_{0},\dots,x_{q}\in\mathbf{X}$, with $d(x_{0},\dots,x_{q})=r$. Then for
any $\lambda_{i}\geq\frac{r}{c-1}$, there exists some $\ell\in\mathbf{L}_{i}$
so that $\ell\in\cap_{i=0}^{k}U_{x_{i}}$.

###### Proof.

We consider a landmark set $\mathbf{L}\subseteq\mathbf{X}$ with
$d_{H}(\mathbf{L},\mathbf{X})=\epsilon$. Without loss of generality, we take
the point $x_{0}$, for which there must exists some $\ell\in\mathbf{L}$ such
that $d(x_{0},\ell)\leq\epsilon$ by the Hausdorff distance bound, so $\ell\in
U_{x_{0}}$. In order to guarantee that $\ell$ is in $U_{x_{i}},i=1,\dots,q$,
we must satisfy

$\displaystyle d(x_{i},\ell)\leq d(x_{i},x_{0})+d(x_{0},\ell)$
$\displaystyle\leq c\epsilon$ $\displaystyle r+\epsilon$ $\displaystyle\leq
c\epsilon$ $\displaystyle r$ $\displaystyle\leq(c-1)\epsilon$
$\displaystyle\epsilon$ $\displaystyle\geq\frac{r}{c-1}$

Thus, for any $\mathbf{L}_{i}$ with
$\lambda_{i}=d_{H}(\mathbf{L}_{i-1},\mathbf{X})\geq\frac{r}{c-1}$, there
exists such an $\ell$. ∎

######  Lemma 4.10.

Let $x_{0},\dots,x_{q}\in\mathbf{X}$, with $d(x_{0},\dots,x_{q})=r$, and let
$i$ be the index such that $\lambda_{i}\geq\frac{r}{c-1}$ and
$\lambda_{i+1}<\frac{r}{c-1}$, then there exist
$\ell_{j}\in\mathbf{L}_{i},j=0,1,\dots,q$ such that
$d(x_{j},\ell_{j})\leq\lambda_{i+1}<\frac{r}{c-1}$.

###### Proof.

We have that $\lambda_{i+1}=d_{H}(\mathbf{L}_{i},\mathbf{X})<\frac{r}{c-1}$,
so for all $x\in\mathbf{X}$, there is some $\ell\in\mathbf{L}_{i}$ so that
$d(x,\ell)\leq\lambda_{i+1}<\frac{r}{c-1}$. ∎

######  Proposition 4.11.

Let $x_{0},\dots,x_{q}\in\mathbf{X}$, with $d(x_{0},\dots,x_{q})=r$. Then
there exists an $\ell\in\cap_{j=0}^{q}U_{x_{j}}$ with
$d(x_{j},\ell)\leq\frac{cr}{c-1}$ for all $j=0,\dots,q$.

###### Proof.

Let $i$ be the index such that $\lambda_{i}\geq\frac{r}{c-1}$ and
$\lambda_{i+1}<\frac{r}{c-1}$. From lemma 4.10, there is an
$\ell\in\mathbf{L}_{i}$ with $d(\ell,x_{0})<\frac{r}{c-1}$, and since
$\mathbf{L}_{i}\geq\frac{r}{c-1}$, $\ell\in U_{x_{0}}$. Now, from lemma 4.9,
such an $\ell$ is also in $U_{x_{j}}$ for $j=1,\dots,q$. ∎

This motivates the construction of a carrier
$\mathscr{C}:\mathcal{R}(\mathcal{X};r)\to\mathcal{R}(\mathcal{X},\mathfrak{U};r)$.
Let

$\mathscr{C}(x_{0},\dots,x_{q})=\bigg{\langle}\\{\ell(x_{0},\dots,x_{q})\\}\cup\bigcup_{\sigma\in\mathcal{P}(x_{0},\dots,x_{k})}\mathscr{C}(\sigma)\bigg{\rangle}$
(25)

where $\ell(x_{0},\dots,x_{q})$ is an arbitrary choice of $\ell$ which
satisfies proposition 4.11.

######  Proposition 4.12.

Let $d(x_{0},\dots,x_{q})=r$. Then the carrier in eq. 18 is acyclic at level
$\frac{2c}{c-1}r$.

###### Proof.

We consider when the carrier forms a cone with $\ell=\ell(x_{0},\dots,x_{q})$,
which is in every set $U_{x_{i}}$. Let $y$ be a point in
$\mathscr{C}(x_{0},\dots,x_{q})$. Either $y$ is one of $x_{0},\dots,x_{q}$, or
it was included as $\ell(\sigma)$ for some
$\sigma\subset\\{x_{0},\dots,x_{q}\\}$. Because $d(\sigma)\leq
d(x_{0},\dots,x_{q})$, This means that $d(y,x_{j})\leq\frac{c}{c-1}r$ for any
$x_{j}\in\sigma$. We can then bound using triangle inequality

$\displaystyle d(y,\ell)$ $\displaystyle\leq d(y,x_{j})+d(x_{j},\ell)$ (26)
$\displaystyle\leq\frac{c}{c-1}r+\frac{c}{c-1}r$ (27)
$\displaystyle\leq\frac{2c}{c-1}r.$ (28)

Because this holds for any point $y$ in the carrier,
$\mathscr{C}(x_{0},\dots,x_{q})$ forms a cone by level $\frac{2c}{c-1}r$, so
is acyclic. ∎

If we wish to obtain a $\alpha=1+\epsilon$ interleaving, we can calculate that
we must set $c=\frac{\epsilon+1}{\epsilon-1}$. In the limit of $c\to\infty$,
$\epsilon\to 1$ from above, so we are limited to $\alpha>2$ using this
strategy. We can achieve $\alpha=3$ by setting $c=3$, which limits the size of
the sets in the cover while achieving a relatively small multiplicative
interleaving bound. A tighter bound can be achieved by re-weighting edges with
distance $\geq\frac{c}{c-1}r$ in proposition 4.12 – see [32, 8] for details.

##  5 Computations

In this section, we demonstrate the use of Vietoris-Rips cover complexes in
studying the homology of point cloud data. We first examine how several
different covers can be used to investigate the homology of a sample from the
torus. Next, we use the greedy landmark cover of section 4.2 to investigate
the homology of $d$-dimensional Klein bottles associated with high-dimensional
image patches. We have incorporated an implementation of the Vietoris-Rips
cover complex into the BATS software111https://github.com/CompTop/BATS package
[5] to support our experiments.

###  5.1 A Flat Torus

For our first example, we sample 500 points in a spiral on a flat torus in 4
dimensions. For intermediate parameters of a filtration, we expect to
generally see the homology of the torus $T^{2}$

$H_{q}(T^{2})=\begin{cases}\mathbb{F}&q=0\\\ \mathbb{F}\oplus\mathbb{F}&q=1\\\
\mathbb{F}&q=2\end{cases}$ (29)

with coefficients in any field.

Figure 1:  Cover of a flat torus pulled back from projection onto the first
coordinate and the persistence diagram of
$\mathcal{R}(\mathbf{X},\mathfrak{U};r)$. The Nerve of the cover is
contractible, as it covers an interval. We see a single essential $H_{0}$
class (above the dashed red line), two persistent $H_{1}$ classes, and a
persistent $H_{2}$ class.

In fig. 1, we pull back a cover of an interval in one dimension covering the
projection of the data set onto the first coordinate. In this case, each set
in the cover has non-trivial structure - generally two robust connected
components and two robust generators in $H_{1}$. However, the persistent
homology of the cover complex $\mathcal{R}(\mathbf{X},\mathfrak{U};r)$
demonstrates robust generators corresponding to the homology of the torus.

Figure 2:  Cover of a flat torus pulled back from projection onto first two
coordinates and the persistence diagram of
$\mathcal{R}(\mathbf{X},\mathfrak{U};r)$. The nerve of the cover is homotopic
to the circle, and we see essential $H_{0}$ and essential $H_{1}$ classes from
the nerve of this cover. We also see an additional persistent $H_{1}$ class
and persistent $H_{2}$ class.

In fig. 2, we pull back a cover of the the data set projected onto its first
two coordinates. In this case, the nerve of the cover is homotopic to a
circle, and each set in the cover has points that lie in a circle. In this
case, the cover complex $\mathcal{R}(\mathbf{X},\mathfrak{U};r)$ has prominent
homology classes for each class in the torus, but the the classes coming from
the nerve of the cover are essential.

Figure 3:  Cover of a flat torus obtained from the 20-nearest neighbors of
each point and the persistence diagram of
$\mathcal{R}(\mathbf{X},\mathfrak{U};r)$. The nerve of the cover is homotopic
to the torus, and we see essential homology classes corresponding to the
homology of the torus.

In fig. 3, instead of a pullback cover we simply produce a cover containing a
set for every point $x\in\mathcal{X}$ containing $x$ itself and its 20 nearest
neighbors. In this case, all sets are close to acyclic, but the nerve of the
cover is equivalent to the torus, which we see reflected in the essential
homology classes in the persistence diagram.

Figure 4:  Cover of the flat torus based on the procedure in section 4.2 and
the persistence diagram of $\mathcal{R}(\mathbf{X},\mathfrak{U};r)$. The Nerve
is contractible, and so we just see a single essential $H_{0}$ class. We also
see two persistent $H_{1}$ classes and a persistent $H_{2}$ class.

In fig. 4 we construct a cover of the data using the procedure in section 4.2
with $c=1.0$ for maximum sparsity. While this low value of $c$ gives a very
pessimistic interleaving bound, each set in the cover is quite small,
averaging less than $20$ points, and we still see the homology of the torus
reflected in the prominent homology classes of the persistence diagram of
$\mathcal{R}(\mathbf{X},\mathfrak{U};r).$

###  5.2 $d$-Dimensional Klein bottles

An interesting space motivated by data which admits a non-trivial fibration
structure is a Klein bottle which lies near a high-density subset of high-
contrast image patches [6]. The fibration map can be obtained using the Harris
edge detector [19, 29] which sends an image patch to the direction of largest
variation.

In [27], this model is generalized to higher-dimensional images to obtain a
fibration over $\mathbb{R}P^{d-1}$ for $d$-dimensional images. We will refer
to this space as the $d$-dimensional Klein bottle, $\mathcal{K}^{d}$, which
was described independently in a different context by Davis [14]. The homology
of this space can be computed using the Leray-Serre spectral sequence [24] –
see [27] for explicit computational details.

$H_{k}(\mathcal{K}^{d})=\begin{cases}\mathbb{Z}&k=0\\\
\mathbb{Z}_{2}\oplus\mathbb{Z}_{2}&0<k<d-1,~{}k~{}\text{odd}\\\
\mathbb{Z}&k=d,~{}d~{}\text{odd}\\\
\mathbb{Z}\oplus\mathbb{Z}_{2}&k=d-1,~{}d~{}\text{even}\\\
0&\text{otherwise}\end{cases}$ (30)

Using the universal coefficient theorem (c.f. [20], 3A.3), we see different
dimensions in homology when computing with fields of different characteristic
due to the 2-torsion in the integral homology of $\mathcal{K}^{d}$

$H_{k}(\mathcal{K}^{d};\mathbb{F}_{2})=\begin{cases}\mathbb{F}_{2}&k=0,d~{}\text{odd}\\\
\mathbb{F}_{2}\oplus\mathbb{F}_{2}&0<k<d\\\ \mathbb{F}_{2}&k=d\\\
0&\text{otherwise}\end{cases}$ (31)

and for $\mathbb{F}=\mathbb{F}_{p}$, $p>2$, or $\mathbb{F}=\mathbb{Q}$, we
have

$H_{k}(\mathcal{K}^{d};\mathbb{F})=\begin{cases}\mathbb{F}&k=0\\\
\mathbb{F}&k=d-1,d~{}\text{even}\\\ \mathbb{F}&k=d,d~{}\text{odd}\\\
0&\text{otherwise}\end{cases}$ (32)

Figure 5:  Persistent homology of a 2-dimensional Klein bottle,
$\mathcal{K}^{2}$. Left: with $\mathbb{F}_{2}$ field coefficients. Right: with
$\mathbb{F}_{3}$ field coefficients. There are two robust $H_{1}$ generators
with $\mathbb{F}_{2}$ coefficients at the location $(0.1,0.8)$.

Figure 6:  Persistent homology of a 3-dimensional Klein bottle,
$\mathcal{K}^{3}$. Left: with $\mathbb{F}_{2}$ field coefficients. Right: with
$\mathbb{F}_{3}$ field coefficients.

We obtain a sample of $\mathcal{K}^{d}$ generalizing the model of Carlsson et
al [6]. Given a unit vector $v_{\phi}\in\mathbb{R}^{d}$ and an angle $\theta$,
we define a patch

$p(x;\theta,v_{\phi})=\cos(\theta)(x^{T}v_{\phi})^{2}+\sin(\theta)(x^{T}v_{\phi})$
(33)

which can be evaluated as a pixelated image patch by evaluating
$x\in\mathbb{R}^{d}$ on a grid. In fig. 5 we generate a Klein bottle
$\mathcal{K}^{2}$ on $3\times 3$ image patches by evaluating $x$ on the grid
$\\{-1,0,1\\}^{2}$, 20 equally spaced values of $\theta$, and $50$ equally
spaced values of $v_{\phi}$ for a total of 1000 points in $\mathbb{R}^{9}$. We
compute persistent homology of the cover complex filtration
$\mathcal{R}(\mathbf{X},\mathfrak{U};r)$ using the landmark-based cover in
section 4.2, with $c=1.0$ for maximum sparsity. Using eq. 31, the homology of
$\mathcal{K}^{2}$ with coefficients in $\mathbb{F}^{2}$ has has dimension
vector $(1,2,1)$, which is clearly observed in the persistence diagram. In eq.
32, coefficients in $\mathbb{F}^{3}$, the dimension vector becomes $(1,1,0)$,
and we see one of the prominent $H_{1}$ classes shrink, and the prominent
$H_{2}$ class shift toward the diagonal in the corresponding persistence
diagram.

In fig. 6, we generate $\mathcal{K}^{3}$ on $5\times 5\times 5$ patches using
$20$ equally-spaced values of $\theta$ and $150$ values of $v_{\phi}$ chosen
by greedily landmarking a larger set of $4000$. The total data set consists of
3000 points in $\mathbb{R}^{125}$, and again we compute persistent homology of
the cover complex filtration $\mathcal{R}(\mathbf{X},\mathfrak{U};r)$ using
the landmark-based cover in section 4.2, with $c=1.0$. Using eq. 31, the
homology dimension vector of this space in $\mathbb{F}^{2}$ is (1,2,2,1), and
for $\mathbb{F}^{3}$ coefficents, the dimension vector is $(1,0,0,1)$. In fig.
6 we see both these dimension vectors match with the prominent homology
classes in each dimension.

##  6 Conclusion

In this paper, we developed a filtered version of the acyclic carrier theorem,
which allowed us to construct interleavings between different geometric
constructions. We have presented several results for Vietoris-Rips cover
complexes, and we anticipate that the use of filtered carriers has broad
potential as a technique to construct interleavings in situations that we have
not yet considered. We have focused on algebraic interleavings, and many of
these results could potentially be extended to homotopy interleavings [1]
given additional care when constructing carriers of cell complexes. Another
interesting line of future investigation would be to use the algorithmic
construction of maps from carriers in data analysis. This could potentially be
used, for instance, in constructing low dimensional embeddings of data that
minimize the interleaving distance between a filtration on the higher-
dimensional point cloud and the embedded point cloud.

Another line of future work is to leverage cover complexes for distrubyted
computation. A limited version of this was explored in [35], and our
interleaving results expand the potential use of cover complexes to more
general settings. We also believe that the interleaving bounds we derive are
likely pessimistic in many situations where data has additional structure.
Analyses of these situations may help tighten our bounds considerably.

## Acknowledgements

BJN was supported by the Defense Advanced Research Projects Agency (DARPA)
under Agreement No. HR00112190040. He thanks Gunnar Carlsson and Jonathan
Taylor for discussions on a early version of this work.

## References

  * [1] Blumberg, A.J., Lesnick, M.: Universality of the Homotopy Interleaving Distance.  arXiv:1705.01690 [cs, math] (2017)
  * [2] Borsuk, K.: On the imbedding of systems of compacta in simplicial complexes.  Fundamenta Mathematicae 35, 217–234 (1948)
  * [3] Cang, Z., Wei, G.W.: TopologyNet: Topology based deep convolutional and multi-task neural networks for biomolecular property predictions.  PLOS Computational Biology 13(7), e1005690 (2017).  DOI 10.1371/journal.pcbi.1005690.  URL http://dx.plos.org/10.1371/journal.pcbi.1005690
  * [4] Carlsson, G.: Topological pattern recognition for point cloud data.  Acta Numerica 23, 289–368 (2014).  DOI 10.1017/S0962492914000051.  URL https://www.cambridge.org/core/product/identifier/S0962492914000051/type/journal_article
  * [5] Carlsson, G., Dwaraknath, A., Nelson, B.J.: Persistent and Zigzag Homology: A Matrix Factorization Viewpoint (2019).  Preprint: https://arxiv.org/abs/1911.10693
  * [6] Carlsson, G., Ishkhanov, T., de Silva, V., Zomorodian, A.: On the local behavior of spaces of natural images.  International Journal of Computer Vision 76(1), 1–12 (2008).  DOI 10.1007/s11263-007-0056-x.  URL http://dx.doi.org/10.1007/s11263-007-0056-x
  * [7] Carlsson, G., de Silva, V.: Zigzag persistence.  Foundations of Computational Mathematics 10(4), 367–405 (2010).  DOI 10.1007/s10208-010-9066-0.  URL http://link.springer.com/10.1007/s10208-010-9066-0
  * [8] Cavanna, N.J., Jahanseir, M., Sheehy, D.R.: A Geometric Perspective on Sparse Filtrations.  In: Canadian Conference on Computational Geometry, p. 6 (2015)
  * [9] Cavanna, N.J., Sheehy, D.R.: The generalized persistent nerve theorem (2018).  Preprint: http://arxiv.org/abs/1807.07920
  * [10] Chazal, F., Cohen-Steiner, D., Glisse, M., Guibas, L.J., Oudot, S.Y.: Proximity of persistence modules and their diagrams.  In: Proceedings of the 25th annual symposium on Computational geometry - SCG ’09, p. 237. ACM Press (2009).  DOI 10.1145/1542362.1542407.  URL http://portal.acm.org/citation.cfm?doid=1542362.1542407
  * [11] Chazal, F., Cohen-Steiner, D., Guibas, L.J., Mémoli, F., Oudot, S.Y.: Gromov-hausdorff stable signatures for shapes using persistence.  Computer Graphics Forum 28(5), 1393–1403 (2009).  DOI 10.1111/j.1467-8659.2009.01516.x.  URL http://dx.doi.org/10.1111/j.1467-8659.2009.01516.x
  * [12] Chazal, F., Oudot, S.Y.: Towards persistence-based reconstruction in euclidean spaces.  In: Proceedings of the twenty-fourth annual symposium on Computational geometry - SCG ’08, p. 232. ACM Press (2008).  DOI 10.1145/1377676.1377719.  URL http://portal.acm.org/citation.cfm?doid=1377676.1377719
  * [13] Chazal, F., de Silva, V., Oudot, S.: Persistence stability for geometric complexes.  Geometriae Dedicata 173, 193–214 (2014)
  * [14] Davis, D.M.: An n-dimensional Klein bottle.  Proceedings of the Royal Society of Edinburgh Section A: Mathematics 149(5), 1207–1221 (2019).  DOI 10.1017/prm.2018.73.  Publisher: Royal Society of Edinburgh Scotland Foundation
  * [15] Dey, T.K., Mémoli, F., Wang, Y.: Multiscale mapper: Topological summarization via codomain covers.  In: Proceedings of the twenty-seventh annual ACM-SIAM symposium on discrete algorithms, pp. 997–1013. SIAM (2016)
  * [16] Eilenberg, S., Steenrod, N.E.: Foundations of Algebraic Topology.  Princeton Mathematical Series. Princeton University Press (1952)
  * [17] Gabriel, P.: Unzerlegbare darstellungen I.  Manuscripta Mathematica 6, 71–103 (1972)
  * [18] Govc, D., Skraba, P.: An approximate nerve theorem.  Foundations of Computational Mathematics 18, 1245–1297 (2017).  DOI 10.1007/s10208-017-9368-6.  URL http://link.springer.com/10.1007/s10208-017-9368-6
  * [19] Harris, C., Stephens, M.: A Combined Corner and Edge Detector.  In: Alvey Vision Conference, pp. 23.1–23.6 (1988).  DOI 10.5244/C.2.23.  URL http://www.bmva.org/bmvc/1988/avc-88-023.html
  * [20] Hatcher, A.: Algebraic Topology.  Cambridge University Press (2002)
  * [21] Hiraoka, Y., Nakamura, T., Hirata, A., Escolar, E.G., Matsue, K., Nishiura, Y.: Hierarchical structures of amorphous solids characterized by persistent homology.  Proceedings of the National Academy of Sciences (2016).  DOI 10.1073/pnas.1520877113.  URL https://www.pnas.org/content/early/2016/06/07/1520877113.  Publisher: National Academy of Sciences Section: Physical Sciences
  * [22] Lesnick, M.: The theory of the interleaving distance on multidimensional persistence modules.  Foundations of Computational Mathematics 15, 613–650 (2015)
  * [23] May, J.P., Sigurdsson, J.: Parametrized Homotopy Theory.  No. v. 132 in Mathematical Surveys and Monographs. American Mathematical Society, Providence, R.I (2006)
  * [24] McCleary, J.: A User’s Guide to Spectral Sequences.  Cambridge Studies in Advanced Mathematics. Cambridge University Press (2001)
  * [25] Mosher, R., Tangora, M.: Cohomology Operations and Applications in Homotopy Theory.  Harper’s Series in Modern Mathematics. Harper & Row (1968)
  * [26] Munkres, J.R.: Elements of Algebraic Topology.  Addison-Wesley Publishing Company (1984)
  * [27] Nelson, B.: Parameterized topological data analysis.  Ph.D. thesis, Stanford University (2020).  URL https://purl.stanford.edu/kn625zh9782
  * [28] Oudot, S.Y.: Persistence Theory: From Quiver Representations to Data Analysis, _Mathematical Surveys and Monographs_ , vol. 209.  American Mathematical Society (2015)
  * [29] Perea, J., Carlsson, G.: A klein-bottle-based dictionary for texture representation.  International Journal of Computer Vision 107(1), 75–97 (2014)
  * [30] Roweis, S.T., Saul, L.K.: Nonlinear Dimensionality Reduction by Locally Linear Embedding.  Science 290(5500), 2323–2326 (2000).  DOI 10.1126/science.290.5500.2323.  Publisher: American Association for the Advancement of Science
  * [31] Serre, J.P.: Homologie singuliere des espaces fibres.  The Annals of Mathematics 54(3), 425 (1951).  DOI 10.2307/1969485
  * [32] Sheehy, D.R.: Linear-size approximations to the vietoris–rips filtration.  Discrete & Computational Geometry 49(4), 778–796 (2013).  DOI 10.1007/s00454-013-9513-1.  URL http://link.springer.com/10.1007/s00454-013-9513-1
  * [33] Singh, G., Memoli, F., Carlsson, G.: Topological Methods for the Analysis of High Dimensional Data Sets and 3D Object Recognition.  In: M. Botsch, R. Pajarola, B. Chen, M. Zwicker (eds.) Eurographics Symposium on Point-Based Graphics. The Eurographics Association (2007).  DOI 10.2312/SPBG/SPBG07/091-100
  * [34] Tenenbaum, J.B., de Silva, V., Langford, J.C.: A Global Geometric Framework for Nonlinear Dimensionality Reduction.  Science 290(5500), 2319–2323 (2000).  DOI 10.1126/science.290.5500.2319
  * [35] Yoon, H.R.: Cellular sheaves and cosheaves for distributed topological data analysis.  Ph.D. dissertation, University of Pennsylvania (2018)
  * [36] Zomorodian, A., Carlsson, G.: Computing persistent homology.  Discrete & Computational Geometry 33(2), 249–274 (2005).  DOI 10.1007/s00454-004-1146-y