COMPUTING PERSISTENCE DIAGRAM BUNDLES ABIGAIL HICKOK Abstract. Persistence diagram PD bundles a generalization of vineyards were intro-

2025-04-27 0 0 1004.21KB 21 页 10玖币

侵权投诉

COMPUTING PERSISTENCE DIAGRAM BUNDLES

ABIGAIL HICKOK

Abstract. Persistence diagram (PD) bundles, a generalization of vineyards, were intro-

duced as a way to study the persistent homology of a set of ﬁltrations parameterized by a

topological space B. In this paper, we present an algorithm for computing piecewise-linear

PD bundles, a wide class that includes many of the PD bundles that one may encounter

in practice. Full details are given for the case in which Bis a triangulated surface, and we

outline the generalization to higher dimensions and other cases.

1. Introduction

In persistent homology, one is given a ﬁltration (e.g., a ﬁltered complex), and one studies

how the homology changes as the ﬁltration parameter increases. Here, we consider the case

in which one is instead given a ﬁbered ﬁltration function, which is a set {fp:Kp→R}p∈B

of ﬁltration functions that is parameterized by some topological space B(the base space),

where Kpis a simplicial complex for each p∈B. At each p∈B, the sublevel sets of fp

form a ﬁltered complex. The associated persistence diagram (PD) bundle is the space of

persistence diagrams PD(fp) as they vary with p∈B.

PD bundles arise naturally in many circumstances. The prototypical PD bundle is a

vineyard, introduced in [3], which is the case where Bis an interval in R. For example, given

a time-varying point cloud, one obtains a vineyard by constructing a ﬁltration (such as the

Vietoris–Rips ﬁltration) at each time. Figure 1 shows an illustration of a vineyard, visualized

as a continuously-varying “stack of PDs”. More generally, however, one might have a set

{X(p)}p∈Bof point clouds parameterized by an arbitrary parameter space B. One obtains

a PD bundle by constructing a ﬁltration for the point cloud at each p∈B. For example,

biological aggregation models (e.g., the D’Orsogna model [2]) produce time-varying point

clouds whose coordinates also depend on various real-valued system parameters µ1, . . . , µk.

The parameter space Bin this example is a subset of Rk+1. For each (t, µ1, . . . , µk)∈B,

there is a point cloud from which one can construct a ﬁltration. Another special case is the

persistent homology transform (B=Sd), which is used in the ﬁeld of shape analysis [15].

Other concrete examples of PD bundles are given in [7].

1.1. Contributions. I generalize Cohen-Steiner et. al’s algorithm for computing vineyards

[3] to an algorithm for eﬃciently computing PD bundles. I restrict to the case in which the

PD bundle is piecewise linear. This means that Bis a simplicial complex, Kp≡ K for all

p∈B, and for every simplex σ∈ K, the function fσ(p) := fp(σ) is linear in pon every

simplex of B. The restriction to piecewise-linear PD bundles allows us to take advantage of

methods in computational geometry, such as the Bentley–Ottman planesweep algorithm [4]

for ﬁnding intersections of lines in a plane and algorithms for solving the point-location

problem in a line arrangement [13]. An analogous piecewise-linear restriction was helpful for

computing vineyards in [3].

Date: September 21, 2023.

arXiv:2210.06424v2 [math.AT] 19 Sep 2023

2 ABIGAIL HICKOK

Figure 1. An illustration of a vineyard, which consists of a persistence di-

agram for each time t. (This ﬁgure is a slightly modiﬁed version of a ﬁgure

that appeared originally in [9], which is available under a Creative Commons

license.)

The idea of the algorithm is to subdivide the base space Binto polyhedrons and compute

a PD “template” for each polyhedron. The subdivision is given by Proposition 2.7 ( [7]).

For any p∈B, the persistence diagram PD(fp) can then be computed in O(N) time from

the PD template for the polyhedron that contains p, where Nis the number of simplices in

K. By contrast, computing PD(fp) from scratch takes O(N3) time in the worst case.

The piecewise-linear restriction is reasonable for most applications. For example, suppose

that we have a point cloud X(t, µ) whose coordinates depend on time tand a parameter

µ∈R. If the data set arises from either real-world data collection or through numerical

simulation, then we likely only know the coordinates of the point cloud X(t, µ) at a discrete

set {ti}of time steps and a discrete set {µj}of system-parameter values. For every (ti, µj),

there is the ﬁltration function f(ti,µj):K → Rassociated with the Vietoris–Rips ﬁltration (or

any other ﬁltration) of X(ti, µj). For the Vietoris–Rips ﬁltration, Kis the simplicial complex

that contains a simplex for every subset of points in the point cloud. To obtain a ﬁbered

ﬁltration function, we deﬁne Bto be a triangulation of [min ti,max ti]×[min µj,max µj]

whose vertices are {(ti, µj)}ij . We can extend {f(ti,µj)}ij to a ﬁbered ﬁltration function

with base space Bby deﬁning the ﬁltration values of a simplex σvia linear interpolation of

{f(ti,µj)(σ)}ij . By construction, the resulting PD bundle is piecewise linear.

Full details are only given for the case in which dim(B) is a triangulated surface, but

the generalization to higher dimensions is discussed in Section 3.2. When the base space

Bis a triangulated surface, it is already an improvement over a vineyard because it allows

three parameters in total: a ﬁltration parameter as well as two parameters that locally

parameterize B.

1.2. Related Work. PD bundles were introduced in [7] as a generalization of vineyards [3].

The algorithm that I present in this paper for computing PD bundles is a broad generalization

of the algorithm in [3]. The algorithm in this paper is also related to the Rivet algorithm

for computing ﬁbered barcodes of 2D multiparameter persistence modules [8].

COMPUTING PERSISTENCE DIAGRAM BUNDLES 3

1.3. Organization. The paper proceeds as follows. I review the relevant background on

persistent homology, vineyards, and PD bundles in Section 2. I present my algorithm for

computing piecewise-linear PD bundles in Section 3. Finally, I conclude and discuss possible

directions for future research in Section 4.

2. Background

We begin by reviewing persistent homology, vineyards, and PD bundles; for more details

on persistent homology, see [5,12], for more on vineyards, see [3], and for an introduction to

PD bundles, see [7].

2.1. Persistent homology. Let Kbe a simplicial complex. A ﬁltration function f:K → R

is a real-valued function on Kthat is monotonic. That is, f(τ)≤f(σ) if τis a face of σ.

Monotonicity guarantees that the r-sublevel sets Kr:= {σ∈ K | f(σ)≤r)}are simplicial

complexes.

In persistent homology, we study how the homology of Krchanges as rincreases. Let

{ri}k

i=1 be the image of f, ordered such that ri< ri+1. These are the critical values at

which Krchanges; for r∈[ri, ri+1), we have Kr=Kri. For every i≤j, the inclusion

ιi,j :Kri→ Krjinduces a map ιi,j

∗:H∗(Kri,F)→H∗(Krj,F) on homology, where Fis a

ﬁeld. For the remainder of this paper, we compute homology over the ﬁeld F=Z/2Z. The

qth-persistent homology (PH) is the pair

{Hq(Kri,F)}1≤i≤k,{ιi,j

∗}1≤i≤j≤k.

A homology class is born at riif it is not in the image of ιi,i−1

∗. The homology class dies at

rj> riif jis the minimum index such that ιi,j

∗maps the homology class to zero. (Such a

jmay not exist; in that case, the homology class never dies.) The Fundamental Theorem

of Persistent Homology yields compatible choices of bases for the vector spaces Hq(Kri,F).

The generators in our deﬁnition of a persistence diagram, below, are the basis elements in

the decomposition given by the Fundamental Theorem of Persistent Homology.

Persistent homology is often visualized as a persistence diagram (PD). The qth persistence

diagram P Dq(f) is a multiset of points in the extended plane R2that summarizes the qth

persistent homology. It contains the points on the diagonal with inﬁnite multiplicity (for

technical reasons) and one point for every generator. If a generator is born at band dies at d,

then the coordinates of the corresponding point in the PD are (b, d), and if the generator is

born at band never dies, then the coordinates of the point are (b, ∞). Note that oﬀ-diagonal

points in a PD may also appear with multiplicity.

One of the standard methods for computing PH is the algorithm introduced in [6], which

we review here. Let f:K → Rbe a ﬁltration function, and let σ1, . . . , σNbe the simplices

of K, indexed such that i<jif σiis a proper face of σj. The algorithm requires a choice of

compatible simplex indexing idx : K → {1, . . . , N}, where Nis the number of simplices in K.

Deﬁnition 2.1. Asimplex indexing is a bijection idx : K → {1, . . . , N}.

Deﬁnition 2.2. Acompatible simplex indexing is a simplex indexing idx : K → {1, . . . , N}

such that idx(σi)<idx(σj) if f(σi)< f(σj) or σiis a proper face of σj.

A compatible simplex indexing exists because monotonicity ensures that f(σi)≤f(σj) if σi

is a face of σj. Because there may not be a unique compatible simplex indexing, we deﬁne

the simplex indexing induced by fas follows.

4 ABIGAIL HICKOK

Deﬁnition 2.3. The simplex indexing induced by fis the unique compatible simplex in-

dexing idxf:K → {1, . . . , N}such that idxf(σi)<idxf(σj) if either f(σi)< f(σj) or if

f(σi) = f(σj) and i<j.

The function idxfis a compatible simplex indexing because the sequence σ1, . . . , σNof sim-

plices is ordered such that i<jif σiis a proper face of σj.

Let Dbe the boundary matrix compatible with the simplex indexing idxf. That is, let D

be the matrix whose (i, j)th entry is

Dij =(1,idx−1

f(i) is an (m−1)-dimensional face of the m-dimensional simplex idx−1

f(j)

0,otherwise.

We decompose the boundary matrix Dinto a matrix product D=RU such that Uis upper

triangular and Ris a binary matrix that is “reduced”. A binary matrix Ris reduced if

lowR(j)̸= lowR(j′) whenever j̸=j′are the indices of nonzero columns in R. The quantity

lowR(j), which is called the pairing function, is the row index of the last 1 in column jif

column jis nonzero and undeﬁned if column jis the zero vector. An RU decomposition can

be computed in O(N3) time [5, 6].

Cohen-Steiner et al. [3] showed that the pairing function lowR(j) depends only on the

boundary matrix Dand not on the particular reduced binary matrix Rin the decomposition

D=RU. A pair (idx−1

f(i),idx−1

f(j)) of simplices with i= lowR(j) represents a persistent

homology generator. The birth simplex idx−1

f(i) creates the homology class and the death

simplex idx−1

f(j) destroys the homology class. The two simplices in a pair have consecutive

dimensions; that is, if dim(idx−1(i)) = q, then dim(idx−1(j)) = q+ 1. If dim(idx−1

f(i)) = q

and dim(idx−1

f(j)) = q+ 1, then a point with coordinates (f(idx−1

f(i)), f(idx−1

f(j))) is added

to the qth persistence diagram. We refer to f(idx−1

f(i)) as its birth and to f(idx−1

f(j)) as its

death. Some simplices are not paired. If i̸= lowR(j) for all j, then the simplex idx−1

f(i) is a

birth simplex for a homology class that never dies. Its birth is f(idx−1

f(i)) and its death is

∞. If dim(idx−1

f(i)) = q, then a point with coordinates (f(idx−1

f(i)),∞) is added to the qth

persistence diagram.

2.2. Vineyards. Let Kbe a simplicial complex. A 1-parameter ﬁltration function on Kis

a function f:K × I→R, where I= [t0, t1] is an interval in R, such that f(·, t) is a ﬁltration

function on Kfor all t∈I. For each t∈I, the r-sublevel sets Kt

r={σ∈ K | f(σ, t)≤r}

are a ﬁltration of K. The set {{Kt

r}r∈R}t∈Iis a set of ﬁltrations parameterized by t∈I. For

each t∈I, one can compute the persistence diagram P D(f(·, t)). The associated vineyard

is the 1-parameter set {P D(f(·, t))}t∈Iof persistence diagrams. We visualize the vineyard in

R2×Ias a continuous stack of PDs (see Figure 1). The points in the PDs trace out curves

with time; these curves are the vines.

An algorithm for computing vineyards is given by [3], and we review it here. Let f:

K × I→Rbe a 1-parameter ﬁltration function, and let σ1, . . . , σNbe the simplices of K,

indexed such that i < j if σiis a proper face of σj. As in Section 2.1, we ﬁx a compatible

simplex indexing idxf:K × I→ {1, . . . , N}such that idxf(σi, t)<idxf(σj, t) if we have

either f(σi, t)< f(σj, t) or we have f(σi, t) = f(σj, t) and i<j. The simplex indexing can

only change at times t∗at which f(σ, t∗) = f(τ, t∗) for some σ, τ ∈ K. At t∗, the indices

of σand τmay change. (If σ,τare the unique pair of simplices whose indices change

at t∗, then σand τare transposed in the simplex indexing and σand τhave consecutive

COMPUTING PERSISTENCE DIAGRAM BUNDLES 5

indices in the indexing. Otherwise, there is a sequence of such transpositions.) Let D(t)

denote the boundary matrix compatible with the indexing at time tand let lowR(·, t) denote

the corresponding pairing function. One computes D(t0) at the initial time t0and an RU

decomposition D(t0) = R(t0)U(t0). The initial pairing function lowR(·, t0) is read oﬀ from

the initial RU decomposition. Then we sweep through the intersections t∗(from left to right)

at which the simplex indexing changes. At each t∗, we update the simplex indexing, RU

decomposition, and pairing function. This updating procedure yields the birth and death

simplices for the ﬁltration function f(·, t∗), which one can use to obtain the new persistence

diagram.

The procedure above is an eﬃcient way of computing the diagrams PD(f(·, t)) for all

t∈[t0, t1]. At worst, updating R(t∗) requires adding one column to another and adding

one row to another—similarly for U(t∗). The addition of columns and rows is an O(N)

operation, although in experiments, the authors of [3] found that updating R(t∗) and U(t∗)

can be done in approximately constant time if one uses the sparse matrix representations

that are given in [3]. If there is a single transposition of simplices at t∗, then at most two

(birth, death) simplex pairs are updated, and these updates occur in O(1) time.

A special type of vineyard is a piecewise-linear vineyard. If we are only given f(σ, ti)

at discrete time steps ti, then for all iwe extend f(σ, t) to t∈[ti, ti+1] by linear inter-

polation. In this case, one can compute the transposition times t∗by using the Bentley–

Ottman planesweep algorithm [4]. This is because computing when (if) two simplices σ, τ

get transposed in [ti, ti+1] is equivalent to ﬁnding the intersection (if it exists) between the

line segments

y=f(σ, ti+1)−f(σ, ti)

ti+1 −ti

(t−ti) + f(σ, ti),

y=f(τ, ti+1)−f(τ, ti)

ti+1 −ti

(t−ti) + f(τ, ti).

2.3. PD bundles. PD bundles were introduced in [7] as a generalization of vineyards in

which a set of ﬁltrations is parameterized by an arbitrary topological space B. A vineyard

is the special case in which Bis an interval in R.

Deﬁnition 2.4. Aﬁbered ﬁltration function is a set {fp:Kp→R}p∈Bof ﬁltration functions

parameterized by a topological space B(the base space). When Kp≡ K for all p∈B, we

deﬁne f(σ, p) := fp(σ) for all simplices σ∈ K and p∈B.

Deﬁnition 2.5. Let {fp:Kp→R}p∈Bbe a ﬁbered ﬁltration function. The topological

space Bis the base space. The space E:= {(p, z)|z∈P Dq(fp), p ∈B}is the qth total

space. We give Ethe subspace topology inherited from the inclusion E →B×R2. The

associated qth PD bundle is the triple (E, B, π), where πis the projection from Eto B.

In [3], it was computationally easier to work with a piecewise-linear vineyard, which is a

vineyard for a ﬁbered ﬁltration function of the form f:K × [t0, t1]→Rsuch that f(σ, ·)

is piecewise linear for all σ∈ K. (See the discussion at the end of Section 2.2.) Below, we

deﬁne an analog of piecewise-linear vineyards.

Deﬁnition 2.6 (Piecewise-linear PD bundles).Let {fp:Kp→R}p∈Bbe a ﬁbered ﬁltration

function in which Kp≡ K. As in Deﬁnition 2.4, we deﬁne f(σ, p) := fp(σ) for all σ∈ K and

p∈B. If Bis a simplicial complex and f(σ, ·) is linear on each simplex of Bfor all simplices

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

COMPUTINGPERSISTENCEDIAGRAMBUNDLESABIGAILHICKOKAbstract.Persistencediagram(PD)bundles,ageneralizationofvineyards,wereintro-ducedasawaytostudythepersistenthomologyofasetoffiltrationsparameterizedbyatopologicalspaceB.Inthispaper,wepresentanalgorithmforcomputingpiecewise-linearPDbundles,awideclassthati...

展开>> 收起<<

COMPUTING PERSISTENCE DIAGRAM BUNDLES ABIGAIL HICKOK Abstract. Persistence diagram PD bundles a generalization of vineyards were intro-.pdf

共21页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

COMPUTING PERSISTENCE DIAGRAM BUNDLES ABIGAIL HICKOK Abstract. Persistence diagram PD bundles a generalization of vineyards were intro-

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: