# A Framework for Fast and Stable Representations of Multiparameter Persistent
Homology Decompositions

David Loiseaux1, Mathieu Carrière1, Andrew J. Blumberg2
1DataShape, Centre Inria d’Université Côte d’Azur 2Mathematics, Columbia
University

###### Abstract

Topological data analysis (TDA) is an area of data science that focuses on
using invariants from algebraic topology to provide multiscale shape
descriptors for geometric data sets such as point clouds. One of the most
important such descriptors is persistent homology, which encodes the change in
shape as a filtration parameter changes; a typical parameter is the feature
scale. For many data sets, it is useful to simultaneously vary multiple
filtration parameters, for example feature scale and density. While the
theoretical properties of single parameter persistent homology are well
understood, less is known about the multiparameter case. In particular, a
central question is the problem of representing multiparameter persistent
homology by elements of a vector space for integration with standard machine
learning algorithms. Existing approaches to this problem either ignore most of
the multiparameter information to reduce to the one-parameter case or are
heuristic and potentially unstable in the face of noise. In this article, we
introduce a new general representation framework that leverages recent results
on decompositions of multiparameter persistent homology. This framework is
rich in information, fast to compute, and encompasses previous approaches.
Moreover, we establish theoretical stability guarantees under this framework
as well as efficient algorithms for practical computation, making this
framework an applicable and versatile tool for analyzing geometric and point
cloud data. We validate our stability results and algorithms with numerical
experiments that demonstrate statistical convergence, prediction accuracy, and
fast running times on several real data sets.

##  1 Introduction

Topological Data Analysis (TDA) [8] is a methodology for analyzing data sets
using multiscale shape descriptors coming from algebraic topology. There has
been intense interest in the field in the last decade, since topological
features promise to allow practitioners to compute and encode information that
classical approaches do not capture. Moreover, TDA rests on solid theoretical
grounds, with guarantees accompanying many of its methods and descriptors. TDA
has proved useful in a wide variety of application areas, including computer
graphics [17, 33], computational biology [34], and material science [2, 35],
among many others.

The main tool of TDA is persistent homology. In its most standard form, one is
given a finite metric space $X$ (e.g., a finite set of points and their
pairwise distances) and a continuous function $f:X\rightarrow\mathbb{R}$. This
function usually represents a parameter of interest (such as, e.g., scale or
density for point clouds, marker genes for single-cell data, etc), and the
goal of persistent homology is to characterize the topological variations of
this function on the data at all possible scales. Of course, the idea of
considering multiscale representations of geometric data is not new [18, 32,
40]; the contribution of persistent homology is to obtain a novel and
theoretically tractable multiscale shape descriptor. More formally, persistent
homology is achieved by computing the so-called persistence barcode of $f$,
which is obtained by looking at all sublevel sets of the form
$\\{f^{-1}((-\infty,\alpha])\\}_{\alpha\in\mathbb{R}}$, also called filtration
induced by $f$, and by computing a decomposition of this filtration, that is,
by recording the appearances and disappearances of topological features
(connected components, loops, enclosed spheres, etc) in these sets. When such
a feature appears (resp. disappears), e.g., in a sublevel set
$f^{-1}((-\infty,\alpha_{b}])$, we call the corresponding threshold
$\alpha_{b}$ (resp. $\alpha_{d}$) the birth time (resp. death time) of the
topological feature, and we summarize this information in a set of intervals,
or bars, called the persistence barcode
$D(f):=\\{(\alpha_{b},\alpha_{d})\\}_{\alpha\in
A}\subset\mathbb{R}\times\mathbb{R}\cup\\{\infty\\}$. Moreover, the bar length
$\alpha_{d}-\alpha_{b}$ often serves as a proxy for the statistical
significance of the corresponding feature.

However, an inherent limitation of the formulation of persistent homology is
that it can handle only a single filtration parameter $f$. However, in
practice it is common that one has to deal with multiple parameters. This
translates into multiple filtration functions: a standard example is  when one
aims at obtaining meaningful topological representation of a noisy point
cloud. In this case, both feature scale and density functions are necessary
(see Appendix A). An extension of persistent homology to several filtration
functions is called multiparameter persistent homology [5, 19], and studies
the topological variations of a continuous multiparameter function
$f:X\rightarrow\mathbb{R}^{n}$ with $n\in\mathbb{N}^{*}$. This setting is
notoriously difficult to analyze theoretically as there is no result ensuring
the existence of an analogue of persistence barcodes, i.e., a decomposition
into subsets of $\mathbb{R}^{n}$, each representing the lifespan of a
topological feature.

Still, it remains possible to define weaker topological invariants in this
setting. The most common one is the so-called rank invariant (as well as its
variations, such as the generalized rank invariant [23], and its
decompositions, such as the signed barcodes [6]), which describes how the
topological features associated to any pair of sublevel sets $\\{x\in
X:f(x)\leq\alpha\\}$ and $\\{x\in X:f(x)\leq\beta\\}$ such that
$\alpha\leq\beta$ (w.r.t. the partial order in $\mathbb{R}^{n}$), are
connected. The rank invariant is a construction in abstract algebra, and so
the task of finding appropriate representations of this invariant, i.e.,
embeddings into Hilbert spaces, is critical. Hence, a number of such
representations have been defined, which first approximate the rank invariant
by computing persistence barcodes from several linear combinations of
filtrations (often called the fibered barcode), and then aggregate known
single-parameter representations for them [13, 7, 39]. This procedure has also
been generalized recently [41].

However, the rank invariant, and its associated representations, are known to
be much less informative than decompositions (when they exist): many functions
have different decompositions yet the same rank invariants. Therefore, the
aforementioned representations can encode only limited multiparameter
topological information. Instead, in this work, we focus on candidate
decompositions of the function, in order to create descriptors that are
strictly more powerful than the rank invariant. Indeed, while there is no
general decomposition theorem, there is recent work that constructs candidate
decompositions in terms of simple pieces [1, 15, 26] that always exist but do
not necessarily suffice to reconstruct all of the multiparameter information.
Nonetheless, they are strictly more informative than the rank invariant under
mild conditions, are stable, and approximate the true decomposition when it
exists111Note that although multiparameter persistent homology can always be
decomposed as a sum of indecomposable pieces (see [5, Theorem 4.2] and [21]),
these decompositions are prohibitively difficult to interpret and work with..
For instance, in Figure 2, we present a bifiltration of a noisy point cloud
with scale and density (left), and a corresponding candidate decomposition
comprised of subsets of $\mathbb{R}^{2}$, each representing a topological
feature (middle). For instance, there is a large green subset in the
decomposition that represents the circle formed by the points that are not
outliers (also highlighted in green in the bifiltration).

Figure 1: Common pipelines for the use of multiparameter persistent homology
in data science—our work provides new contributions to the arrow highlighted
in red.

Unfortunately, while more informative, candidate decompositions suffer from
the same problem than the rank invariant; they also need appropriate
representations in order to be processed by standard methods. In this work, we
bridge this gap by providing new representations designed for candidate
decompositions. See Figure 1 for a summarizing figure.

Figure 2: (left) Bi-filtration of a noisy point cloud induced by both feature
scale (using unions of balls with increasing radii) and (co)density. The cycle
highlighted in the green zone can be detected as a large subset in the
corresponding candidate decomposition computed by the MMA method [26]
(middle), and in our representation of it (right).

#### Contributions.

Our contributions in this work are listed below:

  * •

We provide a general framework that parametrizes representations of
multiparameter persistent homology decompositions (Definition 1) and which
encompasses previous approaches in the literature. These representations take
the form of a parametrized family of continuous functions on $\mathbb{R}^{n}$
that can be binned into images for visualization and data science.

  * •

We identify parameters in this framework that result in representations that
have stability guarantees while still encoding more information than the rank
invariant (see Theorem 1).

  * •

We illustrate the performance of our framework with numerical experiments: (1)
We demonstrate the practical consequences of the stability theorem by
measuring the statistical convergence of our representations. (2) We achieve
the best performance with the lowest runtime on several classification tasks
on public data sets (see Sections 4.1 and 4.3).

#### Related work.

Closely related to our method is the recent contribution [9], which also
proposes a representation for decompositions. However, their approach, while
being efficient in practice, is a heuristic with no corresponding mathematical
guarantees. In particular, it is known to be unstable: similar decompositions
can lead to very different representations, as shown in Appendix B. Our
approach can be understood as a subsequent generalization of the work of [9],
with new mathematical guarantees that allow to derive, e.g., statistical rates
of convergence.

#### Outline.

Our work is organized as follows. In Section 2, we recall the basics of
multiparameter persistent homology. Next, in Section 3 we present our general
framework and state our associated stability result. Finally, we showcase the
numerical performances of our representations in Section 4, and we conclude in
Section 5.

##  2 Background

In this section, we briefly recall the basics of single and multiparameter
persistent homology, and refer the reader to Appendix C and [31, 34] for a
more complete treatment.

#### Persistent homology.

The basic brick of persistent homology is a filtered topological space $X$, by
which we mean a topological space $X$ together with a function $f\colon
X\to\mathbb{R}$ (for instance, in Figure 5, $X=\mathbb{R}^{2}$ and $f=f_{P}$).
Then, given $\alpha>0$, we call $F(\alpha):=f^{-1}((-\infty,\alpha])\subseteq
X$ the sublevel set of $f$ at level $\alpha$. Given levels
$\alpha_{1}\leq\dots\leq\alpha_{n}$, the corresponding sublevel sets are
nested w.r.t. inclusion, i.e., one has $F(\alpha_{1})\subseteq
F(\alpha_{2})\subseteq\ldots\subseteq F(\alpha_{i})\subseteq\ldots\subseteq
F(\alpha_{n})$. This system is an example of filtration of $X$, where a
filtration is generally defined as a sequence of nested subspaces
$X_{1}\subseteq\ldots\subseteq X_{i}\subseteq\ldots\subseteq X$. Then, the
core idea of persistent homology is to apply the $k$th homology functor
$H_{k}$ on each $F(\alpha_{i})$. We do not define the homology functor
explicitly here, but simply recall that each $H_{k}(F(\alpha_{i}))$ is a
vector space, whose basis elements represent the $k$th dimensional topological
features of $F(\alpha_{i})$ (connected components for $k=0$, loops for $k=1$,
spheres for $k=2$, etc). Moreover, the inclusions $F(\alpha_{i})\subseteq
F(\alpha_{i+1})$ translate into linear maps $H_{k}(F(\alpha_{i}))\to
H_{k}(F(\alpha_{i+1}))$, which connect the features of $F(\alpha_{i})$ and
$F(\alpha_{i+1})$ together. This allows to keep track of the topological
features in the filtration, and record their levels, often called times, of
appearance and disappearance. More formally, such a sequence of vector spaces
connected with linear maps ${\mathbb{M}}=H_{*}(F(\alpha_{1}))\to\dots\to
H_{*}(F(\alpha_{n}))$ is called a persistence module, and the standard
decomposition theorem [12, Theorem 2.8] states that this module can always be
decomposed as
${\mathbb{M}}=\oplus_{i=1}^{m}\mathbb{I}[\alpha_{b_{i}},\alpha_{d_{i}}]$,
where $\mathbb{I}[\alpha_{b_{i}},\alpha_{d_{i}}]$ stands for a module of
dimension 1 (i.e., that represents a single topological feature) between
$\alpha_{b_{i}}$ and $\alpha_{d_{i}}$, and dimension 0 (i.e., that represents
no feature) elsewhere. It is thus convenient to summarize such a module with
its persistence barcode
$D({\mathbb{M}})=\\{[\alpha_{b_{i}},\alpha_{d_{i}}]\\}_{1\leq i\leq m}$. Note
that in practice, one is only given a sampling of the topological space $X$,
which is usually unknown. In that case, persistence barcodes are computed
using combinatorial models of $X$ computed from the data, called simplicial
complexes. See Appendix C.

#### Multiparameter persistent homology.

The persistence modules defined above extend straightforwardly when there are
multiple filtration functions. An $n$-filtration, or multifiltration, induced
by a function $f:X\rightarrow\mathbb{R}^{n}$, is the family of sublevel sets
$F=\\{F(\alpha)\\}_{\alpha\in\mathbb{R}^{n}}$, where $F(\alpha):=\\{x\in
X:f(x)\leq\alpha\\}$ and $\leq$ denotes the partial order of $\mathbb{R}^{n}$.
Again, applying the homology functor $H_{k}$ on the multifiltration $F$
induces a multiparameter persistence module ${\mathbb{M}}$. However, contrary
to the single-parameter case, the algebraic structure of such a module is very
intricate, and there is no general decomposition into modules of dimension at
most 1, and thus no analogue of the persistence barcode. Instead, the rank
invariant has been introduced as a weaker invariant: it is defined, for a
module ${\mathbb{M}}$, as the function ${\rm RI}:(\alpha,\beta)\mapsto{\rm
rank}({\mathbb{M}}(\alpha)\to{\mathbb{M}}(\beta))$ for any $\alpha\leq\beta$,
but is also known to miss a lot of structural properties of ${\mathbb{M}}$. To
remedy this, several methods have been developed to compute candidate
decompositions for ${\mathbb{M}}$ [1, 15, 26], where a candidate decomposition
is a module $\tilde{\mathbb{M}}$ that can be decomposed as
$\tilde{\mathbb{M}}\simeq\oplus_{i=1}^{m}M_{i}$, where each $M_{i}$ is an
interval module, i.e., its dimension is at most 1, and its support ${\rm
supp}\left(M_{i}\right):=\\{\alpha\in\mathbb{R}^{n}:{\rm
dim}(M_{i}(\alpha))=1\\}$ is an interval of $\mathbb{R}^{n}$ (see Appendix D).
In particular, when ${\mathbb{M}}$ does decompose into intervals, candidate
decompositions must agree with the true decomposition. One also often asks
candidate decompositions to preserve the rank invariant.

#### Distances.

Finally, multiparameter persistence modules can be compared with two standard
distances: the interleaving and bottleneck (or $\ell^{\infty}$) distances.
Their explicit definitions are technical and not necessary for our main
exposition, so we refer the reader to, e.g., [5, Sections 6.1, 6.4] and
Appendix D for more details. The stability theorem [28, Theorem 5.3] states
that multiparameter persistence modules are stable: $d_{\rm
I}({\mathbb{M}},{\mathbb{M}}^{\prime})\leq\left\lVert
f-f^{\prime}\right\rVert_{\infty},$ where $f$ and $f^{\prime}$ are continuous
multiparameter functions associated to ${\mathbb{M}}$ and
${\mathbb{M}}^{\prime}$ respectively.

##  3 T-CDR: a template for representations of candidate decompositions

Even though candidate decompositions of multiparameter persistence modules are
known to encode useful data information, their algebraic definitions make them
not suitable for subsequent data science and machine learning purposes. Hence,
in this section, we introduce the Template Candidate Decomposition
Representation (T-CDR): a general framework and template system for
representations of candidate decompositions, i.e., maps defined on the space
of candidate decompositions and taking values in an (implicit or explicit)
Hilbert space.

###  3.1 T-CDR definition

#### Notations.

In this article, by a slight abuse of notation, we will make no difference in
the notations between an interval module and its support, and we will denote
the restriction of an interval support $M$ to a given line $\ell$ as
${\left.\kern-1.2ptM\vphantom{\big{|}}\right|_{\ell}}$.

######  Definition 1.

Let ${\mathbb{M}}=\oplus_{i=1}^{m}M_{i}$ be a candidate decomposition, and let
$\mathcal{M}$ be the space of interval modules. The Template Candidate
Decomposition Representation (T-CDR) of ${\mathbb{M}}$ is:

$V_{\mathrm{op},w,\phi}({\mathbb{M}})=\mathrm{op}(\\{w(M_{i})\cdot\phi(M_{i})\\}_{i=1}^{m}),$
(1)

where $\mathrm{op}$ is a permutation invariant operation (sum, max, min, mean,
etc), $w:\mathcal{M}\rightarrow\mathbb{R}$ is a weight function, and
$\phi:\mathcal{M}\rightarrow\mathcal{H}$ sends any interval module to a vector
in a Hilbert space $\mathcal{H}$.

The general definition of T-CDR is inspired from a similar framework that was
introduced for single-parameter persistence with the automatic representation
method Perslay [10].

#### Relation to previous work.

Interestingly, whenever applied on candidate decompositions that preserve the
rank invariant, specific choices of $\mathrm{op}$, $w$ and $\phi$ reproduce
previous representations:

  * •

Using $w:M_{i}\mapsto 1$,
$\phi:M_{i}\mapsto\left\\{\begin{array}[]{ll}\mathbb{R}^{n}&\rightarrow\mathbb{R}\\\
x&\mapsto\Lambda(x,{\left.\kern-1.2ptM_{i}\vphantom{\big{|}}\right|_{\ell_{x}}})\end{array}\right.$
and $\mathrm{op}=k$th maximum, where $l_{x}$ is the diagonal line crossing
$x$, and $\Lambda(\cdot,\ell)$ denotes the tent function associated to any
segment $\ell\subset\mathbb{R}^{n}$, induces the $k$th multiparameter
persistence landscape [39].

  * •

Using $w:M_{i}\mapsto 1$,
$\phi:M_{i}\mapsto\left\\{\begin{array}[]{ll}\mathbb{R}^{n}\times\mathbb{R}^{n}&\rightarrow\mathbb{R}^{d}\\\
p,q&\mapsto
w^{\prime}(M_{i}\cap[p,q])\cdot\phi^{\prime}(M_{i}\cap[p,q])\end{array}\right.$
and $\mathrm{op}=\mathrm{op}^{\prime}$, where $\mathrm{op}^{\prime}$,
$w^{\prime}$ and $\phi^{\prime}$ are the parameters of any persistence diagram
representation from Perslay, induces the multiparameter persistence kernel
[13].

  * •

Using $w:M_{i}\mapsto{\rm vol}(M_{i})$,
$\phi:M_{i}\mapsto\left\\{\begin{array}[]{ll}\mathbb{R}^{n}&\rightarrow\mathbb{R}\\\
x&\mapsto{\rm exp}(-{\rm min}_{\ell\in
L}d(x,{\left.\kern-1.2ptM_{i}\vphantom{\big{|}}\right|_{\ell}})^{2}/\sigma^{2})\end{array}\right.$
and $\mathrm{op}=\sum$, where $L$ is a set of (pre-defined) diagonal lines,
induces the multiparameter persistence image [9].

Recall that the first two approaches are built from fibered barcodes and rank
invariants, and that it is easy to find persistence modules that are different
yet share the same rank invariant (see [38, Figure 3]. On the other hand, the
third approach uses more information about the candidate decomposition, but is
known to be unstable (see Appendix B). Hence, in the next section, we focus on
specific choices for the T-CDR parameters that induce stable yet informative
representations.

###  3.2 Metric properties

In this section, we study specific parameters for T-CDR (see Definition 1)
that induce representations with associated robustness properties. We call
this subset of representations Stable Candidate Decomposition Representations
(S-CDR), and define them below.

######  Definition 2.

The S-CDR parameters are:

  1. 1.

the weight function $w:M\mapsto\sup\\{\varepsilon>0:\exists
y\in\mathbb{R}^{n}\text{ s.t. }\ell_{y,\varepsilon}\subset{\rm
supp}\left(M\right)\\}$,where $\ell_{y,\varepsilon}$ is the segment between
$y-\varepsilon\cdot[1,\dots,1]$ and $y+\varepsilon\cdot[1,\dots,1]$,

  2. 2.

the individual interval representations
$\phi_{\delta}(M):\mathbb{R}^{n}\to\mathbb{R}$:

(a)
$\phi_{\delta}(M)(x)=\frac{1}{\delta}{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}w({\rm
supp}\left(M\right)\cap R_{x,\bm{\delta}})}}$, (b)
$\phi_{\delta}(M)(x)=\frac{1}{(2\delta)^{n}}\mathrm{vol}\left({\rm
supp}\left(M\right)\cap R_{x,\bm{\delta}}\right)$,

(c)
$\phi_{\delta}(M)(x)=\frac{1}{(2\delta)^{n}}\sup_{x^{\prime},\bm{\delta}^{\prime}}\left\\{{\rm
vol}(R_{x^{\prime},\bm{\delta}^{\prime}}):R_{x^{\prime},\bm{\delta}^{\prime}}\subseteq{\rm
supp}\left(M\right)\cap R_{x,\bm{\delta}}\right\\}$,

where $R_{x,\bm{\delta}}$ is the hypersquare
$\left\\{y\in\mathbb{R}^{n}:x-\bm{\delta}\leq y\leq
x+\bm{\delta}\right\\}\subseteq\mathbb{R}^{n}$,
$\bm{\delta}:=\delta\cdot[1,\dots,1]\in\mathbb{R}^{n}$ for any $\delta>0$, and
${\rm vol}$ denotes the volume of a set in $\mathbb{R}^{n}$.

  3. 3.

the permutation invariant operators $\mathrm{op}=\sum$ and $\mathrm{op}=\sup$.

In other words, our weight function is the length of the largest diagonal
segment one can fit inside ${\rm supp}\left(M\right)$, and the interval
representations (a), (b) and (c) are the largest diagonal length, volume, and
largest hypersquare volume one can fit locally inside ${\rm
supp}\left(M\right)\cap R_{x,\bm{\delta}}$ respectively.

Equipped with these S-CDR parameters, we can now define the two following
S-CDR, that can be applied on any candidate decomposition
${\mathbb{M}}=\oplus_{i=1}^{m}M_{i}$:

$V_{p,\delta}({\mathbb{M}}):=\sum_{i=1}^{m}\frac{w(M_{i})^{p}}{\sum_{j=1}^{m}w(M_{j})^{p}}\phi_{\delta}(M_{i}),$
(2)

$V_{\infty,\delta}({\mathbb{M}}):=\sup_{1\leq i\leq m}\phi_{\delta}(M_{i}).$
(3)

These S-CDR parameters allow for some trade-off between computational cost and
the amount of information that is kept: (a) and (c) are very easy to compute,
but (b) encodes more information about interval shapes. See Figure 2 (right)
for visualizations.

#### Stability.

The main motivation for introducing S-CDR parameters is that the corresponding
S-CDR are stable in the interleaving and bottleneck distances, as stated in
the following theorem.

######  Theorem 1.

Let ${\mathbb{M}}=\oplus_{i=1}^{m}M_{i}$ and
${\mathbb{M}}^{\prime}=\oplus_{j=1}^{m^{\prime}}M^{\prime}_{j}$ be two
candidate decompositions. Assume that we have
$\frac{1}{m}\sum_{i}w(M_{i}),\frac{1}{m^{\prime}}\sum_{j}w(M^{\prime}_{j})\geq
C$, for some $C>0$. Then for any $\delta>0$, one has

$\displaystyle\left\lVert
V_{0,\delta}({\mathbb{M}})-V_{0,\delta}({\mathbb{M}}^{\prime})\right\rVert_{\infty}$
$\displaystyle\leq 2(d_{\rm
B}({\mathbb{M}},{\mathbb{M}}^{\prime})\wedge\delta)/\delta,$ (4)
$\displaystyle\left\lVert
V_{1,\delta}({\mathbb{M}})-V_{1,\delta}({\mathbb{M}}^{\prime})\right\rVert_{\infty}$
$\displaystyle\leq\left[4+\frac{2}{C}\right](d_{\rm
B}({\mathbb{M}},{\mathbb{M}}^{\prime})\wedge\delta)/\delta,$ (5)
$\displaystyle\left\lVert
V_{\infty,\delta}({\mathbb{M}})-V_{\infty,\delta}({\mathbb{M}}^{\prime})\right\rVert_{\infty}$
$\displaystyle\leq(d_{\rm
I}({\mathbb{M}},{\mathbb{M}}^{\prime})\wedge\delta)/\delta,$ (6)

where $\wedge$ stands for minimum.

A proof of Theorem 1 can be found in Appendix F.

These results are the main theoretical contribution in this work, as the only
other decomposition-based representation in the literature [9] has no such
guarantees. The other representations [13, 7, 39, 41] enjoy similar guarantees
than ours, but are computed from the rank invariant and do not exploit the
information contained in decompositions. Theorem 1 shows that S-CDRs bring the
best of both worlds: these representations are richer than the rank invariant
and stable at the same time. We also provide an additional stability result
with a similar, yet more complicated representation in Appendix G, whose upper
bound does not involve taking minimum.

######  Remark 1.

S-CDR are injective representations: if the support of two interval modules
are different, then their corresponding S-CDRs (evaluated on a point that
belongs to the support of one interval but not on the support of the other)
will differ, provided that $\delta$ is sufficiently small.

##  4 Numerical Experiments

In this section, we illustrate the efficiency of our S-CDRs with numerical
experiments. First, we explore the stability theorem in Section 4.1 by
studying the convergence rates, both theoretically and empirically, of S-CDRs
on various data sets, as well as their running times in Section 4.2. Then, we
showcase the efficiency of S-CDRs on classification tasks in Section 4.3. Our
code for computing S-CDRs is based on the MMA [26] and Gudhi [36] libraries
for computing candidate decompositions222 Several different approaches can be
used for computing decompositions [1, 15]. In our experiments, we used MMA
[26] because of its simplicity and rapidity.  and is publicly available at
https://github.com/DavidLapous/multipers. We also provide pseudo-code in
Appendix H.

###  4.1 Convergence rates

In this section, we study the convergence rate of S-CDRs with respect to the
number of sampled points, when computed from specific bifiltrations. Similar
to the single parameter persistence setting [14], these rates are derived from
Theorem 1. Indeed, since concentration inequalities for multiparameter
persistence modules have already been described in the literature, these
concentration inequalities can transfer to our representations. Note that
while Equations (7) and (8), which provide such rates, are stated for the
S-CDR in (3), they also hold for the S-CDR in (2).

#### Measure bifiltration.

Let $\mu$ be a compactly supported probability measure of $\mathbb{R}^{D}$,
and let $\mu_{n}$ be the discrete measure associated to a sampling of $n$
points from $\mu$. The measure bifiltration associated to $\mu$ and $\mu_{n}$
is defined as $\mathcal{F}^{\mu}_{r,t}:=\\{x\in\mathbb{R}^{D}:\mu(B(x,r))\leq
t\\}$, where $B(x,r)$ denotes the Euclidean ball centered on $x$ with radius
$r$. Now, let ${\mathbb{M}}$ and ${\mathbb{M}}_{n}$ be the multiparameter
persistence modules obtained from applying the homology functor on top of the
measure bifiltrations $\mathcal{F}^{\mu}$ and $\mathcal{F}^{\mu_{n}}$. These
modules are known to enjoy the following stability result [4, Theorem 3.1,
Proposition 2.23 (i)]: $d_{\rm I}({\mathbb{M}},{\mathbb{M}}_{n})\leq
d_{\mathrm{Pr}}(\mu,\mu_{n})\leq\min(d_{W}^{p}(\mu,\mu_{n})^{\frac{1}{2}},d_{W}^{p}(\mu,\mu_{n})^{\frac{p}{p+1}}),$
where $d_{W}^{p}$ and $d_{\rm Pr}$ stand for the $p$-Wasserstein and Prokhorov
distances between probability measures. Combining these inequalities with
Theorem 1, then taking expectations and applying the concentration
inequalities of the Wasserstein distance (see [27, Theorem 3.1] and [22,
Theorem 1]) lead to:

$\delta\mathbb{E}\left[\left\lVert
V_{\infty,\delta}({\mathbb{M}})-V_{\infty,\delta}({\mathbb{M}}_{n})\right\rVert_{\infty}\right]\leq\left(c_{p,q}\mathbb{E}\left(|X|^{q}\right)n^{-\left(\frac{1}{2p\vee
d}\right)\wedge\frac{1}{p}-\frac{1}{q}}\log^{\alpha/q}n\right)^{\frac{p}{p+1}},$
(7)

where $\vee$ stands for maximum, $\alpha=2$ if $2p=q=d$, $\alpha=1$ if $d\neq
2p$ and $q=dp/(d-p)\wedge 2p$ or $q>d=2p$ and $\alpha=0$ otherwise, $c_{p,q}$
is a constant that depends on $p$ and $q$, and $X$ is a random variable of law
$\mu$.

####  Čech complex and density.

A limitation of the measure bifiltration is that it can be difficult to
compute. Hence, we now focus on another, easier to compute bifiltration. Let
$X$ be a smooth compact $d$-submanifold of $\mathbb{R}^{D}$ ($d\leq D$), and
$\mu$ be a measure on $X$ with density $f$ with respect to the uniform measure
on $X$. We now define the bifiltration $\mathcal{F}^{C,f}$ with:

$\mathcal{F}_{u,v}^{C,f}:=\mathrm{\check{C}ech}(u)\cap
f^{-1}([v,\infty))=\left\\{x\in\mathbb{R}^{D}:d(x,X)\leq u,f(x)\geq
v\right\\}.$

Moreover, given a set $X_{n}$ of $n$ points sampled from $\mu$, we also
consider the approximate bifiltration ${\mathcal{F}}^{C,f_{n}}$, where
$f_{n}\colon X\to\mathbb{R}$ is an estimation of $f$ (such as, e.g., a kernel
density estimator). Let ${\mathbb{M}}$ and ${\mathbb{M}}_{n}$ be the
multiparameter persistence modules associated to $\mathcal{F}^{C,f}$ and
${\mathcal{F}}^{C,f_{n}}$. Then, the stability of the interleaving distance
[28, Theorem 5.3] ensures:

$d_{\rm I}({\mathbb{M}},{\mathbb{M}}_{n})\leq\left\lVert
f-f_{n}\right\rVert_{\infty}\vee d_{H}(X,X_{n}),$

where $d_{H}$ stands for the Hausdorff distance. Moreover, concentration
inequalities for the Hausdorff distance and kernel density estimators are also
available in the literature (see [14, Theorem 4] and [24, Corollary 15]). More
precisely, when the density $f$ is $L$-Lipschitz and bounded from above and
from below, i.e., when $0<f_{\min}\leq f\leq f_{\max}<\infty$, and when
$f_{n}$ is a kernel density estimator of $f$ with associated kernel $k$, one
has:

$\mathbb{E}(d_{H}(X,X_{n}))\lesssim\left(\frac{\log
n}{n}\right)^{\frac{1}{d}}\text{ and }\mathbb{E}(\left\lVert
f-f_{n}\right\rVert_{\infty})\lesssim
Lh_{n}+\sqrt{\frac{\log(1/h_{n})}{nh_{n}^{d}}},$

where $h_{n}$ is the (adaptive) bandwidth of the kernel $k$ . In particular,
if $\mu$ is a measure comparable to the uniform measure of a $d=2$-manifold,
then for any stationary sequence $h_{n}:=h>0$, and considering a Gaussian
kernel $k$, one has:

$\delta\mathbb{E}\left[\left\lVert
V_{\infty,\delta}({\mathbb{M}})-V_{\infty,\delta}({\mathbb{M}}_{n})\right\rVert_{\infty}\right]\lesssim\sqrt{\frac{\log
n}{n}}+Lh.$ (8)

#### Empirical convergence rates.

Now that we have established the theoretical convergence rates of S-CDRs, we
estimate and validate them empirically on data sets. We will first study a
synthetic data set and then a real data set of point clouds obtained with
immunohistochemistry. We also illustrate how the stability of S-CDRs (stated
in Theorem 1) is critical for obtaining such convergence in Appendix B, where
we show that our main competitor, the multiparameter persistence image [10],
is unstable and thus cannot achieve convergence, both theoretically and
numerically.

Annulus with non-uniform density. In this synthetic example, we generate an
annulus of 25,000 points in $\mathbb{R}^{2}$ with a non-uniform density,
displayed in Figure 3(a). Then, we compute the bifiltration
$\mathcal{F}^{C,f_{n}}$ corresponding to the Alpha filtration and the sublevel
set filtration of a kernel density estimator, with bandwidth parameter
$h=0.1$, on the complete Alpha simplicial complex. Finally, we compute the
candidate decompositions and associated S-CDRs of the associated
multiparameter module (in homology dimension 1), and their normalized
distances to the target representation, using either
$\left\lVert\cdot\right\rVert_{2}^{2}$ or
$\left\lVert\cdot\right\rVert_{\infty}$. The corresponding distances for
various number of sample points are displayed in log-log plots in Figure 3(b).
One can see that the empirical rate is roughly consistent with the theoretical
one ($-1/2$ for $\left\lVert\cdot\right\rVert_{\infty}$ and $-1$ for
$\left\lVert\cdot\right\rVert_{2}$), even when $p\neq\infty$ (in which case
our S-CDRs are stable for $d_{\rm B}$ but theoretically not for $d_{\rm I}$).

(a) Scatter plot of the synthetic data set colored by a kernel density
estimator.

(b) (left) $\left\lVert\cdot\right\rVert^{2}_{2}$ and (right)
$\left\lVert\cdot\right\rVert_{\infty}$ between the target representation and
the empirical one w.r.t. $n$.

Figure 3:  Convergence rate of synthetic data set.

Immunohistochemistry data. In our second experiment, we consider a point cloud
representing cells, taken from [37], see Figure 4(a). These cells are given
with biological markers, which are typically used to assess, e.g., cell types
and functions. In this experiment, we first triangulate the point cloud by
placing a $100\times 100$ grid on top of it. Then, we filter this grid using
the sublevel set filtrations of kernel density estimators (with Gaussian
kernel and bandwidth $h=1$) associated to the CD8 and CD68 biological markers
for immune cells. Finally, we compute the associated candidate decompositions
of the multiparameter modules in homology dimensions 0 and 1, and we compute
and concatenate their corresponding S-CDRs. The convergence rates are
displayed in Figure 4(b). Similar to the previous experiment, the theoretical
convergence rate of our representations is upper bounded by the one for kernel
density estimators with the $\infty$-norm, which is of order
$\frac{1}{\sqrt{n}}$ with respect to the number $n$ of sampled points. Again,
the observed and theoretical convergence rates are consistent.

(a) Point cloud of cells colored by CD8 (red) and CD68 (black).

(b) (left) $\left\lVert\cdot\right\rVert_{2}^{2}$ and (right)
$\left\lVert\cdot\right\rVert_{\infty}$ distances between the target
representation and the empirical one w.r.t. $n$.

Figure 4:  Convergence rate of immunohistochemistry data set.

###  4.2 Running time comparisons

In this section, we provide running time comparisons between S-CDRs and the
MPI and MPL representations. We provide results in Table 2, where it can be
seen that S-CDRs (computed on the pinched annulus and immunohistochemistry
data sets defined above) can be computed much faster than the other
representations, by a factor of at least 25 (all representations are evaluated
on grids of sizes $50\times 50$ and $100\times 100$, and we provide the
maximum running time over $p\in\\{0,1,\infty\\}$). All computations were done
using a Ryzen 4800 laptop CPU, with 16GB of RAM. Interestingly, this sparse
and fast implementation based on corners can also be used to improve on the
running time of the multiparameter persistence landscapes (MPL), as one can
see from Algorithm 4 in Appendix H (which retrieves the persistence barcode of
a multiparameter persistence module along a given line; this is enough to
compute the MPL) and from the second line of Table 2.

###  4.3 Classification

Finally, we illustrate the efficiency of S-CDRs by using them for
classification purposes. We show that they perform comparably or better than
existing topological representations as well as standard baselines on several
UCR benchmark data sets and on immunohistochemistry data. Concerning UCR, we
work with point clouds obtained from time delay embedding applied on the UCR
time series, following the procedure of [9].  In both tasks, every point cloud
has a label (corresponding to the type of its cells in the
immunohistochemistry data, and to pre-defined labels in the UCR data), and our
goal is to check whether we can predict these labels by training classifiers
on S-CDRs computed from the same bifiltration as in the previous section.

We compare the performances of our S-CDRs (evaluated on a $50\times 50$ grid)
to the one of the multiparameter persistence landscape (MPL) [39], kernel
(MPK) [13] and images (MPI) [9], as well as their single-parameter
counterparts (P-L, P-I and PSS-K) 333Note that the sizes of the point clouds
in the immunohistochemistry data were too large for MPK and MPI using the code
provided in https://github.com/MathieuCarriere/multipers, and that all three
single-parameter representations had roughly the same performance, so we only
display one, denoted as P.. We also compare to some non-topological baselines:
we used the standard Ripley function evaluated on 100 evenly spaced samples in
$[0,1]$ for immunohistochemistry data, and k-NN classifiers with three
difference distances for the UCR time series (denoted by B1, B2, B3), as
suggested in [20]. All scores on the immunohistochemistry data were computed
with 5 folds after cross-validating a few classifiers (random forests, support
vector machines and xgboost).  For the time series data, our accuracy scores
were obtained after also cross-validating the following S-CDR parameters;
$p\in\\{0,1\\}$, $\mathrm{op}\in\\{\mathrm{sum},\mathrm{mean}\\}$,
$\delta\in\\{0.01,0.1,0.5,1\\}$, $h\in\\{0.1,0.5,1,1.5\\}$ with homology
dimensions $0$ and $1$. All results can be found in Table 1, and the full
table is in Appendix I (note that there are no variances for UCR data since
pre-defined train/test splits were provided). One can see that S-CDR almost
always outperform topological baselines and are comparable to the standard
baselines on the UCR benchmarks. Most notably, S-CDR radically outperforms the
standard baseline and competing topological measures on the
immunohistochemistry data set.

Dataset | B1 | B2 | B3 | PSS-K | P-I | P-L | MPK | MPL | MPI | S-CDR
---|---|---|---|---|---|---|---|---|---|---
DPOAG | 62.6 | 62.6 | 77.0 | 76.9 | 69.8 | 70.5 | 67.6 | 70.5 | 71.9 | 71.9
DPOC | 71.7 | 72.5 | 71.7 | 47.5 | 67.4 | 66.3 | 74.6 | 69.6 | 71.7 | 73.8
PPOAG | 78.5 | 78.5 | 80.5 | 75.9 | 82.0 | 78.0 | 78.0 | 78.5 | 81.0 | 81.9
PPOC | 80.8 | 79.0 | 78.4 | 78.4 | 72.2 | 72.5 | 78.7 | 78.7 | 81.8 | 79.4
PPTW | 70.7 | 75.6 | 75.6 | 61.4 | 72.2 | 73.7 |  79.5 | 73.2 | 76.1 | 75.6
IPD | 95.5 | 95.5 | 95.0 | - | 64.7 | 61.1 | 80.7 | 78.6 | 71.9 | 81.2
GP | 91.3 | 91.3 | 90.7 | 90.6 | 84.7 | 80.0 | 88.7 | 94.0 | 90.7 | 96.3
GPAS | 89.9 | 96.5 | 91.8 | - | 84.5 | 87.0 | 93.0 | 85.1 | 90.5 | 88.0
GPMVF | 97.5 | 97.5 | 99.7 | - | 88.3 | 87.3 | 96.8 | 88.3 | 95.9 | 95.3
PC | 93.3 | 92.2 | 87.8 | - | 83.4 | 76.7 | 85.6 | 84.4 | 86.7 | 93.1
| Ripley | P | MPL | S-CDR
immuno | 67.2 $\pm$ 2.3 | 60.7 $\pm$ 4.2 | 65.3 $\pm$ 3.0 | 91.4 $\pm$ 1.6

Table 1: Scores for time series and immunohistochemistry.

| Annulus | Immuno
---|---|---
Ours (S-CDR) | $250ms\pm 2ms$ | $275ms\pm 9.8ms$
Ours (MPL) | $36.9ms\pm 0.8ms$ | $65.9ms\pm 0.9ms$
MPI (50) | $6.43s\pm 25ms$ | $5.67s\pm 23.3ms$
MPL (50) | $17s\pm 39ms$ | $15.6s\pm 14ms$
MPI (100) | $13.1s\pm 125ms$ | $11.65s\pm 7.9ms$
MPL (100) | $35s\pm 193ms$ | $31.3s\pm 23.3ms$

Table 2:  Running times for S-CDRs and competitors.

##  5 Conclusion

In this article, we study the general question of representing decompositions
of multiparameter persistence modules in Topological Data Analysis. We first
introduce T-CDR: a general template framework including specific
representations (called S-CDR) that are provably stable. Our experiments show
that S-CDR is superior to the state of the art.

Limitations. (1) Our current T-CDR parameter selection is currently done
through cross-validation, which can be very time consuming and limits the
number of parameters to choose from. (2) Our classification experiments were
mostly illustrative. In particular, it would be useful to investigate more
thoroughly on the influence of the T-CDR and S-CDR parameters, as well as the
number of filtrations, on the classification scores. (3) In order to generate
finite-dimensional vectors, we evaluated T-CDR and S-CDR on finite grids,
which limited their discriminative powers when fine grids were too costly to
compute.

Future work. (1) Since T-CDR is similar to the Perslay framework of single
parameter persistence [10] and since, in this work, each of the framework
parameter was optimized by a neural network, it is thus natural to investigate
whether one can optimize T-CDR parameters in a data-driven way as well, so as
to be able to avoid cross-validation. (2) In our numerical applications, we
focused on representations computed off of MMA decompositions [26]. In the
future, we plan to investigate whether working with other decomposition
methods [1, 15] lead to better numerical performance when combined with our
representation framework.

## References

  * AENY [19] Hideto Asashiba, Emerson G. Escolar, Ken Nakashima, and Michio Yoshiwaki.  On approximation of $2$D persistence modules by interval-decomposables.  arXiv:1911.01637 [math], November 2019.
  * BHO [18] Mickaël Buchet, Yasuaki Hiraoka, and Ippei Obayashi.  Persistent homology and materials informatics.  In Nanoinformatics, pages 75–95. Springer-Verlag, 2018.
  * BL [18] Magnus Bakke Botnan and Michael Lesnick.  Algebraic stability of zigzag persistence modules.  Algebraic & Geometric Topology, 18(6):3133–3204, October 2018\.
  * BL [21] Andrew J. Blumberg and Michael Lesnick.  Stability of 2-parameter persistent homology.  arXiv:2010.09628 [cs, math], February 2021.
  * BL [22] Magnus Botnan and Michael Lesnick.  An introduction to multiparameter persistence.  In CoRR. arXiv:2203.14289, 2022.
  * BOO [22] Magnus Botnan, Steffen Oppermann, and Steve Oudot.  Signed Barcodes for Multi-Parameter Persistence via Rank Decompositions.  In 38th International Symposium on Computational Geometry (SoCG 2022), volume 224, pages 19:1–19:18. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2022.
  * CAC+ [21] Baris Coskunuzer, Ignacio Akcora, Cuneyt Dominguez, Yuzhou Chen, Zhiwei Zhen, Murat Kantarcioglu, and Yulia Gel.  Smart Vectorizations for Single and Multiparameter Persistence.  In CoRR. arXiv:2104.04787, 2021.
  * Car [09] Gunnar Carlsson.  Topology and data.  Bulletin of the American Mathematical Society, 46(2):255–308, 2009\.
  * CB [20] Mathieu Carrière and Andrew Blumberg.  Multiparameter persistence image for topological machine learning.  In Advances in Neural Information Processing Systems 33 (NeurIPS 2020), pages 22432–22444. Curran Associates, Inc., 2020.
  * CCI+ [20] Mathieu Carrière, Frédéric Chazal, Yuichi Ike, Théo Lacombe, Martin Royer, and Yuhei Umeda.  PersLay: a neural network layer for persistence diagrams and new graph topological signatures.  In 23rd International Conference on Artificial Intelligence and Statistics (AISTATS 2020), pages 2786–2796. PMLR, 2020.
  * CdGO [16] Frédéric Chazal, Vin de Silva, Marc Glisse, and Steve Oudot.  The Structure and Stability of Persistence Modules.  SpringerBriefs in Mathematics. Springer International Publishing, Cham, 2016.
  * CdSGO [16] Frédéric Chazal, Vin de Silva, Marc Glisse, and Steve Oudot.  The structure and stability of persistence modules.  SpringerBriefs in Mathematics. Springer-Verlag, 2016.
  * CFK+ [19] René Corbet, Ulderico Fugacci, Michael Kerber, Claudia Landi, and Bei Wang.  A kernel for multi-parameter persistent homology.  Computers & Graphics: X, 2:100005, 2019.
  * CGLM [15] Frédéric Chazal, Marc Glisse, Catherine Labruère, and Bertrand Michel.  Convergence rates for persistence diagram estimation in topological data analysis.  Journal of Machine Learning Research, 16(110):3603–3635, 2015.
  * CKMW [20] Chen Cai, Woojin Kim, Facundo Mémoli, and Yusu Wang.  Elder-rule-staircodes for augmented metric spaces.  In 36th International Symposium on Computational Geometry (SoCG 2020), pages 26:1–26:17. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2020\.
  * [16] Mathieu Carrière, Steve Oudot, and Maks Ovsjanikov.  Local signatures using persistence diagrams.  In HAL. HAL:01159297, 2015.
  * [17] Mathieu Carrière, Steve Oudot, and Maks Ovsjanikov.  Stable topological signatures for points on 3D shapes.  Computer Graphics Forum, 34(5):1–12, 2015.
  * CVBM [02] Olivier Chapelle, Vladimir Vapnik, Olivier Bousquet, and Sayan Mukherjee.  Choosing Multiple Parameters for Support Vector Machines.  Machine Learning, 46(1):131–159, January 2002.
  * CZ [09] Gunnar Carlsson and Afra Zomorodian.  The theory of multidimensional persistence.  Discrete & Computational Geometry, 42(1):71–93, 2009.
  * DBK+ [18] Hoang-Anh Dau, Anthony Bagnall, Kaveh Kamgar, Chin-Chia Yeh, Yan Zhu, Shaghayegh Gharghabi, Chotirat Ratanamahatana, and Eamonn Keogh.  The UCR time series archive.  In CoRR. arXiv:1810.07758, 2018.
  * DX [22] Tamal Dey and Cheng Xin.  Generalized persistence algorithm for decomposing multiparameter persistence modules.  Journal of Applied and Computational Topology, 2022.
  * FG [15] Nicolas Fournier and Arnaud Guillin.  On the rate of convergence in Wasserstein distance of the empirical measure.  Probability Theory and Related Fields, 162(3):707–738, August 2015\.
  * KM [21] Woojin Kim and Facundo Mémoli.  Generalized Persistence Diagrams for Persistence Modules over Posets.  Journal of Applied and Computational Topology, 5:533–581, 2021\.
  * KSRW [19] Jisu Kim, Jaehyeok Shin, Alessandro Rinaldo, and Larry Wasserman.  Uniform convergence rate of the kernel density estimator adaptive to intrinsic volume dimension.  In Proceedings of the 36th International Conference on Machine Learning (ICML 2019), volume 97, pages 3398–3407. PMLR, 2019.
  * Lan [18] Claudia Landi.  The rank invariant stability via interleavings.  In Research in Computational Topology, pages 1–10. Springer, 2018\.
  * LCB [22] David Loiseaux, Mathieu Carrière, and Andrew Blumberg.  Efficient Approximation of Multiparameter Persistence Modules.  In CoRR. arXiv:2206.02026, 2022.
  * Lei [20] Jing Lei.  Convergence and Concentration of Empirical Measures under Wasserstein Distance in Unbounded Functional Spaces.  Bernoulli, 26(1), February 2020.
  * Les [15] Michael Lesnick.  The theory of the interleaving distance on multidimensional persistence modules.  Foundations of Computational Mathematics, 15(3):613–650, 2015.
  * LW [22] Michael Lesnick and Matthew Wright.  Computing Minimal Presentations and Bigraded Betti Numbers of 2-Parameter Persistent Homology.  arXiv:1902.05708 [cs, math], February 2022.
  * MP [84] J.R. Munkres, Addison-Wesley (1942-1999)., and Perseus Publishing.  Elements of Algebraic Topology.  Advanced Book Classics. Basic Books, 1984.
  * Oud [15] Steve Oudot.  Persistence theory: from quiver representations to data analysis, volume 209 of Mathematical Surveys and Monographs.  American Mathematical Society, 2015.
  * Oze [19] Sedat Ozer.  Similarity domains machine for scale-invariant and sparse shape modeling.  IEEE Trans. Image Process., 28(2):534–545, 2019.
  * PSO [18] Adrien Poulenard, Primoz Skraba, and Maks Ovsjanikov.  Topological function optimization for continuous shape matching.  Computer Graphics Forum, 37(5):13–25, 2018.
  * RB [19] Raúl Rabadán and Andrew Blumberg.  Topological data analysis for genomics and evolution.  Cambridge University Press, 2019.
  * STR+ [17] Mohammad Saadatfar, Hiroshi Takeuchi, Vanessa Robins, Nicolas François, and Yasuaki Hiraoka.  Pore configuration landscape of granular crystallization.  Nature Communications, 8:15082, 2017.
  * The [22] The GUDHI Project.  GUDHI User and Reference Manual.  GUDHI Editorial Board, 3.6.0 edition, 2022.
  * VBM+ [21] Oliver Vipond, Joshua Bull, Philip Macklin, Ulrike Tillmann, Christopher Pugh, Helen Byrne, and Heather Harrington.  Multiparameter persistent homology landscapes identify immune cell spatial patterns in tumors.  Proceedings of the National Academy of Sciences of the United States of America, 118(41), 2021.
  * [38] Oliver Vipond.  Local equivalence of metrics for multiparameter persistence modules.  arXiv:2004.11926 [math], April 2020.
  * [39] Oliver Vipond.  Multiparameter persistence landscapes.  Journal of Machine Learning Research, 21(61):1–38, 2020.
  * Wit [87] Andrew P. Witkin.  Scale-space filtering.  In Readings in Computer Vision: Issues, Problems, Principles, and Paradigms, pages 329–332. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, January 1987.
  * XMSD [23] Cheng Xin, Soham Mukherjee, Shreyas Samaga, and Tamal Dey.  GRIL: A 2-parameter Persistence Based Vectorization for Machine Learning.  In CoRR. arXiv:2304.04970, 2023.

##  Appendix A Limitation of single-parameter persistent homology

A standard example of single-parameter filtration for point clouds, called the
Čech filtration, is to consider $f:x\mapsto d_{P}(x):=\min{p\in P}\left\lVert
x-p\right\rVert$, where $P$ is a point cloud. The sublevel sets of this
function are balls centered on the points in $P$ with growing radii, and the
corresponding persistence barcode contains the topological features formed by
$P$. See Figure 5(a). When the radius of the balls is small, they form three
connected components (upper left), identified as the three long red bars in
the barcode (lower). When this radius is moderate, a cycle is formed (upper
middle), identified as the long blue bar in the barcode (lower). Finally, when
the radius is large, the balls cover the whole Euclidean plane, and no
topological features are left, except for one connected component, that never
dies (upper right).

(a) Persistence barcode obtained from growing balls on a clean point cloud.

(b) Persistence barcode obtained from growing balls on a noisy point cloud.

Figure 5:  Example of persistence barcode construction for point clouds using
Čech filtration. In the middle sublevel sets, we highlight the topological
cycles in blue.

The limitation of the Čech filtration alone for noisy point cloud is
illustrated in Figure 5(b), where only feature scale is used, and the presence
of three outlier points messes up the persistence barcode entirely, since they
induce the appearance of two cycles instead of one. In order to remedy this,
one could remove points whose density is smaller than a given threshold, and
then process the trimmed point cloud as before, but this requires using an
arbitrary threshold choice to decide which points should be considered
outliers or not.

##  Appendix B Unstability of MPI

In this section, we provide theoretical and experimental evidence that the
multiparameter persistence image (MPI) [10], which is another decomposition-
based representation from the literature, suffers from lack of stability as it
does not enjoy guarantees such as the ones provided of S-CDRs by Theorem 1.
There two main sources of instability in the MPI. The first one is due to the
discretization induced by the lines: since it is obtained by placing Gaussian
functions on top of slices of the intervals in the decompositions, if the
Gaussian bandwidth $\sigma$ (see previous work, third item in Section 3.1) is
too small w.r.t. the distance between consecutive lines in $L$, discretization
effects can arise, as illustrated in Figure 6, in which the intervals do not
appear as continuous shapes.

Figure 6: Examples of numerical artifacts occurring when the number of lines
is too small w.r.t. the Gaussian bandwidth, for two different families of
lines.

The second problem comes from the weight function: it is easy to build
decompositions that are close in the interleaving distance, yet whose interval
volumes are very different. See [3, Figure 15], and Figure 7, in which we show
a family of modules ${\mathbb{M}}^{\epsilon}$ (left) made of a single interval
built from connecting two squares with a bridge of diameter $\epsilon>0$. We
also show the distances between ${\mathbb{M}}^{\epsilon}$ and the limit module
${\mathbb{M}}$ made of two squares with no bridge, through their MPI and
S-CDRs (right). Even though the interleaving distance between
${\mathbb{M}}^{\epsilon}$ and ${\mathbb{M}}$ goes to zero as $\epsilon$ goes
to zero, the distances between MPI representations converge to a positive
constant, whereas the distances between S-CDRs goes to zero.

Figure 7: Example of unstability of MPI.

We also show that this lack of stability can even prevent convergence. In
Figure 8, we repeated the setup of Section 4.1 on a synthetic data set sampled
from a noisy annulus in the Euclidean plane. As one can clearly see,
convergence does not happen for MPI as the Euclidean distance to the limit MPI
representation associated to the maximal number of subsample points suddenly
drops to zero after an erratic behavior, while S-CDRs exhibit a gradual
decrease in agreement with Theorem 1.

Figure 8: Example of lack of convergence for MPI.

##  Appendix C Simplicial homology

In this section, we recall the basics of simplicial homology with coefficients
in $\mathbb{Z}/2\mathbb{Z}$, which we use for practical computations. A more
detailed presentation can be found in [30, Chapter 1]. The basic bricks of
simplicial (persistent) homology are simplicial complexes, which are
combinatorial models of topological spaces that can be stored and processed
numerically.

######  Definition 3.

Given a set of points $X_{n}:=\\{x_{1},\dots,x_{n}\\}$ sampled in a
topological space $X$, an abstract simplicial complex built from $X_{n}$ is a
family $S(X_{n})$ of subsets of $X_{n}$ such that:

  * •

if $\tau\in S(X_{n})$ and $\sigma\subseteq\tau$, then $\sigma\in S(X_{n})$,
and

  * •

if $\sigma,\tau\in S(X_{n})$, then either $\sigma\cap\tau\in S(X_{n})$ or
$\sigma\cap\tau=\varnothing$.

Each element $\sigma\in S(X_{n})$ is called a simplex of $S(X_{n})$, and the
dimension of a simplex is defined as ${\rm dim}(\sigma):={\rm
card}(\sigma)-1$. Simplices of dimension $0$ are called vertices.

An important linear operator on simplices is the so-called boundary operator.
Roughly speaking, it turns a simplex into the chain of its faces, where a
chain is a formal sum of simplices. The set of chains has a group structure,
denoted by $Z_{*}(S(X_{n}))$.

######  Definition 4.

Given a simplex $\sigma:=[x_{i_{1}},\dots,x_{i_{p}}]$, the boundary operator
$\partial$ is defined as

$\partial(\sigma):=\sum_{j=1}^{p}[x_{i_{1}},\dots,x_{i_{j-1}},x_{i_{j+1}},\dots,x_{i_{p}}].$

In other words, it is the chain constructed from $\sigma$ by removing one
vertex at a time. This operator $\partial$ can then be extended
straightforwardly to chains by linearity.

Given a simplicial complex, a topological feature is defined as a cycle, i.e.,
a chain such that each simplex in its boundary appears an even number of
times. In order to formalize this property, we remove a simplex in a chain
every time it appears twice, and we let a cycle be a chain $c$ s.t.
$\partial(c)=0$.

Now, one can easily check that $\partial\circ\partial(c)=0$ for any chain $c$,
i.e., the boundary of a cycle is always a cycle. Hence, one wants to exclude
cycles that are boundaries, since they correspond somehow to trivial cycles.
Again, such boundaries form a group that is denoted by $B_{*}(S(X_{n}))$.

######  Definition 5.

The homology group in dimension $k$ is the quotient group

$H_{k}(S(X_{n})):=\frac{Z_{k}(S(X_{n})}{B_{k}(S(X_{n}))}.$

In other words, it is the group (one can actually show it is a vector space)
of cycles made of simplices of dimension $k$ that are not boundaries.

See Figure 9 for an illustration of these definitions. Finally, given a
filtered simplicial complex (as defined in Section 2), computing its
associated persistence barcode using the simplicial homology functor can be
done with several softwares, such as, e.g., Gudhi [36].

Figure 9: Example of simplicial complex $S$ built from eight points, and made
of eight vertices (simplices of dimension 0), fourteen edges (simplices of
dimension 1) and six triangles (simplices of dimension 2). The purple path is
a cycle; indeed
$\partial([v_{1},v_{7}]+[v_{7},v_{4}]+[v_{4},v_{6}]+[v_{6},v_{1}])=[v_{1}]+[v_{7}]+[v_{7}]+[v_{4}]+[v_{4}]+[v_{6}]+[v_{6}]+[v_{1}]=0$
since every vertex appears twice. Similarly, the blue path is a cycle as well.
However, both paths represent the same topological feature, in the sense that
they belong to the same equivalence class of $H_{1}(S)$, since their sum is
exactly the boundary of the 2-chain comprised of the six triangles of the
complex, i.e., they differ only by a trivial cycle. Hence, the dimension of
$H_{1}(S)$ is 1.

##  Appendix D Modules, interleaving and bottleneck distances

In this section, we provide a more formalized version of multiparameter
persistence modules and their associated distances. Strictly speaking,
multiparameter persistence modules are nothing but a parametrized family of
vector spaces obtained from applying the homology functor to a
multifiltration, as explained in Section 2.

######  Definition 6.

A multiparameter persistence module ${\mathbb{M}}$ is a family of vector
spaces $\\{M(\alpha):\alpha\in\mathbb{R}^{n}\\}$, together with linear
transformations, also called transition maps,
$\varphi_{\alpha}^{\beta}:{\mathbb{M}}(\alpha)\to{\mathbb{M}}(\beta)$ for any
$\alpha\leq\beta$ (where $\leq$ denotes the partial order of
$\mathbb{R}^{n}$), that satisfy
$\varphi_{\alpha}^{\gamma}=\varphi_{\beta}^{\gamma}\circ\varphi_{\alpha}^{\beta}$
for any $\alpha\leq\beta\leq\gamma$.

Of particular interest are interval modules, since they are easier to work
with.

######  Definition 7.

An interval module ${\mathbb{M}}$ is a multiparameter persistence module such
that:

  * •

its dimension is at most 1: ${\rm dim}({\mathbb{M}}(\alpha))\leq 1$ for any
$\alpha\in\mathbb{R}^{n}$, and

  * •

its support ${\rm supp}({\mathbb{M}}):=\\{\alpha\in\mathbb{R}^{n}:{\rm
dim}({\mathbb{M}}(\alpha))=1\\}$ is an interval of $\mathbb{R}^{n}$,

where an interval of $\mathbb{R}^{n}$ is a subset of
$I\subseteq\mathbb{R}^{n}$ that satisfy:

  * •

(convexity) if $p,q\in$ and $p\leq r\leq q$ then $r\in I$, and

  * •

(connectivity) if $p,q\in I$, then there exists a finite sequence
$r_{1},r_{2},\dots,r_{m}\in I,$ for some $m\in\mathbb{N}$, such that $p\sim
r_{1}\sim r_{2}\sim\dots\sim r_{m}\sim q$, where $\sim$ can be either $\leq$
or $\geq$.

In the main body of this article, we study representations for candidate
decompositions of modules, i.e., direct sums444 Since multiparameter
persistence modules are essentially families of vector spaces connected by
transition maps, they admit direct sum decompositions, pretty much like usual
vector spaces do.  of interval modules that approximate the input modules.

Multiparameter persistence modules can be compared with the interleaving
distance [28].

######  Definition 8 (Interleaving distance).

Given $\varepsilon>0$, two multiparameter persistence modules ${\mathbb{M}}$
and ${\mathbb{M}}^{\prime}$ are $\bm{\varepsilon}$-interleaved if there exist
two morphisms $f\colon{\mathbb{M}}\to{\mathbb{M}}^{\prime}_{\bm{\varepsilon}}$
and $g\colon{\mathbb{M}}^{\prime}\to{\mathbb{M}}_{\bm{\varepsilon}}$ such that
$g_{\cdot+\bm{\varepsilon}}\circ
f_{\cdot}=\varphi_{\cdot}^{\cdot+2\bm{\varepsilon}}\text{ and
}f_{\cdot+\bm{\varepsilon}}\circ
g_{\cdot}=\psi_{\cdot}^{\cdot+2\bm{\varepsilon}},$ where
${\mathbb{M}}_{\bm{\varepsilon}}$ is the shifted module
$\\{{\mathbb{M}}(x+\bm{\varepsilon})\\}_{x\in\mathbb{R}^{n}}$,
$\bm{\varepsilon}=(\varepsilon,\dots,\varepsilon)\in\mathbb{R}^{n}$, and
$\varphi$ and $\psi$ are the transition maps of ${\mathbb{M}}$ and
${\mathbb{M}}^{\prime}$ respectively. The interleaving distance between two
multiparameter persistence modules ${\mathbb{M}}$ and ${\mathbb{M}}^{\prime}$
is then defined as $d_{\rm
I}({\mathbb{M}},{\mathbb{M}}^{\prime}):=\inf\left\\{\varepsilon\geq
0:{\mathbb{M}}\text{ and }{\mathbb{M}}^{\prime}\text{ are
}\bm{\varepsilon}\text{-interleaved}\right\\}.$

The main property of this distance is that it is stable for multi-filtrations
that are obtained from the sublevel sets of functions. More precisely, given
two continuous functions $f,g:S\to\mathbb{R}^{n}$ defined on a simplicial
complex $S$, let ${\mathbb{M}}(f),{\mathbb{M}}(g)$ denote the multiparameter
persistence modules obtained from the corresponding multifiltrations
$\\{S^{f}_{x}:=\\{\sigma\in S:f(\sigma)\leq x\\}\\}_{x\in\mathbb{R}^{n}}$ and
$\\{S_{x}^{g}:=\\{\sigma\in S:g(\sigma)\leq x\\}\\}_{x\in\mathbb{R}^{n}}$.
Then, one has [28, Theorem 5.3]:

$d_{\rm I}({\mathbb{M}}(f),{\mathbb{M}}(g))\leq\left\lVert
f-g\right\rVert_{\infty}.$ (9)

Another usual distance is the bottleneck distance [3, Section 2.3].
Intuitively, it relies on decompositions of the modules into direct sums of
indecomposable summands555Recall that a module ${\mathbb{M}}$ is
indecomposable. if ${\mathbb{M}}\cong A\oplus B\Rightarrow{\mathbb{M}}\simeq
A\text{ or }{\mathbb{M}}\simeq B$ . (which are not necessarily intervals), and
is defined as the largest interleaving distance between summands that are
matched under some matching.

######  Definition 9 (Bottleneck distance).

Given two multisets $A$ and $B$, $\mu\colon A\not\to B$ is called a matching
if there exist $A^{\prime}\subseteq A$ and $B^{\prime}\subseteq B$ such that
$\mu\colon A^{\prime}\to B^{\prime}$ is a bijection. The subset
$A^{\prime}:=\mathrm{coim}(\mu)$ (resp. $B^{\prime}:=\mathrm{im}(\mu)$) is
called the coimage (resp. image) of $\mu$.

Let ${\mathbb{M}}\cong\bigoplus_{i\in\mathcal{I}}M_{i}$ and
${\mathbb{M}}^{\prime}\cong\bigoplus_{j\in\mathcal{J}}M^{\prime}_{j}$ be two
multiparameter persistence modules. Given $\varepsilon\geq 0$, the modules
${\mathbb{M}}$ and ${\mathbb{M}}^{\prime}$ are $\bm{\varepsilon}$-_matched_ if
there exists a matching $\mu\colon\mathcal{I}\not\to\mathcal{J}$ such that
$M_{i}$ and $M^{\prime}_{\mu(i)}$ are $\bm{\varepsilon}$-interleaved for all
$i\in\mathrm{coim}(\mu)$, and $M_{i}$ (resp. $M^{\prime}_{j}$) is
$\bm{\varepsilon}$-interleaved with the null module 0 for all
$i\in\mathcal{I}\backslash\mathrm{coim}(\mu)$ (resp.
$j\in\mathcal{J}\backslash\mathrm{im}(\mu)$).

The bottleneck distance between two multiparameter persistence modules
${\mathbb{M}}$ and ${\mathbb{M}}^{\prime}$ is then defined as $d_{\rm
B}({\mathbb{M}},{\mathbb{M}}^{\prime}):=\inf\left\\{\varepsilon\geq
0\,:\,{\mathbb{M}}\text{ and }{\mathbb{M}}^{\prime}\text{ are
}\bm{\varepsilon}\text{-matched}\right\\}.$

Since a matching between the decompositions of two multiparameter persistence
modules induces an interleaving between the modules themselves, it follows
that $d_{\rm I}\leq d_{\rm B}$. Note also that $d_{\rm B}$ can actually be
arbitrarily larger than $d_{\rm I}$, as showcased in [3, Section 9].

##  Appendix E The fibered barcode and its properties

######  Definition 10.

Let $n\in\mathbb{N}^{*}$ and $F=\\{F^{(1)},\dots,F^{(n)}\\}$ be a
multifiltration on a topological space $X$. Let ${\bf e},b\in\mathbb{R}^{n}$,
and $\ell_{{\bf e},b}:\mathbb{R}\rightarrow\mathbb{R}^{n}$ be the line in
$\mathbb{R}^{n}$ defined with $\ell_{{\bf e},b}(t)=t\cdot{\bf e}+b$, that is,
$\ell_{{\bf e},b}$ is the line of direction ${\bf e}$ passing through $b$. Let
$F_{{\bf e},b}:\mathbb{R}\rightarrow\mathcal{P}(X)$ defined with $F_{{\bf
e},b}(t)=\bigcap_{i=1}^{n}F^{(i)}([\ell_{{\bf e},b}(t)]_{i})$, where
$[\cdot]_{i}$ denotes the $i$-th coordinate. Then, each $F_{{\bf e},b}$ is a
single-parameter filtration and has a corresponding persistence barcode
$B_{{\bf e},b}$. The set $\mathcal{B}(F)=\\{B_{{\bf e},b}\,:\,{\bf
e},b\in\mathbb{R}^{n}\\}$ is called the fibered barcode of $F$.

The two following lemmas from [25] describe two useful properties of the
fibered barcode.

######  Lemma 1 (Lemma 1 in [25]).

Let ${\bf e},b\in\mathbb{R}^{n}$ and $\ell_{{\bf e},b}$ be the corresponding
line. Let $\hat{e}={\rm min}_{i}[{\bf e}]_{i}$. Let $F,F^{\prime}$ be two
multi-filtrations, ${\mathbb{M}},{\mathbb{M}}^{\prime}$ be the corresponding
persistence modules and $B_{{\bf e},b}\in\mathcal{B}(F)$ and $B^{\prime}_{{\bf
e},b}\in\mathcal{B}(F^{\prime})$ be the corresponding barcodes in the fibered
barcodes of $F$ and $F^{\prime}$. Then, the following stability property
holds:

$d_{\rm B}(B_{{\bf e},b},B^{\prime}_{{\bf e},b})\leq\frac{d_{\rm
I}({\mathbb{M}},{\mathbb{M}}^{\prime})}{\hat{e}}.$ (10)

######  Lemma 2 (Lemma 2 in [25]).

Let ${\bf e},{\bf e}^{\prime},b,b^{\prime}\in\mathbb{R}^{n}$ and $\ell_{{\bf
e},b}$, $\ell_{{\bf e}^{\prime},b^{\prime}}$ be the corresponding lines. Let
$\hat{e}={\rm min}_{i}[{\bf e}]_{i}$ and $\hat{e}^{\prime}={\rm min}_{i}[{\bf
e}^{\prime}]_{i}$. Let $F$ be a multi-filtration, ${\mathbb{M}}$ be the
corresponding persistence module and $B_{{\bf e},b},B_{{\bf
e}^{\prime},b^{\prime}}\in\mathcal{B}(F)$ be the corresponding barcodes in the
fibered barcode of $F$. Assume ${\mathbb{M}}$ is decomposable
${\mathbb{M}}=\oplus_{i=1}^{m}M_{i}$, and let $K>0$ such that $M_{i}\subseteq
B_{\infty}(0,K):=\\{x\in\mathbb{R}^{n}\,:\,\left\lVert
x\right\rVert_{\infty}\leq K\\}$ for all $i\in\llbracket 1,m\rrbracket$. Then,
the following stability property holds:

$d_{\rm B}(B_{{\bf e},b},B_{{\bf
e}^{\prime},b^{\prime}})\leq\frac{(K+\max\\{\left\lVert
b\right\rVert_{\infty},\left\lVert
b^{\prime}\right\rVert_{\infty}\\})\cdot\left\lVert{\bf e}-{\bf
e}^{\prime}\right\rVert_{\infty}+\left\lVert
b-b^{\prime}\right\rVert_{\infty}}{\hat{e}\cdot\hat{e}^{\prime}}.$ (11)

##  Appendix F Proof of Theorem 1

Our proof is based on several lemmas. In the first one, we focus on the S-CDR
weight function $w$ as defined in Definition 2.

######  Lemma 3.

Let $M$ and $M^{\prime}$ be two interval modules with compact support. Then,
one has

$d_{\rm
I}(M,0)=\frac{1}{2}\sup_{b,d\in\mathrm{supp}(M)}\min_{j}(d_{j}-b_{j})_{+}=w(M).$
(12)

Furthermore, one has the equality

$|w(M)-w(M^{\prime})|\leq d_{\rm I}(M,M^{\prime}).$ (13)

###### Proof.

We first show Equation (12) with two inequalities.

First inequality: $\leq$ Let $M$ be an interval module. If $d_{\rm I}(M,0)=0$,
then the inequality is trivial, so we now assume that $d_{\rm I}(M,0)>0$. Let
$\delta>0$ such that $\delta<d_{\rm I}(M,0)$. By definition of $d_{\rm I}$,
the identity morphism $M\to M_{2\bm{\delta}}$ cannot be factorized by $0$.
This implies the existence of some $b\in\mathbb{R}^{n}$ such that
$\mathrm{rank}(M(b)\to M(b+2\bm{\delta}))>0$; in particular,
$b,b+2\bm{\delta}\in{\rm supp}\left(M\right)$. Making $\delta$ converge to
$d_{\rm I}(M,0)$ yields the desired inequality.

Second inequality: $\geq$ Let $(K_{n})_{n\in\mathbb{N}}$ be a compact interval
exhaustion of ${\rm supp}\left(M\right)$, and $b_{n},d_{n}\in K_{n}$ be two
points that achieve the maximum in

$\frac{1}{2}\sup_{b,d\in K_{n}}\min_{j}(d_{j}-b_{j})_{+}.$

Now, by functoriality of persistence modules, we can assume without loss of
generality that $b_{n}$ and $d_{n}$ are on the same diagonal line (indeed, if
they are not, it is possible to transform $d_{n}$ into $\tilde{d}_{n}$ such
that $b_{n}$ and $\tilde{d}_{n}$ are on the same diagonal line and also
achieve the supremum). Thus, $\mathrm{rank}(M(b_{n})\to M(d_{n}))>0$, and
$d_{\rm I}(M,0)\geq\frac{1}{2}\left\lVert d_{n}-b_{n}\right\rVert_{\infty}$.
Taking the limit over $n\in\mathbb{N}$ leads to the desired inequality.

Inequality (13) follows directly from the triangle inequality applied on
$d_{\rm I}$.

∎

In the following lemma, we rewrite volumes of interval module supports using
interleaving distances.

######  Lemma 4.

Let $M$ be an interval module, and $R\subseteq\mathbb{R}^{n}$ be a compact
rectangle, with $n\geq 2$. Then, one has:

${\rm vol}\left({\rm supp}\left(M\right)\cap
R\right)=2\int_{\left\\{y\in\mathbb{R}^{n}:y_{n}=0\right\\}}d_{\rm
I}\left({\left.\kern-1.2ptM\vphantom{\big{|}}\right|_{l_{y}\cap
R}},0\right)\,\mathrm{d}\lambda^{n-1}(y)$

where $l_{y}$ is the diagonal line crossing $y$, and $\lambda^{n-1}$ denotes
the Lebesgue measure in $\mathbb{R}^{n-1}$.

###### Proof.

Using the change of variables $y_{i}=x_{i}-x_{n}$ and $t=x_{n}$ (which has a
trivial Jacobian) yields the following inequalities:

$\displaystyle{\rm vol}({\rm supp}\left(M\right)\cap R)$
$\displaystyle=\int_{{\rm supp}\left(M\right)\cap
R}\,\mathrm{d}\lambda^{n}(x)$
$\displaystyle=\int_{\left\\{y\in\mathbb{R}^{n}:y_{n}=0\right\\}}\int_{t\in\mathbb{R}}\mathds{1}_{{\rm
supp}\left(M\right)\cap R}(y+\bm{t})\,\mathrm{d}t\,\mathrm{d}\lambda^{n-1}(y)$
$\displaystyle=\int_{\left\\{y\in\mathbb{R}^{n}:y_{n}=0\right\\}}\mathrm{diam}_{\left\lVert\cdot\right\rVert_{\infty}}\left({{\rm
supp}\left(M\right)\cap l_{y}\cap R}\right)\,\mathrm{d}\lambda^{n-1}(y)$

where $l_{y}$ is the diagonal line passing through $y$. Now, since $M$ is an
interval module, one has
$\mathrm{diam}_{\left\lVert\cdot\right\rVert_{\infty}}\left({{\rm
supp}\left(M\right)\cap l_{y}\cap R}\right)=2d_{\rm
I}({\left.\kern-1.2ptM\vphantom{\big{|}}\right|_{l_{y}\cap R}},0)$, which
concludes the proof.

∎

In the following proposition, we provide stability bounds for single interval
modules.

######  Proposition 1.

If $M$ and $M^{\prime}$ are two interval modules, then for any $\delta>0$ and
S-CDR parameter $\phi_{\delta}$ in Definition 2, one has:

  1. 1.

$0\leq\phi_{\delta}(M)(x)\leq\frac{w(M)}{\delta}\wedge 1$, for any
$x\in\mathbb{R}^{n}$,

  2. 2.

$\left\lVert\phi_{\delta}(M)-\phi_{\delta}(M^{\prime})\right\rVert_{\infty}\leq
2(d_{\rm I}(M,M^{\prime})\wedge\delta)/\delta$.

###### Proof.

Claim 1. is a simple consequence of Equation (12).

Claim 2. for S-CDR parameter (a) is a simple consequence of the triangle
inequality.

Let us prove Claim 2. for (b). Let $x\in\mathbb{R}^{n}$ and $\delta>0$. One
has:

$\displaystyle|\phi_{\delta}(M)(x)-\phi_{\delta}(M^{\prime})(x)|$
$\displaystyle\leq\frac{2}{(2\delta)^{n}}\int_{\left\\{y:y_{n}=0\right\\}}|d_{\rm
I}\left({\left.\kern-1.2ptM\vphantom{\big{|}}\right|_{l_{y}\cap
R_{x,\bm{\delta}}}},0\right)-d_{\rm
I}\left({\left.\kern-1.2ptM^{\prime}\vphantom{\big{|}}\right|_{l_{y}\cap
R_{x,\bm{\delta}}}},0\right)|\,\mathrm{d}\lambda^{n-1}(y)$
$\displaystyle\leq\frac{2}{(2\delta)^{n}}\int_{\left\\{y:y_{n}=0\right\\}}d_{\rm
I}\left({\left.\kern-1.2ptM\vphantom{\big{|}}\right|_{l_{y}\cap
R_{x,\bm{\delta}}}},{\left.\kern-1.2ptM^{\prime}\vphantom{\big{|}}\right|_{l_{y}\cap
R_{x,\bm{\delta}}}}\right)\,\mathrm{d}\lambda^{n-1}(y)$ $\displaystyle\leq
2(d_{\rm I}(M,M^{\prime})\wedge\delta)/\delta,$

where the first inequality comes from Lemma 4, the second inequality is an
application of the triangle inequality, and the third inequality comes from
Lemma 1.

Finally, let us prove Claim 2. for (c). Let $x\in\mathbb{R}^{n}$ and
$\delta>0$. Let $b\leq d\in{\rm supp}\left(M\right)\cap R_{x,\bm{\delta}}$.
Let also $\gamma>0$. Then, using Lemma 4, one has:

$\displaystyle\frac{1}{(2\delta)^{n}}{\rm vol}({\rm supp}\left(M\right)\cap
R_{b,d})$
$\displaystyle=\frac{2}{(2\delta)^{n}}\int_{\left\\{y\in\mathbb{R}^{n}:y_{n}=0\right\\}}d_{\rm
I}({\left.\kern-1.2ptM\vphantom{\big{|}}\right|_{R_{b,d}\cap
l_{y}}},0)\,\mathrm{d}\lambda^{n-1}(y)$
$\displaystyle\leq\frac{2}{\delta}\gamma+\frac{2}{(2\delta)^{n}}\int_{\left\\{y\in\mathbb{R}^{n}:y_{n}=0\right\\}}d_{\rm
I}({\left.\kern-1.2ptM\vphantom{\big{|}}\right|_{R_{b+\bm{\gamma},d-\bm{\gamma}}\cap
l_{y}}},0)\,\mathrm{d}\lambda^{n-1}(y),$

using the convention $R_{a,b}=\varnothing$ if $a\not\leq b$. Now, set
$\gamma:=d_{\rm
I}({\left.\kern-1.2ptM\vphantom{\big{|}}\right|_{R_{x,\bm{\delta}}}},{\left.\kern-1.2ptM^{\prime}\vphantom{\big{|}}\right|_{R_{x,\bm{\delta}}}})$.
If $b+\bm{\gamma}$ or $d-\bm{\gamma}\not\in{\rm supp}\left(M^{\prime}\right)$
then $d_{\rm
I}({\left.\kern-1.2ptM\vphantom{\big{|}}\right|_{R_{x,\bm{\delta}}}},{\left.\kern-1.2ptM^{\prime}\vphantom{\big{|}}\right|_{R_{x,\bm{\delta}}}})=\gamma>d_{\rm
I}(M,M^{\prime})$ which is impossible. Thus,

$\displaystyle\frac{1}{(2\delta)^{n}}{\rm vol}(R_{b,d})$
$\displaystyle\leq{2d_{\rm
I}({\left.\kern-1.2ptM\vphantom{\big{|}}\right|_{R_{x,\bm{\delta}}}},{\left.\kern-1.2ptM^{\prime}\vphantom{\big{|}}\right|_{R_{x,\bm{\delta}}}})}/{\delta}$
$\displaystyle\ \ \ \ \ \ \ +\sup_{a,c\in R_{x,\bm{\delta}}\cap{\rm
supp}\left(M^{\prime}\right)}\frac{2}{(2\delta)^{n}}\int_{\left\\{y\in\mathbb{R}^{n}:y_{n}=0\right\\}}d_{\rm
I}({\left.\kern-1.2ptM\vphantom{\big{|}}\right|_{R_{a,c}\cap
l_{y}}},0)\,\mathrm{d}\lambda^{n-1}(y)$ $\displaystyle={2d_{\rm
I}({\left.\kern-1.2ptM\vphantom{\big{|}}\right|_{R_{x,\bm{\delta}}}},{\left.\kern-1.2ptM^{\prime}\vphantom{\big{|}}\right|_{R_{x,\bm{\delta}}}})}/{\delta}+\phi_{\delta}(M^{\prime})(x)$

Finally, taking the supremum on $b\leq d\in{\rm supp}\left(M\right)\cap
R_{x,\bm{\delta}}$ yields

$\phi_{\delta}(M)(x)-\phi_{\delta}(M^{\prime})(x)\leq 2d_{\rm
I}({\left.\kern-1.2ptM\vphantom{\big{|}}\right|_{R_{x,\bm{\delta}}}},{\left.\kern-1.2ptM^{\prime}\vphantom{\big{|}}\right|_{R_{x,\bm{\delta}}}})/\delta\leq
2\left(d_{\rm I}(M,M^{\prime})\wedge\delta\right)/\delta.$

The desired inequality follows by symmetry on $M$ and $M^{\prime}$.

∎

Equipped with these results, we can finally prove Theorem 1.

###### Proof.

Theorem 1.

Let ${\mathbb{M}}=\oplus_{i=1}^{m}M_{i}$ and
${\mathbb{M}}^{\prime}=\oplus_{j=1}^{m^{\prime}}M^{\prime}_{j}$ be two modules
that are decomposable into interval modules and $x\in\mathbb{R}^{n}$.

Inequality 5. To simplify notations, we define the following:
$w_{i}:=w(M_{i})$, $\phi_{i,x}:=\phi_{\delta}(M_{i})(x)$ and
$w_{j}^{\prime}:=w(M^{\prime}_{j})$,
$\phi_{j,x}^{\prime}:=\phi_{\delta}(x,M^{\prime}_{j})$. Let us also assume
without loss of generality that the indices are consistent with a matching
achieving the bottleneck distance. In other words, the bottleneck distance is
achieved for a matching that matches $M_{i}$ with $M^{\prime}_{i}$ for every
$i$ (up to adding $0$ modules in the decompositions of ${\mathbb{M}}$ and
${\mathbb{M}}^{\prime}$ so that $m=m^{\prime}$). Finally, assume without loss
of generality that $\sum_{i}w_{i}^{\prime}\geq\sum_{i}w_{i}$. Then, one has:

$\displaystyle|V_{1,\delta}({\mathbb{M}})(x)-V_{1,\delta}({\mathbb{M}}^{\prime})(x)|$
$\displaystyle=\left|\frac{1}{\sum_{i}w_{i}}\sum_{i}w_{i}\phi_{i,x}-\frac{1}{\sum_{i}w_{i}^{\prime}}\sum_{i}w_{i}^{\prime}\phi_{i,x}^{\prime}\right|$
$\displaystyle\leq\frac{1}{\sum_{i}w_{i}^{\prime}}\left|\sum_{i}w_{i}\phi_{i,x}-\sum_{i}w_{i}^{\prime}\phi_{i,x}^{\prime}\right|+\left|\frac{1}{\sum_{i}w_{i}}-\frac{1}{\sum_{i}w_{i}^{\prime}}\right|\left|\sum_{i}w_{i}\phi_{i,x}\right|.$

Now, for any index $i$, since $d_{\rm I}(M_{i},M^{\prime}_{i})\leq d_{\rm
B}({\mathbb{M}},{\mathbb{M}}^{\prime})$ and $|w_{i}-w_{i}^{\prime}|\leq d_{\rm
I}(M_{i},M^{\prime}_{i})\leq d_{\rm B}({\mathbb{M}},{\mathbb{M}}^{\prime})$ by
Lemma 3, Proposition 1 ensures that:

$|w_{i}\phi_{i,x}-w_{i}^{\prime}\phi_{i,x}^{\prime}|\leq|w_{i}-w_{i}^{\prime}|\phi_{i,x}+w_{i}^{\prime}|\phi_{i,x}-\phi_{i,x}^{\prime}|\leq
2(w_{i}+w_{i}^{\prime})(d_{\rm
B}({\mathbb{M}},{\mathbb{M}}^{\prime})\wedge\delta)/\delta$

and

$\left|\frac{1}{\sum_{i}w_{i}}-\frac{1}{\sum_{i}w_{i}^{\prime}}\right|\leq\frac{1}{\sum_{i}w_{i}^{\prime}}\left|\frac{\sum_{i}w_{i}^{\prime}-w_{i}}{\sum_{i}w_{i}}\right|\leq\frac{md_{\rm
B}({\mathbb{M}},{\mathbb{M}}^{\prime})}{(\sum_{i}w^{\prime}_{i})(\sum_{i}w_{i})}.$

Finally,

$\displaystyle|V_{1,\delta}({\mathbb{M}})(x)-V_{1,\delta}({\mathbb{M}}^{\prime})(x)|$
$\displaystyle\leq\left[\frac{\sum_{i}w_{i}+w_{i}^{\prime}}{\sum_{i}w_{i}^{\prime}}+\frac{\sum_{i}w_{i}}{\frac{1}{m}(\sum_{i}w_{i})(\sum_{i}w_{i}^{\prime})}\right]2(d_{\rm
B}({\mathbb{M}},{\mathbb{M}}^{\prime})\wedge\delta)/\delta$
$\displaystyle\leq\left[4+\frac{2}{C}\right](d_{\rm
B}({\mathbb{M}},{\mathbb{M}}^{\prime})\wedge\delta)/\delta.$

Inequality 4 can be proved using the proof of Inequality 5 by replacing every
$w_{i}$ by 1.

Inequality 6. Let us prove the inequality for (b). Let
$R:=R_{x-\bm{\delta},x+\bm{\delta}}$. One has:

$\displaystyle V_{\infty,\delta}({\mathbb{M}})(x)-V_{\infty,\delta}$
$\displaystyle({\mathbb{M}}^{\prime})(x)=$
$\displaystyle\sup_{i}\frac{2}{(2\delta)^{n}}\int_{\left\\{y\in\mathbb{R}^{n}:y_{n}=0\right\\}}d_{\rm
I}({\left.\kern-1.2ptM_{i}\vphantom{\big{|}}\right|_{l_{y}\cap
R}},0)\,\mathrm{d}\lambda^{n-1}(y)$ $\displaystyle-$
$\displaystyle\sup_{j}\frac{2}{(2\delta)^{n}}\int_{\left\\{y\in\mathbb{R}^{n}:y_{n}=0\right\\}}d_{I}({\left.\kern-1.2ptM^{\prime}_{j}\vphantom{\big{|}}\right|_{l_{y}\cap
R}},0)\,\mathrm{d}\lambda^{n-1}(y)$ $\displaystyle\emph{\footnotesize(for any
index $j$)}\leq$
$\displaystyle\sup_{i}\frac{2}{(2\delta)^{n}}\int_{\left\\{y\in\mathbb{R}^{n}:y_{n}=0\right\\}}d_{\rm
I}({\left.\kern-1.2ptM_{i}\vphantom{\big{|}}\right|_{l_{y}\cap R}},0)-d_{\rm
I}({\left.\kern-1.2ptM^{\prime}_{j}\vphantom{\big{|}}\right|_{l_{y}\cap
R}},0)\,\mathrm{d}\lambda^{n-1}(y)$ $\displaystyle\leq$
$\displaystyle\frac{2}{(2\delta)^{n}}\int_{\left\\{y\in\mathbb{R}^{n}:y_{n}=0\right\\}}\sup_{i}\inf_{j}d_{\rm
I}({\left.\kern-1.2ptM_{i}\vphantom{\big{|}}\right|_{l_{y}\cap
R}},{\left.\kern-1.2ptM^{\prime}_{j}\vphantom{\big{|}}\right|_{l_{y}\cap
R}})\,\mathrm{d}\lambda^{n-1}(y)$

Now, as the interleaving distance is equal to the bottleneck distance for
single parameter persistence [11, Theorem 5.14], one has:

$\sup_{i}\inf_{j}d_{\rm
I}({\left.\kern-1.2ptM_{i}\vphantom{\big{|}}\right|_{l_{y}\cap
R}},{\left.\kern-1.2ptM^{\prime}_{j}\vphantom{\big{|}}\right|_{l_{y}\cap
R}})\leq d_{\rm
B}({\left.\kern-1.2pt{\mathbb{M}}\vphantom{\big{|}}\right|_{l_{y}\cap
R}},{\left.\kern-1.2pt{\mathbb{M}}^{\prime}\vphantom{\big{|}}\right|_{l_{y}\cap
R}})=d_{\rm
I}({\left.\kern-1.2pt{\mathbb{M}}\vphantom{\big{|}}\right|_{l_{y}\cap
R}},{\left.\kern-1.2pt{\mathbb{M}}^{\prime}\vphantom{\big{|}}\right|_{l_{y}\cap
R}})\leq d_{\rm I}({\mathbb{M}},{\mathbb{M}}^{\prime})\wedge\delta$

which leads to the desired inequality. The proofs for (a) and (c) follow the
same lines (upper bound the suprema in the right hand term with either infima
or appropriate choices in order to reduce to the single parameter case). ∎

##  Appendix G An additional stability theorem

In this section, we define a new S-CDR, with a slightly different type of
upper bound. It relies on the fibered barcode introduced in Appendix E. We
also slightly abuse notations and use $M_{i}$ to denote both an interval
module and its support.

######  Proposition 2.

Let ${\mathbb{M}}\simeq\oplus_{i=1}^{m}M_{i}$ be a multiparameter persistence
module that can be decomposed into interval modules. Let $\sigma>0$, and let
$0\leq\delta\leq\delta({\mathbb{M}})$, where

$\delta({\mathbb{M}}):={\rm inf}\\{\delta\geq 0:\Gamma_{{\mathbb{M}}}{\rm\
achieves\ }d_{\rm B}(B_{{\bf e}_{\Delta},x},B_{{\bf e}_{\Delta},x+\delta{{\bf
u}}}){\rm\ for\ all\ }x,{\bf u}{\rm\ s.t.\ }\left\lVert{{\bf
u}}\right\rVert_{\infty}=1,\langle{\bf e}_{\Delta},{\bf u}\rangle=0\\},$

where $\Gamma_{{\mathbb{M}}}$ is the partial matching induced by the
decomposition of ${\mathbb{M}}$. Let $\mathcal{N}(x,\sigma)$ denote the
function
$\mathcal{N}(x,\sigma):\left\\{\begin{array}[]{ll}\mathbb{R}^{n}&\rightarrow\mathbb{R}\\\
p&\mapsto{\rm exp}\left(-\frac{\left\lVert
p-x\right\rVert^{2}}{2\sigma^{2}}\right)\end{array}\right.$ and let

$V_{\delta,\sigma}({\mathbb{M}}):\left\\{\begin{array}[]{ll}\mathbb{R}^{n}&\rightarrow\mathbb{R}\\\
x&\mapsto\max_{1\leq i\leq m}\ \ \max_{f\in\mathcal{C}(x,\delta,M_{i})}\ \
\left\lVert\mathcal{N}(x,\sigma)\cdot f\right\rVert_{1}\end{array}\right.$
(14)

where $\mathcal{C}(x,\delta,M_{i})$ stands for the set of interval functions
from $\mathbb{R}^{n}$ to $\\{0,1\\}$ whose support is $T_{\delta}(\ell)\cap
M_{i}$, where $\ell$ is a connecting component of ${\rm im}(\ell_{{\bf
e}_{\Delta},x})\cap M_{i}$ and ${\bf
e}_{\Delta}=[1,\dots,1]\in\mathbb{R}^{n}$, and where $T_{\delta}(\ell)$ is the
$\delta$-thickening of the line $L(\ell)$ induced by $\ell$:
$T_{\delta}(\ell)=\\{x\in\mathbb{R}^{k}\,:\,\left\lVert
x,L(\ell)\right\rVert_{\infty}\leq\delta\\}$.

Then, $V_{\delta,\sigma}$ satisfies the following stability property:

$\left\lVert
V_{\delta,\sigma}({\mathbb{M}})-V_{\delta,\sigma}({\mathbb{M}}^{\prime})\right\rVert_{\infty}\leq(\sqrt{\pi}\sigma)^{n}\cdot\sqrt{2^{n+1}\delta^{n-1}d_{\rm
I}({\mathbb{M}},{\mathbb{M}}^{\prime})+C_{n}(\delta)},$ (15)

where $C_{n}(\cdot)$ is a continuous function such that
$C_{n}(\delta)\rightarrow 0$ when $\delta\rightarrow 0$.

###### Proof.

Let ${\mathbb{M}}=\oplus_{i=1}^{m}M_{i}$ and
${\mathbb{M}}^{\prime}=\oplus_{j=1}^{m^{\prime}}M^{\prime}_{j}$ be two
persistence modules that are decomposable into intervals, let
$x\in\mathbb{R}^{k}$ and let
$0\leq\delta\leq\min\\{\delta({\mathbb{M}}),\delta({\mathbb{M}}^{\prime})\\}$.

#### Notations.

We first introduce some notations. Let $N$ (resp. $N^{\prime}$) be the number
of bars in $B_{{\bf e}_{\Delta},x}$ (resp. $B^{\prime}_{{\bf e}_{\Delta},x}$),
and assume without loss of generality that $N\leq N^{\prime}$. Let $\Gamma$ be
the partial matching achieving $d_{\rm B}(B_{{\bf
e}_{\Delta},x},B^{\prime}_{{\bf e}_{\Delta},x})$. Let $N_{1}$ (resp. $N_{2}$)
be the number of bars in $B_{{\bf e}_{\Delta},x}$ that are matched (resp. not
matched) to a bar in $B^{\prime}_{{\bf e}_{\Delta},x}$ under $\Gamma$, so that
$N=N_{1}+N_{2}$. Finally, note that $B_{{\bf
e}_{\Delta},x}=\\{\ell\,:\,\exists i{\rm\ such\ that\
}\ell\in{\mathcal{C}}({\rm im}(\ell_{{\bf e}_{\Delta},x})\cap M_{i}){\rm\ and\
}{\rm im}(\ell_{{\bf e}_{\Delta},x})\cap M_{i}\neq\emptyset\\}$, where
$\mathcal{C}$ stands for the set of connected components (and similarly for
$B^{\prime}_{{\bf e}_{\Delta},x}$), and let $F_{\Gamma}:B_{{\bf
e}_{\Delta},x}\rightarrow B^{\prime}_{{\bf e}_{\Delta},x}$ be a function
defined on all bars of $B_{{\bf e}_{\Delta},x}$ that coincides with $\Gamma$
on the $N_{1}$ bars of $B_{{\bf e}_{\Delta},x}$ that have an associated bar in
$B^{\prime}_{{\bf e}_{\Delta},x}$, and that maps the $N_{2}$ remaining bars of
$B_{{\bf e}_{\Delta},x}$ to some arbitrary bars in the $(N^{\prime}-N_{1})$
remaining bars of $B^{\prime}_{{\bf e}_{\Delta},x}$.

#### A reformulation of the problem with vectors.

We now derive vectors that allow to reformulate the problem in a useful way.
Let $\hat{V}$ be the sorted vector of dimension $N$ containing all weights
$\left\lVert\mathcal{N}(x,\sigma)\cdot f\right\rVert_{1}$, where $f$ is the
interval function whose support is $T_{\delta}(\ell)\cap M_{i}$ for some
$M_{i}$, where $\ell\in B_{{\bf e}_{\Delta},x}$ is a connected component of
${\rm im}(\ell_{{\bf e}_{\Delta},x})\cap M_{i}$. Now, let $\hat{V}^{\prime}$
be the vector of dimension $N^{\prime}$ obtained by concatenating the two
following vectors:

  * •

the vector $\hat{V}^{\prime}_{1}$ of dimension $N$ whose $i$th coordinate is
$\left\lVert\mathcal{N}(x,\sigma)\cdot f^{\prime}\right\rVert_{1}$, where
$f^{\prime}$ is the interval function whose support is
$T_{\delta}(\ell^{\prime})\cap M^{\prime}_{j}$ for some $M^{\prime}_{j}$, and
$\ell^{\prime}\in B^{\prime}_{{\bf e}_{\Delta},x}$ is the image under $\Gamma$
of the bar $\ell\in B_{{\bf e}_{\Delta},x}$ corresponding to the $i$th
coordinate of $\hat{V}$, i.e., $\ell^{\prime}=F_{\Gamma}(\ell)$ where
$[\hat{V}]_{i}=\left\lVert\mathcal{N}(x,\sigma)\cdot f\right\rVert_{1}$ and
$f$ is the interval function whose support is $T_{\delta}(\ell)\cap M_{i_{0}}$
for some $M_{i_{0}}$. In other words, $\hat{V}^{\prime}_{1}$ is the (not
necessarily sorted) vector of weights computed on the bars of
$B^{\prime}_{{\bf e}_{\Delta},x}$ that are images (under the partial matching
$\Gamma$ achieving the bottleneck distance) of the bars of $B_{{\bf
e}_{\Delta},x}$ that were used to generate the (sorted) vector $\hat{V}$.

  * •

the vector $\hat{V}^{\prime}_{2}$ of dimension $(N^{\prime}-N)$ whose $j$th
coordinate is $\left\lVert\mathcal{N}(x,\sigma)\cdot
f^{\prime}\right\rVert_{1}$, where $f^{\prime}$ is an interval function whose
support is $T_{\delta}(\ell^{\prime})\cap M^{\prime}_{j}$ for some
$M^{\prime}_{j}$, and $\ell^{\prime}\in B^{\prime}_{{\bf e}_{\Delta},x}$
satisfies $\ell^{\prime}\not\in{\rm im}(F_{\Gamma})$. In other words,
$\hat{V}^{\prime}_{2}$ is the vector of weights computed on the bars of
$B^{\prime}_{{\bf e}_{\Delta},x}$ (in an arbitrary order) that are not images
of bars of $B_{{\bf e}_{\Delta},x}$ under $\Gamma$.

Finally, we let $V$ be the vector of dimension $N^{\prime}$ obtained by
filling $\hat{V}$ (whose dimension is $N\leq N^{\prime}$) with null values
until its dimension becomes $N^{\prime}$, and we let $V^{\prime}={\rm
sort}(\hat{V}^{\prime})$ be the vector obtained after sorting the coordinates
of $\hat{V}^{\prime}$. Observe that:

$|V_{\delta,\sigma}({\mathbb{M}})(x)-V_{\delta,\sigma}({\mathbb{M}}^{\prime})(x)|=[V-V^{\prime}]_{1}=[V-{\rm
sort}(\hat{V}^{\prime})]_{1}$ (16)

#### An upper bound.

We now upper bound $\left\lVert V-\hat{V}^{\prime}\right\rVert_{\infty}$. Let
$q\in\llbracket 1,N^{\prime}\rrbracket$. Then, one has
$[V]_{q}=\left\lVert\mathcal{N}(x,\sigma)\cdot f\right\rVert_{1}$, where $f$
is an interval function whose support is $T_{\delta}(\ell)\cap M_{i}$ for some
$M_{i}$ with $\ell\in B_{{\bf e}_{\Delta},x}$ if $q\leq N$ and
$\ell=\emptyset$ otherwise; and similarly
$[\hat{V}^{\prime}]_{q}=\left\lVert\mathcal{N}(x,\sigma)\cdot
f^{\prime}\right\rVert_{1}$, where $f^{\prime}$ is an interval function whose
support is $T_{\delta}(\ell^{\prime})\cap M^{\prime}_{j}$ for some
$M^{\prime}_{j}$ with $\ell^{\prime}\in B^{\prime}_{{\bf e}_{\Delta},x}$.
Thus, one has:

$\displaystyle[V-\hat{V}^{\prime}]_{q}$
$\displaystyle=|\left\lVert\mathcal{N}(x,\sigma)\cdot
f\right\rVert_{1}-\left\lVert\mathcal{N}(x,\sigma)\cdot
f^{\prime}\right\rVert_{1}|$
$\displaystyle\leq\left\lVert\mathcal{N}(x,\sigma)\cdot
f-\mathcal{N}(x,\sigma)\cdot f^{\prime}\right\rVert_{1}\text{ by the reverse
triangle inequality}$
$\displaystyle=\left\lVert\mathcal{N}(x,\sigma)\cdot(f-f^{\prime})\right\rVert_{1}\text{
by linearity}$
$\displaystyle\leq\left\lVert\mathcal{N}(x,\sigma)\right\rVert_{2}\cdot\left\lVert
f-f^{\prime}\right\rVert_{2}\text{ by H\"{o}lder's inequality}$
$\displaystyle=(\sqrt{\pi}\sigma)^{k}\cdot\left\lVert
f-f^{\prime}\right\rVert_{2}$

Since $(f-f^{\prime})$ is an interval function whose support is
$(T_{\delta}(\ell)\cap M_{i})\triangle(T_{\delta}(\ell^{\prime})\cap
M^{\prime}_{j})$, one has $\left\lVert
f-f^{\prime}\right\rVert_{2}=\sqrt{|(T_{\delta}(\ell)\cap
M_{i})\triangle(T_{\delta}(\ell^{\prime})\cap M^{\prime}_{j})|}$. Given a
segment $\ell$ and a vector ${\bf u}$, we let $\ell_{{\bf u}}$ denote the
segment ${\bf u}+\ell$, and we let $\ell^{{\bf u}}$ denote the (infinite) line
induced by $\ell_{{\bf u}}$. More precisely:

$\displaystyle\left\lVert f-f^{\prime}\right\rVert^{2}_{2}$
$\displaystyle=|(T_{\delta}(\ell)\cap
M_{i})\triangle(T_{\delta}(\ell^{\prime})\cap M^{\prime}_{j})|$
$\displaystyle=|\bigcup_{{\bf u}}(\ell^{{\bf u}}\cap
M_{i})\triangle\bigcup_{{\bf u}}((\ell^{\prime})^{{\bf u}}\cap
M^{\prime}_{j})|$ $\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{ where }{\bf
u}\text{ ranges over the vectors such that }\left\lVert{\bf
u}\right\rVert_{\infty}\leq\delta,\langle{\bf u},{\bf e}_{\Delta}\rangle=0$
$\displaystyle\leq\int_{{\bf u}}|(\ell^{{\bf u}}\cap
M_{i})\triangle((\ell^{\prime})^{{\bf u}}\cap M^{\prime}_{j})|{\rm d}{\bf u}$
$\displaystyle\leq\int_{{\bf u}}|(\ell^{{\bf u}}\cap M_{i})\triangle(\ell\cap
M_{i})_{{\bf u}}|+|(\ell\cap M_{i})_{{\bf u}}\triangle(\ell^{\prime}\cap
M^{\prime}_{j})_{{\bf u}}|+|(\ell^{\prime}\cap M^{\prime}_{j})_{{\bf
u}}\triangle((\ell^{\prime})^{{\bf u}}\cap M^{\prime}_{j})|{\rm d}{\bf u}$
$\displaystyle\leq\int_{{\bf u}}4d_{\rm B}(B_{{\bf e}_{\Delta},x},B_{{\bf
e}_{\Delta},x+{\bf u}})+4d_{\rm B}(B_{{\bf e}_{\Delta},x},B^{\prime}_{{\bf
e}_{\Delta},x})+4d_{\rm B}(B^{\prime}_{{\bf e}_{\Delta},x},B^{\prime}_{{\bf
e}_{\Delta},x+{\bf u}}){\rm d}{\bf u}$ (17) $\displaystyle\leq 4\int_{{\bf
u}}\left\lVert{\bf u}\right\rVert_{\infty}+d_{\rm
I}({\mathbb{M}},{\mathbb{M}}^{\prime})+\left\lVert{\bf
u}\right\rVert_{\infty}{\rm d}{\bf u}\text{ by Lemma\leavevmode\nobreak\
\ref{lem:landi1} and\leavevmode\nobreak\ \ref{lem:landi2}}$

Inequality (17) comes from the fact that the symmetric difference between two
bars (in two different barcodes) that are both matched (or unmatched) by the
optimal partial matching is upper bounded by four times the bottleneck
distance between the barcodes, and that (by assumption) the partial matchings
achieving $d_{\rm B}(B_{{\bf e}_{\Delta},x},B_{{\bf e}_{\Delta},x+{\bf u}})$
and $d_{\rm B}(B^{\prime}_{{\bf e}_{\Delta},x},B^{\prime}_{{\bf
e}_{\Delta},x+{\bf u}})$ are induced by ${\mathbb{M}}$ and
${\mathbb{M}}^{\prime}$.

#### Conclusion.

Finally, one has

$\displaystyle|V_{\delta,\sigma}({\mathbb{M}})(x)-V_{\delta,\sigma}({\mathbb{M}}^{\prime})(x)|$
$\displaystyle=[V-V^{\prime}]_{1}=[V-{\rm sort}(\hat{V}^{\prime})]_{1}\text{
from Equation\leavevmode\nobreak\ (\ref{eq:reform})}$
$\displaystyle\leq\left\lVert V-V^{\prime}\right\rVert_{\infty}$
$\displaystyle\leq(\sqrt{\pi}\sigma)^{k}\cdot\sqrt{2^{n+1}\delta^{n-1}d_{\rm
I}({\mathbb{M}},{\mathbb{M}}^{\prime})+C_{n}(\delta)},$ (18)

with $C_{n}(\delta)=8\int_{{\bf u}}\left\lVert{\bf u}\right\rVert_{\infty}{\rm
d}{\bf u}\rightarrow 0$ when $\delta\rightarrow 0$. Inequality (18) comes from
the fact that any upper bound for the norm of the difference between a given
vector $\hat{V}^{\prime}$ and a sorted vector $V$, is also an upper bound for
the norm of the difference between the sorted version $V^{\prime}$ of
$\hat{V}^{\prime}$ and the same vector $V$ (see Lemma 3.9 in [16]). ∎

While the stability constant is not upper bounded by $\delta$,
$V_{\delta,\sigma}$ is more difficult to compute than the S-CDRs presented in
Definition 2.

##  Appendix H Pseudo-code for S-CDRs

In this section, we briefly present the pseudo-code that we use to compute
S-CDRs. Our code is based on implicit descriptions of the candidate
decompositions of multiparameter persistence modules (which are the inputs of
S-CDRs) through their so-called birth and death corners. These corners can be
obtained with, e.g., the public softwares MMA [26] and Rivet [29].

In order to compute our S-CDRs, we implement the following procedures:

  1. 1.

Given an interval module $M$ and a rectangle $R\subset\mathbb{R}^{n}$, compute
the restriction ${\left.\kern-1.2ptM\vphantom{\big{|}}\right|_{R}}$.

  2. 2.

Given an interval module $M$ (or
${\left.\kern-1.2ptM\vphantom{\big{|}}\right|_{R}}$), compute $d_{\rm
I}(M,0)$. This allows to compute our weight function and first interval
representation in Definition 2.

  3. 3.

Given an interval module restricted to a rectangle, compute the volume of the
biggest rectangle in the support of this module. This allows to compute the
third interval representation in Definition 2.

For the first point, Algorithm 1 works by "pushing" the corners of the
interval on the given rectangle in order to obtain the updated corners.

Data: birth and death corners of an interval module $M$, rectangle
$R=\\{z\in\mathbb{R}^{n}:m\leq z\leq M\\}$

Result: $\mathrm{new\\_interval\\_corners}$, the birth and death corners of
${\left.\kern-1.2ptM\vphantom{\big{|}}\right|_{R}}$.

for
_$\mathrm{interval}=\\{\mathrm{interval\\_birth\\_corners},\mathrm{interval\\_death\\_corners}\\}$
in  $M$_ do

$\mathrm{new\\_birth\\_list}\leftarrow[\,]$;

for  _$b$ in $\mathrm{interval\\_birth\\_corners}$_ do

if  _$b\leq M$_ then

$b^{\prime}=\\{\max(b_{i},m_{i})\text{ for }i\in\llbracket 1,n\rrbracket\\}$;

Append $b^{\prime}$ to $\mathrm{new\\_birth\\_list}$;

end if

end for

$\mathrm{new\\_death\\_list}\leftarrow[\,]$;

for  _$d$ in $\mathrm{interval\\_death\\_corners}$_ do

if  _$d\geq m$_ then

$d^{\prime}=\\{\min(d_{i},M_{i})\text{ for }i\in\llbracket 1,n\rrbracket\\}$;

Append $d^{\prime}$ to $\mathrm{new\\_death\\_list}$;

end if

end for

$\mathrm{new\\_interval\\_corners}\leftarrow[\mathrm{new\\_birth\\_list},\,\mathrm{new\\_death\\_list}]$;

end for

Algorithm 1 Restriction of an interval module to a rectangle

For the second point, we proved in Lemma 3 that our S-CDR weight function is
equal to $d_{\rm I}(M,0)$ and has a closed-form formula with corners, that we
implement in Algorithm 2.

Data: birth and death corners of an interval module $M$

Result: $\mathrm{distance}$, the interleaving distance $d_{I}(M,0)$.

$\mathrm{distance}\leftarrow 0$;

for  _$b$ in $M\mathrm{\\_birth\\_corners}$_ do

for  _$d$ in $M\mathrm{\\_death\\_corners}$_ do

$\mathrm{distance}\leftarrow\max\left(\mathrm{result},\frac{1}{2}\min_{i}(d_{i}-b_{i})_{+}\right)$;

end for

end for

Algorithm 2 S-CDR weight function

The third point also has a closed-form formula with corners, leading to
Algorithm 3.

Data: birth and death corners of an interval module $M$

Result: $\mathrm{volume}$, the volume of the biggest rectangle fitting in
${\rm supp}\left(M\right)$

$\mathrm{volume}\leftarrow 0$;

for  _$b$ in $M\mathrm{\\_birth\\_corners}$_ do

for  _$d$ in $M\mathrm{\\_death\\_corners}$_ do

$\mathrm{volume}\leftarrow\max\left(\mathrm{result},\Pi_{i}(d_{i}-b_{i})_{+}\right)$;

end for

end for

Algorithm 3 S-CDR interval representation

Finally, we show how to get persistence barcodes corresponding to slicings of
interval modules from its corners.

Data: birth and death corners of an interval module $M$, a diagonal line $l$

Result: $\mathrm{barcode}$, the persistence barcode associated to
${\left.\kern-1.2ptM\vphantom{\big{|}}\right|_{l}}$

$\mathrm{barcode}\leftarrow[\,]$;

$y\leftarrow\text{ an arbitrary point in $l$}$;

for
_$\mathrm{interval}=\\{\mathrm{interval\\_birth\\_corners},\mathrm{interval\\_death\\_corners}\\}$
in  $M$_ do

$\mathrm{birth}\leftarrow
y+\bm{1}\times\min_{b\in\mathrm{interval\\_birth\\_corners}}\max_{i}{b_{i}-y_{i}}$;

$\mathrm{death}\leftarrow
y+\bm{1}\times\max_{d\in\mathrm{interval\\_death\\_corners}}\min_{i}{d_{i}-y_{i}}$;

$\mathrm{bar}\leftarrow[\mathrm{birth},\mathrm{death}]$;

Append $\mathrm{bar}$ to $\mathrm{barcode}$;

end for

Algorithm 4 Restriction of an interval module to a line

##  Appendix I Full UCR results and acronyms

In this section, we provide accuracy scores (obtained with the same parameters
than Section 4.3) for several UCR data sets and classifiers (’svml[x]’ stands
for linear SVM with $C=$x, ’rf[x]’ stands for random forests with x trees, and
’lgbm[x]’ stands for gradient boosting from the LightGBM library with x
maximum tree leaves). A line indicates that the classifier training time
exceeded a reasonable amount of time.

Dataset | B1 | B2 | B3 | MPK | MPL | MPI | svml25 | svml 50 | rf50 | rf 100 | lgbm 100
---|---|---|---|---|---|---|---|---|---|---|---
DistalPhalanxOutlineAgeGroup (DPOAG) | 62.6 | 62.6 | 77.0 | 67.6 | 70.5 | 71.9 | 71.2 | 71.9 | 74.1 | 71.9 | 73.3
DistalPhalanxOutlineCorrect (DPOC) | 71.7 | 72.5 | 71.7 | 74.6 | 69.6 | 71.7 | 73.9 | 73.6 | 72.5 | 74.3 | 73.5
DistalPhalanxTW (DPTW) | 63.3 | 63.3 | 59.0 | 61.2 | 56.1 | 61.9 | 69.1 | 64.0 | 61.9 | 60.4 | 61.2
ProximalPhalanxOutlineAgeGroup (PPOAG) | 78.5 | 78.5 | 80.5 | 78.0 | 78.5 | 81.0 | 82.9 | 84.9 | 82.9 | 81.5 | 84.4
ProximalPhalanxOutlineCorrect (PPOC) | 80.8 | 79.0 | 78.4 | 78.7 | 78.7 | 81.8 | 79.4 | 80.4 | 82.1 | - | 84.9
ProximalPhalanxTW (PPTW) | 70.7 | 75.6 | 75.6 | 79.5 | 73.2 | 76.1 | 77.6 | 75.6 | 78.0 | 75.6 | 75.6
ECG200 | 88.0 | 88.0 | 77.0 | 77.0 | 74.0 | 83.0 | 83.0 | 86 | 83 | 86 | 82.0
ItalyPowerDemand (IPD) | 95.5 | 95.5 | 95.0 | 80.7 | 78.6 | 71.9 | 79.1 | 74.7 | 81.3 | 81.4 | 72.5
MedicalImages (MI) | 68.4 | 74.7 | 73.7 | 55.4 | 55.7 | 60.0 | 61.1 | 61.3 | 61.0 | 62.1 | 62.2
Plane (P) | 96.2 | 100.0 | 100.0 | 92.4 | 84.8 | 97.1 | 99.0 | 99.0 | 99.0 | 98.1 | 94.3
SwedishLeaf (SL) | 78.9 | 84.6 | 79.2 | 78.2 | 64.6 | 83.8 | 85.8 | 85.9 | 84.2 | 83.8 | 83.0
GunPoint (GP) | 91.3 | 91.3 | 90.7 | 88.7 | 94.0 | 90.7 | 90.7 | 99.3 | 93.3 | 91.3 | 88.7
GunPointAgeSpan (GPAS) | 89.9 | 96.5 | 91.8 | 93.0 | 85.1 | 90.5 | 91.8 | 87.0 | 84.5 | 85.1 | 89.2
GunPointMaleVersusFemale (GPMVF) | 97.5 | 97.5 | 99.7 | 96.8 | 88.3 | 95.9 | - | 94.5 | 81.6 | 86.7 | 95.9
PowerCons (PC) | 93.3 | 92.2 | 87.8 | 85.6 | 84.4 | 86.7 | 90.6 | 88 | 94.4 | 91.1 | 88.3
SyntheticControl (SC) | 88.0 | 98.3 | 99.3 | 50.7 | 60.3 | 60.0 | 61.3 | 59.3 | 60.7 | 59.7 | 60.0

Table 3: Classification results for time series.