Tracking the Persistence of Harmonic Chains: Barcode and Stability

Hou, Tao; Parsa, Salman; Wang, Bei

doi:10.4230/LIPIcs.SoCG.2025.58

Tracking the Persistence of Harmonic Chains: Barcode and Stability

Tao Hou

University of Oregon, Eugene, OR, USA Salman Parsa

DePaul University, Chicago, IL, USA Bei Wang

University of Utah, Salt Lake City, UT, USA

Abstract

The persistence barcode is a topological descriptor of data that plays a fundamental role in topological data analysis. Given a filtration of data, the persistence barcode tracks the evolution of its homology groups. In this paper, we introduce a new type of barcode, called the harmonic chain barcode, which tracks the evolution of harmonic chains. In addition, we show that the harmonic chain barcode is stable. Given a filtration of a simplicial complex of size $m$ , we present an algorithm to compute its harmonic chain barcode in $O(m^{3})$ time. Consequently, the harmonic chain barcode can enrich the family of topological descriptors in applications where a persistence barcode is applicable, such as feature vectorization and machine learning.

Keywords and phrases:

Persistent homology, harmonic chains, topological data analysis

Funding:

Tao Hou: Supported by NSF CCF 2439255.

Salman Parsa: Supported by DOE DE-SC0021015.

Bei Wang: Supported by DOE DE-SC0021015, NSF IIS-2145499 and NSF DMS-2301361.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Design and analysis of algorithms ; Mathematics of computing

\rightarrow

Topology

Editors:

Oswin Aichholzer and Haitao Wang

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

There are two primary tasks in topological data analysis (TDA) [27, 30, 53]: reconstruction and inference. In a typical TDA pipeline, the data is given as a point cloud in ${\mathbb{R}}^{N}$ . A “geometric shape” $K$ in ${\mathbb{R}}^{N}$ is reconstructed from the point cloud, usually as a simplicial complex, and $K$ is taken to represent the (unknown) space $X$ from which the data is sampled. $X$ is then studied using $K$ as a surrogate for properties that are invariant under invertible mappings (technically, homeomorphisms). The deduced “topological shape” is not specific to the complex $K$ or the space $X$ , but is a feature of the homeomorphism type of $K$ or $X$ . For example, a standard round circle has the same topological shape as any closed loop such as a knot in the Euclidean space. Although topological properties of $X$ alone are not sufficient to reconstruct $X$ exactly, they are among a few global features of $X$ that can be inferred from the data sampled from $X$ .

An (ordinary) persistence barcode [10, 31] (or equivalently, a persistence diagram [14, 19, 29]) captures the evolution of homological features in a filtration constructed from a simplicial complex $K$ . It consists of a multi-set of intervals in the extended real line, where the start and end points of an interval (i.e., a bar) are the birth and death times of a homological feature in the filtration. Equivalently, a persistence diagram is a multi-set of points in the extended plane, where a point in the persistence diagram encodes the birth and death time of a homological feature.

A main drawback of ordinary persistent homology is that it does not provide canonical choices of geometric representatives for each bar in the barcode. Specifically, there are two levels of choices in assigning representatives for bars in a persistence barcode: first, we choose a basis for persistent homology in a consistent way across the filtration; second, we choose a cycle representative inside each homology class in the basis. Both levels of choices involve choosing among significantly distinct geometric features of data to represent the same bar in the barcode. Since such choices are not canonical, it can be challenging to interpret their underlying geometric meaning. In addition, while existing works [7, 25, 51] compute optimal representatives for ordinary persistence, the optimality would rely on a choice of weights for the simplices and on the optimality criterion, leading to different shapes. Moreover, computing the optimal representatives is NP-hard in many interesting situations [17, 11, 12, 5, 32, 25].

As our first contribution, we introduce a new type of barcode called harmonic chain barcode. This barcode is obtained by tracking the birth and death of harmonic chains in an increasing filtration. Since there is always a unique harmonic chain in a homology class, the harmonic representatives in our harmonic chain barcode immediately remove the second level of choices in a natural way. The main idea is to take the harmonic chain groups along an increasing filtration, and to observe that the groups grow or shrink due to the birth and death of harmonic chains, resulting in a zigzag module with inclusion maps. Like any zigzag module [8], the module of harmonic chain groups decomposes into interval modules, which then form the harmonic chain barcode. Moreover, since the maps in this zigzag module are essentially inclusions, each representative for a bar in our harmonic chain barcode consists of a single harmonic chain which is alive over the entire bar. We emphasize that our harmonic chain barcode is distinct from the ordinary persistence barcode; see for example Figs. 1 and 2.

The ordinary persistence barcode is shown to be stable [19], which is crucial for applications. The stability means that small changes in the data imply only small changes in the barcode. For our second contribution, we show that our harmonic chain barcode is also stable in the same sense as the stability of persistence barcode [19].

Finally, we present an algorithm for computing the harmonic chain barcode in $O(m^{3})$ time for a filtration of size $m$ , matching the complexity of practical algorithms for ordinary persistence.

The interpretation of homological features is crucial for applications such as extracting hierarchical structures of amorphous solids [36] and quantifying the growing branching architectures of plants [42]. Such an interpretation is closely related to the existence of canonical chain representatives for a barcode. In our harmonic chain barcode, using orthogonality, each bar enjoys a canonical choice of representative (within a homology class) which lives exactly at the time-interval of the bar. This arguably promises a more interpretable data feature. Therefore, we expect our harmonic chain barcodes to enrich the family of topological descriptors in applications where ordinary persistence barcodes are used, such as feature vectorization and machine learning. Note that just from the fact that our barcode is different from the ordinary persistence one cannot argue in favor or against our suggested barcode. Such a comparison is only meaningful in a specific domain of application and when performed using experimental evaluations. We refer to [35] for an interesting pipeline of data analysis using extra properties of harmonic chains. [35] also contains a method of propagating the information from harmonic chains back to the original data points, which we find also relevant to our harmonic representatives.

2 Related work

Harmonic chains were first studied in the context of functions on graphs, where they were identified as the kernel of the Laplacian operator on graphs [40]. The graph Laplacian and its kernel are important tools in studying graph properties, see [48, 50] for surveys. Eckmann [28] introduced the higher-order Laplacian for simplicial complexes, and proved the isomorphism of harmonic chains and homology. The work [33] studied the stability of higher-order Laplacians. Horak and Jost [37] defined a weighted Laplacian for simplicial complexes. Already their theoretical results on Laplacian [37] anticipated the possibility of applications, as the harmonic chains are thought to contain important geometric information. They are eigenvectors of the 0 eigenvalue of the Laplace operator on simplicial complexes and the spectrum of the Laplace operator has significant geometric information, see e.g. [38]. This has been validated by recent results that use curves of eigenvalues of Laplacians in a filtration in data analysis [18, 52]. The Laplacian was applied to improve the mapper algorithm [49], and for coarsening triangular meshes [39]. The persistent Laplacian [47] and its stability [44] is an active research area. Due to the close relation of harmonic chains and Laplacians, harmonic chains could find applications in areas that Laplacians have been used. Computing reasonable representative cycles for persistent homology is also an active area of research. Here, usually an optimality criterion is imposed on cycles in a homology class to obtain a unique representative. For a single homology class, a number of works [16, 23, 25, 51, 7, 13, 17, 23, 41] consider different criteria for optimality of cycles. Hardness of computing optimal representatives has been studied by [17, 11, 12, 13, 5, 32, 25]. For persistent homology, the authors of [25] studied the hardness of choosing optimal cycles for persistence bars. Furthermore, the study in [20] uses harmonic cycles in a persistent homology setting to compute the persistence barcode. Lieutier [43] studied the harmonic chains in persistent homology classes, called persistent harmonic forms.

Relation to the work of Basu and Cox.

The most relevant work to ours is the inspiring work of Basu and Cox [2]. Basu and Cox had a similar goal as ours, namely, to associate geometric information to each bar in order to obtain a more interpretable data feature. To that end, they introduced the notion of harmonic persistent barcode, by associating a subspace of harmonic chains to each bar in the ordinary persistence barcode. When the multiplicity of the bar is 1, the subspace is 1-dimensional. This is the space of harmonic chains that are born at $s$ and die entering $t$ . In general, this is a quotient subspace of harmonic chains at time $s$ . Using orthogonality, they can represent this subquotient as a subspace of the harmonic cycles at time $s$ . As a result, they successfully assign a canonical harmonic cycle to a bar in the ordinary persistence diagram. We note that, in general, a bar in the persistence barcode cannot be represented using a single harmonic chain that remains harmonic during the lifetime of the bar. The harmonic cycle associated to a bar using the Basu-Cox approach is the initial harmonic representative of the bar, that is, the harmonic cycle that represents the bar at its birth. Basu and Cox also used the terminal harmonic cycle in some of their arguments, thus showing that the choice is not entirely canonical. However, Basu and Cox proved significant properties of the initial cycles in terms of what they call relative essential content. The novelty of our result is that, in contrast to [2], we define a new barcode distinct from the ordinary persistence barcode, in which each bar has a harmonic cycle associated with it that is harmonic during the lifetime of the bar. Basu and Cox also proved stability for their harmonic persistent barcode, by considering subspaces as points of a Grassmannian manifold and measuring distances in the Grassmannian. Such a distance quantifies the angles between subspaces, whereas our notions of stability are stronger in the sense that they use the classical bottleneck distance analogous to the ordinary persistence homology. The authors of [34] studied a method that permits the construction of stable persistence diagrams that are equipped with a canonical choice of representative cycles for filtrations over arbitrary finite posets. If the underlying poset is a finite subset of the real line, using persistent Laplacians, they obtained harmonic cycles connected (through a certain isomorphism) to those identified by Basu and Cox.

3 Background

In this section, we review the notion of harmonic chains and persistent homology. Homology and cohomology are defined with real coefficients $\mathbb{R}$ (instead of $\mathbb{Z}_{2}$ ). Let $K$ be a simplicial complex and $p$ the homology dimension (or equivalently, homology degree). $C_{p}(K)$ , $Z_{p}(K)$ , and $H_{p}(K)$ denote the $p$ -th chain group, cycle group, and homology group of $K$ , whereas $C^{p}(K)$ , $Z^{p}(K)$ , and $H^{p}(K)$ denote the $p$ -th cochain group, cocycle group, and cohomology group of $K$ , respectively. Groups across all dimensions are denoted as $C_{*}(K)$ , $C^{*}(K)$ , etc. We use $\partial$ and $\delta$ to denote boundary and coboundary operators, respectively.

3.1 Harmonic cycles

Based on the standard notions of homology and cohomology with ${\mathbb{R}}$ coefficients, we identify chains and cochains via duality, i.e., $C_{p}(K)=C^{p}(K)={\mathbb{R}}^{n_{p}}$ , where $n_{p}$ is the number of $p$ -simplices. Therefore, we can talk about coboundaries of cycles in $Z_{p}(K)$ . We first introduce the notion of harmonic chains.

Definition 1.

The $p$ -th harmonic chain group of $K$ , denoted ${\mathbb{H}}_{p}(K)$ , is the group of $p$ -cycles that are also $p$ -cocylces. Equivalently, ${\mathbb{H}}_{p}(K):=Z_{p}(K)\cap Z^{p}(K)$ . Each element in ${\mathbb{H}}_{p}(K)$ is called a harmonic $p$ -chain. The harmonic chain group in all dimensions is the group ${\mathbb{H}}(K):=\bigoplus_{p}{\mathbb{H}}_{p}(K)$ .

We sometimes use harmonic cycles in place of harmonic chains to emphasize the fact that harmonic chains are cycles.

Lemma 2 ([28]).

${\mathbb{H}}_{p}(K)$ is isomorphic to $H_{p}(K)$ and $H^{p}(K)$ . Specifically, each homology and cohomology class has a unique harmonic cycle in it.

Harmonic cycles enjoy certain geometric properties. As an example, we mention the following Proposition 3; see [21, Proposition 3] for a proof. In other words, a harmonic cycle is the chain with the least squared-norm in a cohomology class.

Proposition 3 ([21]).

Let $\alpha\in C^{p}(K)$ be a cochain. There is a unique solution $\overline{\alpha}$ to the least-squares minimization problem $\operatorname*{arg\,min}_{\overline{\alpha}}\{||\overline{\alpha}||^{2}\mid% \exists\gamma\in C^{p-1}(K);\alpha=\overline{\alpha}+\delta\gamma\}.$ Moreover, $\overline{\alpha}$ is characterized by the relation $\partial{\overline{\alpha}}=0$ .

There is an alternative definition of harmonic cycles. Consider the natural inner product on $C_{p}(K)$ given by $\langle\sigma_{i},\sigma_{j}\rangle=\delta_{i,j}$ . The harmonic chain group can be defined as ${\mathbb{H}}_{p}(K)=Z_{p}(K)\cap B_{p}(K)^{\perp}$ . With this definition, the isomorphism of Lemma 2 is realized by a map that sends $z+B_{p}(K)$ to its projection to $B_{p}(K)^{\perp}$ . In addition, the harmonic cycles satisfy ${\mathbb{H}}_{p}(K)=\ker(\partial_{p})\cap\ker(\partial_{p+1}^{\perp}).$ For a short proof of the equivalence among the definitions of harmonic cycles above, see [2]. Importantly, our algorithm relies on the fact that harmonic cycles are cocycles whose boundaries are zero.

3.2 Ordinary persistence

Ordinary persistent homology takes a filtration of a simplicial complex $K$ as input. A continuous filtration $F$ assigns to each $r\in{\mathbb{R}}$ a subcomplex $K_{r}\subseteq K$ such that $K_{r}\subseteq K_{s}$ for $r\leq s$ . Since $K$ is finite, there are finitely many $t_{0},t_{1},\ldots,t_{m}\in{\mathbb{R}}$ where $K_{t_{i}}$ changes. We then abuse the notations slightly by letting $K_{i}:=K_{t_{i}}$ and have a discrete form of $F$ ,

F:\emptyset=K_{0}\hookrightarrow K_{1}\hookrightarrow\cdots\hookrightarrow K_{% m-1}\hookrightarrow K_{m}=K,

(1)

where each $K_{i}\hookrightarrow K_{i+1}$ is an inclusion. Unless stated otherwise, we assume that $F$ is simplex-wise, i.e., each two $K_{i}$ and $K_{i+1}$ differ by at most a single simplex. For simplicity of the exposition, complexes in $F$ sometimes are subscripted by real-valued “timestamps” of the form $K_{t_{i}}$ (e.g., in Sec. 6) or subscripted by integers of the form $K_{i}$ (e.g., in Sec. 5), which should not cause any confusions. Applying homology functor to Eq. 1, we obtain a sequence of homology groups and connecting linear maps (homomorphisms), forming a persistence module:

\mathcal{M}:H_{p}(K_{0})\to H_{p}(K_{1})\to\cdots\to H_{p}(K_{m-1})\to H_{p}(K% _{m}).

(2)

For $s\leq t$ , let $f^{s,t}_{p}:H_{p}(K_{s})\rightarrow H_{p}(K_{t})$ denote the map induced on the $p$ -th homology by inclusion. The image of the map, $f^{s,t}_{p}(H_{p}(K_{s}))\subseteq H_{p}(K_{t})$ , is called the $p$ -th $(s,t)$ -persistent homology group, denoted $H_{p}^{s,t}$ . The group $H_{p}^{s,t}$ consists of homology classes which exist in $K_{s}$ and survive until $K_{t}$ . The dimensions of these vector spaces are the persistent Betti numbers, denoted $\beta^{s,t}_{p}$ . An interval module, denoted $I=I[b,d)$ , is a persistence module of the form

0\rightarrow\cdots\rightarrow 0\rightarrow{\mathbb{R}}\rightarrow\cdots% \rightarrow{\mathbb{R}}\rightarrow 0\rightarrow\cdots\rightarrow 0.

In the above, ${\mathbb{R}}$ is generated by a homology class and the connecting homomorphisms map generator to generator. We have $I_{r}={\mathbb{R}}$ for $b\leq r<d$ and $I_{r}=0$ for other $r$ . Any persistence module can be decomposed into a collection of interval modules in a unique way [45]. The collection of $[b,d)$ for all interval modules is called the persistence barcode. When plotted as points in an extended plane, the result is the equivalent persistence diagram.

Stability of persistence diagram/barcode.

The stability of persistence diagrams (or barcodes) is a crucial property for applications. It says that small changes in data lead to small changes in the persistence diagrams. We only review the stability for sublevel-set filtrations here. Let $D$ and $D^{\prime}$ denote two persistence diagrams. Recall that a persistence diagram is a multi-set of points in the extended plane (each of which is a birth-death pair) which also contains all points on the diagonal. The bottleneck distance of $D,D^{\prime}$ is defined as

d_{B}(D,D^{\prime})=\text{inf}_{\gamma}\text{sup}_{p\in D}||p-\gamma(p)||_{% \infty},

where $\gamma$ ranges over all bijections between $D$ and $D^{\prime}$ and $||\cdot||_{\infty}$ is the largest absolute value of differences of the points’ coordinates.

A function $\tilde{f}:|K|\rightarrow{\mathbb{R}}$ is called simplex-wise linear if it is linear on each simplex. Let $K_{r}=\{\sigma\in K\mid\forall x\in|\sigma|,\tilde{f}(x)\leq r\}$ be the sublevel set complex at value $r\in{\mathbb{R}}.$ The complexes $K_{r}$ and the inclusions between them form a sublevel set filtration $\tilde{F}$ (which is not necessarily simplex-wise). We denote the persistence diagram of $\tilde{F}$ as ${\mathrm{Dgm}}(\tilde{f})$ . We refer to [19, 14] for proof of the following Theorem 4. See [19, 14] for the stability of ordinary persistence.

Theorem 4.

Let $\tilde{f},\tilde{g}:|K|\xrightarrow{}\mathbb{R}$ be simplex-wise linear functions. Then

d_{B}({\mathrm{Dgm}}(\tilde{f}),{\mathrm{Dgm}}(\tilde{g}))\leq||\tilde{f}-% \tilde{g}||_{\infty}.

3.3 Zigzag persistence

We provide a brief overview of zigzag persistence; see [8, 9] for details. A zigzag module

\mathcal{M}:V_{0}\xleftrightarrow{\;g_{0}\;}V_{1}\xleftrightarrow{\;g_{1}\;}% \cdots\xleftrightarrow{\;g_{k-1}\;}V_{k}

is a sequence of vector spaces connected by linear maps that could be forward or backward, i.e., each $g_{i}$ could be $g_{i}:V_{i}\to V_{i+1}$ or $g_{i}:V_{i}\leftarrow V_{i+1}$ . The module $\mathcal{M}$ decomposes into a direct sum of interval modules $I[b,d]$ of the form

0\longleftrightarrow\cdots\longleftrightarrow 0\longleftrightarrow{\mathbb{R}}% \longleftrightarrow\cdots\longleftrightarrow{\mathbb{R}}\longleftrightarrow 0% \cdots\longleftrightarrow 0

with 1-dimensional vector spaces in the range $[b,d]$ . The multi-set of intervals in the decomposition defines the barcode of $\mathcal{M}$ , denoted as $\mathsf{B}(\mathcal{M})$ .

Conventions.

In this paper, we may omit the subscript/dimension of a homology group if there is no danger of ambiguity. Moreover, we use the terms persistence barcode and persistence diagram interchangeably.

4 Harmonic chain barcodes and representatives

As reviewed in Sec. 3.2, by directly taking the homology functor, an increasing filtration of simplicial complexes leads to an ordinary persistence module consisting of homology groups [15, 27]. These homology groups are connected by forward maps of the form $H(K_{i})\xrightarrow{}H(K_{i+1})$ . The ordinary persistence module then decomposes into interval modules, which define the ordinary persistence barcode. In this section, we show that the harmonic chain groups of all the complexes in a filtration constitute an abstract zigzag persistence module (see Sec. 3.3). The main idea is that we take the harmonic chain groups along the filtration, where the groups could grow or shrink, resulting in a zigzag module. Moreover, the maps in this zigzag module are inclusions. Like any zigzag module [8], the module of harmonic chain groups decomposes into interval modules. These intervals form the harmonic chain barcode, the main object of interest in this paper.

Throughout the section, consider a simplex-wise filtration

F:\emptyset=K_{0}\xhookrightarrow{\;\sigma_{0}\;}K_{1}\xhookrightarrow{\;% \sigma_{1}\;}\cdots\xhookrightarrow{\;\sigma_{m-1}\;}K_{m}=K,

where each $K_{i+1}$ differs from $K_{i}$ by the addition of a simplex $\sigma_{i}$ . Recall that $K_{i}:=K_{t_{i}}$ for $t_{i}\in\mathbb{R}$ where $K_{t_{i}}$ is a complex from a continuous filtration indexed over $\mathbb{R}$ ; see Sec. 3.2.

Proposition 5.

For each inclusion $K_{i}\xhookrightarrow{\;\sigma_{i}\;}K_{i+1}$ in $F$ :

\dim({\mathbb{H}}(K_{i+1}))=\dim({\mathbb{H}}(K_{i}))\pm 1.

Proof.

This follows from Lemma 2 and some well-known facts in persistence (see [27, 29]). $\hfill\blacktriangleleft$

Definition 6.

A simplex $\sigma_{i}$ inserted in $F$ is called positive if $\dim({\mathbb{H}}(K_{i+1}))=\dim({\mathbb{H}}(K_{i}))+1,$ and negative if $\dim({\mathbb{H}}(K_{i+1}))=\dim({\mathbb{H}}(K_{i}))-1$ .

We describe how we connect the harmonic chain groups of complexes in $F$ by inclusions. For each $K_{i}$ and each chain $c=\sum_{j=0}^{i-1}\alpha_{j}\sigma_{j}$ in $C_{p}(K_{i})$ , we identify $c$ as a chain $c=\sum_{j=0}^{m-1}\alpha_{j}\sigma_{j}$ in $C_{p}(K)$ , where $\alpha_{j}=0$ for $j\geq i$ . This makes both $C_{p}(K_{i})$ and $C_{p}(K_{i+1})$ a subspace of $C_{p}(K)$ . We then have the following inclusion:

Z_{p}(K_{i})\hookrightarrow Z_{p}(K_{i+1}).

(3)

Recall that ${\mathbb{H}}_{p}(K_{i}):=Z_{p}(K_{i})\cap Z^{p}(K_{i})$ , which means that ${\mathbb{H}}_{p}(K_{i})\subseteq Z_{p}(K_{i})\subseteq C_{p}(K)$ . Hence, we also identify each harmonic cycle in ${\mathbb{H}}_{p}(K_{i})$ as a chain in $C_{p}(K)$ . We then observe in Theorem 7 a similar inclusion as in Eq. 3 between any harmonic chain groups ${\mathbb{H}}_{p}(K_{i})$ and ${\mathbb{H}}_{p}(K_{i+1})$ , with a possible flip on the direction.

Theorem 7.

For each arrow $K_{i}\xhookrightarrow{\;\sigma_{i}\;}K_{i+1}$ in $F$ , where $\sigma_{i}$ is a $p$ -simplex:

$\blacksquare$

There is an inclusion ${\mathbb{H}}_{p}(K_{i})\hookrightarrow{\mathbb{H}}_{p}(K_{i+1})$ if $\sigma_{i}$ is positive;
$\blacksquare$

And there is an inclusion ${\mathbb{H}}_{p-1}(K_{i})\hookleftarrow{\mathbb{H}}_{p-1}(K_{i+1})$ if $\sigma_{i}$ is negative.

In addition, in each case the harmonic chain groups in other dimensions remain unchanged, i.e., ${\mathbb{H}}_{q}(K_{i})={\mathbb{H}}_{q}(K_{i+1})$ for any other $q\notin\{p,p-1\}$ .

Proof.

The only harmonic chain groups that might change from $K_{i}$ to $K_{i+1}$ are those in dimension $p$ because cycle and cocycle groups in other dimensions do not change.

First consider Case I that $\sigma_{i}$ is positive. Let $\iota:K_{i}\hookrightarrow K_{i+1}$ be the inclusion map. As noted above, we identify any $c\in C_{*}(K_{i})=C^{*}(K_{i})$ with $\iota_{\sharp}(c)\in C_{*}(K_{i+1})=C^{*}(K_{i+1})$ .

Case I.1: ${\mathbb{H}}_{p}(K_{i})\subseteq{\mathbb{H}}_{p}(K_{i+1})$ .: Take $z\in{\mathbb{H}}_{p}(K_{i})$ . Obviously, $\iota_{\sharp}(z)$ is a cycle in $K_{i+1}$ . For any $c\in C_{p+1}(K_{i+1})$ , $\delta(\iota_{\sharp}(z))(c)=\iota_{\sharp}(z)(\partial c)$ . Since $C_{p+1}(K_{i})=C_{p+1}(K_{i+1})$ , $c$ and hence $\partial c$ exist in $K_{i}$ , meaning that $\iota_{\sharp}(z)(\partial c)=z(\partial c)=(\delta z)(c)=0$ . It follows that $\iota_{\sharp}(z)$ is a cocycle in $K_{i+1}$ . Therefore, ${\mathbb{H}}_{p}(K_{i})\subseteq{\mathbb{H}}_{p}(K_{i+1})$ .
Case I.2: ${\mathbb{H}}_{p-1}(K_{i})={\mathbb{H}}_{p-1}(K_{i+1})$ .: Take $z\in{\mathbb{H}}_{p-1}(K_{i+1})$ . Since $\sigma_{i}$ is a positive $p$ -simplex, we have $Z_{p-1}(K_{i+1})=Z_{p-1}(K_{i})$ and $B_{p-1}(K_{i})=B_{p-1}(K_{i+1})$ . So $z\in Z_{p-1}(K_{i})$ and we consider $z$ as a cochain in $K_{i}$ . Then, for any $c\in C_{p}(K_{i})$ , $\delta(z)(c)=z(\partial c)=0$ , with the last equality due to $\partial c\in B_{p-1}(K_{i})=B_{p-1}(K_{i+1})$ . Therefore, ${\mathbb{H}}_{p}(K_{i+1})\subseteq{\mathbb{H}}_{p}(K_{i})$ . Take $z\in{\mathbb{H}}_{p-1}(K_{i})$ . For any $c\in C_{p}(K_{i+1})$ , $\delta(\iota_{\sharp}z)(c)=(\iota_{\sharp}z)(\partial c)=0$ , with the last equality due to $\partial c\in B_{p-1}(K_{i+1})=B_{p-1}(K_{i})$ . Therefore, ${\mathbb{H}}_{p-1}(K_{i})={\mathbb{H}}_{p-1}(K_{i+1})$ .

Now consider Case II that $\sigma_{i}$ is negative.

Case II.1: ${\mathbb{H}}_{p}(K_{i+1})={\mathbb{H}}_{p}(K_{i})$ .: Since $\sigma_{i}$ is negative, $Z_{p}(K_{i+1})=Z_{p}(K_{i})$ and $B_{p}(K_{i+1})=B_{p}(K_{i})$ . The verification for this case is then the same as the verification for Case I.2 with a shift on the homology degree.
Case II.2: ${\mathbb{H}}_{p-1}(K_{i+1})\subseteq{\mathbb{H}}_{p-1}(K_{i})$ .: Take $z\in{\mathbb{H}}_{p-1}(K_{i+1})$ . We have $Z_{p-1}(K_{i+1})=Z_{p-1}(K_{i})$ . Therefore, $z\in Z_{p-1}(K_{i})$ and we consider $z$ as a cochain in $K_{i}$ . For any $c\in C_{p}(K_{i})$ , $\delta(z)(c)=z(\partial c)=0$ , with the last equality due to $\partial c\in B_{p-1}(K_{i})\subseteq B_{p-1}(K_{i+1})$ . Therefore, ${\mathbb{H}}_{p-1}(K_{i+1})\subseteq{\mathbb{H}}_{p-1}(K_{i})$ .

$\hfill\blacktriangleleft$

Definition 8 (Harmonic chain barcode).

Consider the following harmonic zigzag module

{\mathbb{H}}(F):{\mathbb{H}}(K_{0})\leftrightarrow{\mathbb{H}}(K_{1})% \leftrightarrow\cdots\leftrightarrow{\mathbb{H}}(K_{m}),

(4)

where the harmonic chain groups are connected by either forward inclusions (e.g., ${\mathbb{H}}(K_{i})\to{\mathbb{H}}(K_{i+1})$ ) or backward inclusions (e.g., ${\mathbb{H}}(K_{i})\leftarrow{\mathbb{H}}(K_{i+1})$ ); see Theorem 7. Define the harmonic chain barcode $\mathsf{B}^{\mathbb{H}}(F)$ of $F$ as the barcode of the zigzag module ${\mathbb{H}}(F)$ , that is,

\mathsf{B}^{\mathbb{H}}(F):=\mathsf{B}({\mathbb{H}}(F)).

In general, the harmonic chain barcode is different from the ordinary persistence barcode for a filtration; see Fig. 2. In this paper, we also consider the zigzag module ${\mathbb{H}}_{p}(F)$ derived by taking ${\mathbb{H}}_{p}(K_{i})$ on each $K_{i}$ in $F$ . While the $p$ -th harmonic chain groups in ${\mathbb{H}}_{p}(F)$ are still connected by forward or backward inclusions, we may have ${\mathbb{H}}_{p}(K_{i})={\mathbb{H}}_{p}(K_{i+1})$ for two consecutive groups in ${\mathbb{H}}_{p}(F)$ . We therefore define the $p$ -th harmonic chain barcode $\mathsf{B}^{\mathbb{H}}_{p}(F)$ of $F$ as the barcode of ${\mathbb{H}}_{p}(F)$ , i.e., $\mathsf{B}^{\mathbb{H}}_{p}(F):=\mathsf{B}({\mathbb{H}}_{p}(F))$ . Since ${\mathbb{H}}(F)=\bigoplus_{p}{\mathbb{H}}_{p}(F)$ (following from Theorem 7), we have $\mathsf{B}^{\mathbb{H}}(F)=\bigsqcup_{p}\mathsf{B}^{\mathbb{H}}_{p}(F)$ .

Harmonic representatives.

In the rest of the section, we define harmonic representatives.

Proposition 9.

Let $[b,d]$ be an interval in $\mathsf{B}^{\mathbb{H}}(F)$ . The inclusion ${\mathbb{H}}(K_{b-1})\hookrightarrow{\mathbb{H}}(K_{b})$ in ${\mathbb{H}}(F)$ is forward. Moreover, if $d<m$ , then the inclusion ${\mathbb{H}}(K_{d})\hookleftarrow{\mathbb{H}}(K_{d+1})$ is backward.

Proof.

This follows from Theorem 7 and the fact that $\dim({\mathbb{H}}(K_{b}))=\dim({\mathbb{H}}(K_{b-1}))+1$ and $\dim({\mathbb{H}}(K_{d+1}))=\dim({\mathbb{H}}(K_{d}))-1$ . $\hfill\blacktriangleleft$

Representatives for general zigzag modules were introduced in [4, 46] (see also [26]), which consist of a sequence of cycles for each interval. However, since the harmonic chain groups are connected by inclusion maps in ${\mathbb{H}}(F)$ , we have:

Proposition 10.

Each representative for an interval in $\mathsf{B}^{\mathbb{H}}(F)$ contains a single harmonic cycle.

We then adapt the definition of representatives for general zigzag modules [26, 46] and define harmonic representatives as follows:

Definition 11 (Harmonic representative).

A harmonic $p$ -representative (or simply $p$ -representative) for an interval $[b,d]\in\mathsf{B}^{\mathbb{H}}_{p}(F)$ is a $p$ -cycle $z\in{\mathbb{H}}_{p}(K_{i})$ for $i\in[b,d]$ satisfying:

Birth condition:: $z$ is born in ${\mathbb{H}}_{p}(K_{b})$ , i.e., $z\in{\mathbb{H}}_{p}(K_{b})\setminus{\mathbb{H}}_{p}(K_{b-1})$ (notice that $b>0$ );
Death condition:: $z$ dies leaving ${\mathbb{H}}_{p}(K_{d})$ , i.e., $z\in{\mathbb{H}}_{p}(K_{d})\setminus{\mathbb{H}}_{p}(K_{d+1})$ if $d<m$ .

Sometimes we relax the restriction of $[b,d]\in\mathsf{B}^{\mathbb{H}}_{p}(F)$ and have a harmonic representative for an arbitrary integer interval $[b,d]\subseteq[0,m]$ . For details of the original definition of zigzag representatives and justification of Proposition 10 and Definition 11, see the full version of the paper.

5 A cubic-time algorithm for computing harmonic chain barcode

In this section, we propose an $O(m^{3})$ algorithm for computing the harmonic chain barcode and its harmonic representatives given a filtration containing $m$ insertions. We first overview the algorithm and then describe the implementation. Although there have been algorithms [9, 22, 26, 46] for computing zigzag barcodes in the general case, these algorithms target zigzag modules induced from directly taking the homology functor on zigzag filtrations. Our algorithm targets the special type of zigzag module ${\mathbb{H}}(F)$ , where harmonic chain groups are derived from an ordinary non-zigzag filtration and are connected by inclusions (on the chain level).

For simplicity, when describing the algorithm, complexes in a filtration are always indexed by integers instead of the real-valued timestamps (see Sec. 3.2). Again, we assume that the input is a simplex-wise filtration $F:\emptyset=K_{0}\xhookrightarrow{\;\sigma_{0}\;}K_{1}\xhookrightarrow{\;% \sigma_{1}\;}\cdots\xhookrightarrow{\;\sigma_{m-1}\;}K_{m}=K,$ where each $K_{i+1}$ differs from $K_{i}$ by the addition of a simplex $\sigma_{i}$ .

Algorithm 1 provides an overview: our algorithm computes the harmonic chain barcode by iteratively maintaining the harmonic representatives. It processes the insertions in $F$ one by one and finds pairings of the birth indices (starting points of the intervals) and death indices (ending points of the intervals) to form intervals in $\mathsf{B}^{\mathbb{H}}(F)$ . When we encounter a new birth index, it is initially unpaired; when we encounter a new death index, an unpaired birth index is chosen to pair with the death index.

The following definition helps present the algorithm.

Definition 12.

For an interval $[b,i]\subseteq[0,m]$ , a partial $p$ -representative for $[b,i]$ is a $p$ -representative as in Definition 11 by ignoring the death condition.

Algorithm 1 Computing the harmonic chain barcode.

Let $U^{p}$ be the set of unpaired birth indices for each homology degree $p$ , where $U^{p}=\emptyset$ initially. Before each iteration that processes the insertion $K_{i}\xhookrightarrow{\;\sigma_{i}\;}K_{i+1}$ , we maintain a $p$ -cycle $z$ for each $b\in U^{p}$ that is a partial representative for the interval $[b,i]$ . We use partial representatives to determine a finalized representative when a birth index is paired with a death index (by making sure the death condition is satisfied).

When processing the insertion of a $p$ -simplex $\sigma_{i}$ via $K_{i}\xhookrightarrow{\;\sigma_{i}\;}K_{i+1}$ , we proceed as follows:

If $\sigma_{i}$ is positive:

$\blacksquare$

Since $\dim({\mathbb{H}}_{p}(K_{i+1}))=\dim({\mathbb{H}}_{p}(K_{i}))+1$ (by Theorem 7), we add a new birth index $i+1$ to $U^{p}$ .
$\blacksquare$

Find a harmonic $p$ -cycle $z\in{\mathbb{H}}_{p}(K_{i+1})\setminus{\mathbb{H}}_{p}(K_{i})$ , and let $z$ be the partial representative for $i+1\in U^{p}$ .

If $\sigma_{i}$ is negative:

$\blacksquare$

Since $\dim({\mathbb{H}}_{p-1}(K_{i+1}))=\dim({\mathbb{H}}_{p-1}(K_{i}))-1$ , we have a new death index $i$ .
$\blacksquare$

Let $U^{p-1}=\{b_{j}\mid j=1,\ldots,k\}$ , where each $b_{j}$ has a partial $(p-1)$ -representative $z_{j}$ .
$\blacksquare$

Let $U^{\prime}=\{b_{j}\in U^{p-1}\mid z_{j}\not\in{\mathbb{H}}_{p-1}(K_{i+1})\}$ , i.e., $U^{\prime}$ contains all birth indices in $U^{p-1}$ whose partial representatives do not persist to $K_{i+1}$ .
$\blacksquare$

Pair the smallest (i.e., the “oldest”) index $b_{j^{*}}\in U^{\prime}$ with $i$ which forms a new interval $[b_{j^{*}},i]\in\mathsf{B}^{\mathbb{H}}_{p-1}(F)$ . Assign $z_{j^{*}}$ as the representative for $[b_{j^{*}},i]\in\mathsf{B}^{\mathbb{H}}_{p-1}(F)$ and remove $i$ from $U^{p-1}$ .
$\blacksquare$

Consider each $b_{j}\in U^{\prime}\setminus\{b_{j^{*}}\}$ . We have that $z_{j}\not\in{\mathbb{H}}_{p-1}(K_{i+1})$ because $\delta(z_{j})$ becomes non-zero in $K_{i+1}$ ( $\partial z_{j}$ is always zero after being born). Also, the only reason that $\delta(z_{j})\neq 0$ in $K_{i+1}$ is because $\alpha_{j}:=\delta(z_{j})(\sigma_{i})=z_{j}(\partial\sigma_{i})\neq 0$ . Let $\alpha_{*}=z_{j^{*}}(\partial\sigma_{i})$ . Update the partial representative for $b_{j}$ as $z_{j}:=z_{j}-(\alpha_{j}/\alpha_{*})\cdot z_{j^{*}}$ so that $z_{j}$ now persists to ${\mathbb{H}}_{p-1}(K_{i+1})$ .

After processing all the insertions, for each $b$ in each $U^{p}$ with a partial representative $z$ , let $[b,m]$ form an interval in ${\mathbb{H}}_{p}(F)$ with a representative $z$ .

Example.

Fig. 1 provides an example of how Algorithm 1 computes harmonic chain barcode ${\mathbb{H}}_{1}(F)$ and representatives for a filtration $F$ , with the resulting barcode in Fig. 2. For simplicity, $K_{0},K_{1},K_{2}$ are omitted and vertex insertions are ignored. In $K_{4}$ , $K_{5}$ , and $K_{7}$ , new 1-cycles are born that are also harmonic cycles due to a lack of triangles. The partial representatives $z_{4}$ , $z_{5}$ , $z_{7}$ for the indices $U^{1}=\{4,5,7\}$ all persist till $K_{7}$ . When the triangle $a b e$ is inserted in $K_{8}$ (producing a death index $7$ ), $\delta(z_{4})(abe)=1$ , $\delta(z_{5})(abe)=1$ , and $\delta(z_{7})(abe)=3$ . We pair $4\in U^{1}$ with $7$ and have $[4,7]\in{\mathbb{H}}_{1}(F)$ with a representative $z_{4}$ . We also let $z_{5}:=z_{5}-z_{4}$ and $z_{7}:=z_{7}-3z_{4}$ , which now both persist to ${\mathbb{H}}_{1}(K_{8})$ . The remaining steps are similar. Notice that when $a b e$ is inserted, the “alive” bar represented by the boundary of $a b e$ (i.e., $ab+be-ae$ ) is not killed. This is a significant difference from ordinary persistence (which will kill the alive bar represented by $\partial(abe)$ when $a b e$ is inserted).

Figure 1: An example of the computation of harmonic chain barcode

{\mathbb{H}}_{1}(F)

and representatives.

Figure 2: Harmonic chain barcode and ordinary persistence barcode for the filtration in Fig. 1. Deviating from conventions in ordinary persistence, bars are drawn as closed integer intervals, e.g.,

[7,7]

in the ordinary barcode is killed by the addition of

a b e

in

K_{8}

.

$\blacktriangleright$ Remark 13.

Algorithm 1 chooses the “oldest” birth, among the options, to pair with a death while the ordinary persistence chooses the “youngest” one [29]. A brief explanation is that a summation of representatives persists to the next harmonic chain group in ${\mathbb{H}}(F)$ , whereas a summation of representatives in the ordinary persistence becomes trivial in the next homology group (and cannot persist). We refer to [26, 46] for a formal definition of the different types of birth/death ends and how they impact the computation of persistence.

The following (rephrased) proposition from [24] helps prove the correctness of Algorithm 1:

Proposition 14 (Proposition 9, [24]).

If a pairing $\pi$ of the birth and death indices in ${\mathbb{H}}(F)$ satisfies that each interval from $\pi$ has a harmonic representative, then $\pi$ induces the harmonic chain barcode $\mathsf{B}^{\mathbb{H}}(F)$ .

Theorem 15.

Algorithm 1 correctly computes the harmonic chain barcode for filtration $F$ .

Proof.

We first show by induction that before Algorithm 1 processes each $\sigma_{i}$ , the $p$ -cycle $z$ maintained for any $b\in U^{p}$ is a partial $p$ -representative for $[b,i]$ . Suppose that the claim is true before processing $\sigma_{i}$ . If $\sigma_{i}$ is positive, index $i+1$ is added to $U^{p}$ and we assign $z\in{\mathbb{H}}_{p}(K_{i+1})\setminus{\mathbb{H}}_{p}(K_{i})$ to $i+1$ , which is clearly a partial representative for $[i+1,i+1]$ . For an index $b$ previously in $U^{p}$ having a partial representative $z$ , since ${\mathbb{H}}_{p}(K_{i})\subseteq{\mathbb{H}}_{p}(K_{i+1})$ (Theorem 7), we have that $z$ is still a partial representative for the interval $[b,i+1]$ .

In the case that $\sigma_{i}$ is negative, whenever we update a representative $z_{j}$ as $z_{j}-(\alpha_{j}/\alpha_{*})\cdot z_{j^{*}}$ , we have that $b_{j^{*}}<b_{j}$ and hence the updated $z_{j}$ remains born in ${\mathbb{H}}_{p-1}(K_{b_{j}})$ . Therefore, the new $z_{j}$ is still a partial representative for $[b,i]$ , which is also a partial representative for $[b,i+1]$ because now $z_{j}\in{\mathbb{H}}_{p-1}(K_{i+1})$ .

By Proposition 14, we only need to show that each interval output by the algorithm admits a harmonic representative. This follows from the algorithm. For example, whenever we output an interval $[b_{j^{*}},i]\in\mathsf{B}^{\mathbb{H}}_{p-1}(F)$ when $\sigma_{i}$ is negative, we have $z_{j^{*}}\not\in\mathsf{B}^{\mathbb{H}}_{p-1}(K_{i+1})$ , which ensures the death condition. $\hfill\blacktriangleleft$

Implementation.

Due to space limitations, we only briefly describe the gist of the implementation; refer to the full version of the paper for details and missing proofs. The only step in Algorithm 1 that cannot be easily implemented is finding a new harmonic cycle born in ${\mathbb{H}}_{p}(K_{i+1})$ when $\sigma_{i}$ is positive. In this case, the dimension of the harmonic chain group increases and we need to find a single harmonic cycle independent of the previous harmonic group. We can do this naively by computing a basis for the kernel of $\delta$ in $K_{i+1}$ , and check all cocycles in the basis to see if they are independent of the existing set of harmonic representatives maintained for $K_{i}$ . This, however, requires at least $\Theta(m^{3})$ per simplex insertion.

For a more efficient implementation, before iteration $i$ that processes the insertion $K_{i}\xhookrightarrow{\;\sigma_{i}\;}K_{i+1}$ , we maintain the following matrices for each homology degree $p$ :

1.

$\mathtt{H}^{p}$ : Columns in $\mathtt{H}^{p}$ are partial $p$ -representatives for all indices in $U^{p}$ .
2.

$\mathtt{R}^{p}$ : Columns in $\mathtt{R}^{p}$ form a boundary basis with distinct pivots for $B_{p}(K_{i})$ .
3.

$\mathtt{Cob}^{p}$ : Columns in $\mathtt{Cob}^{p}$ form a coboundary basis for $B^{p}(K_{i})$ .
4.

$\mathtt{SC}^{p}$ : Columns in $\mathtt{SC}^{p}$ encode “ $p$ -pseudo-cochains” (see full version for definition) in $K_{i}$ based on the basis provided in $\mathtt{R}^{p}$ , whose coboundaries are columns in $\mathtt{Cob}^{p+1}$ .
5.

$\mathtt{BoC}^{p}$ : Columns in $\mathtt{BoC}^{p}$ are boundaries of the coboundaries in $\mathtt{Cob}^{p+1}$ , with distinct pivots.

In summary, columns in $\mathtt{SC}^{p-1}$ , $\mathtt{Cob}^{p}$ , and $\mathtt{BoC}^{p-1}$ have one-to-one correspondence as follows:

\mathtt{SC}^{p-1}[j]\xmapsto{\ \delta\ }\mathtt{Cob}^{p}[j]\xmapsto{\ \partial% \ }\mathtt{BoC}^{p-1}[j].

Assuming $\sigma_{i}$ is a $p$ -simplex, the rationale for maintaining the matrices is as follows:

$\blacksquare$

We use $\mathtt{BoC}^{p-1}$ to find a linear combination $\phi$ of $\hat{\sigma}_{i}$ and cocycles in $\mathtt{Cob}^{p}$ such that $\partial\phi=0$ (see Algorithm 2). The cocycle $\phi$ is then a new harmonic $p$ -cycle when $\sigma_{i}$ is positive (see Proposition 16).
$\blacksquare$

$\mathtt{SC}^{p-1}$ helps maintain the coboundary basis in $\mathtt{Cob}^{p}$ .
$\blacksquare$

$\mathtt{R}^{p-1}$ provides the boundary basis on which pseudo-cochains in $\mathtt{SC}^{p-1}$ can be defined (again, refer to the full version for details of pseudo-cochains).

Algorithm 2 Reduction based on

\mathtt{BoC}^{p-1},\mathtt{Cob}^{p}

for finding a new-born harmonic cycle.

Proposition 16.

If Algorithm 2 ends with $\zeta=0$ , then $\sigma_{i}$ is positive and $\phi$ is a new harmonic $p$ -cycle born in ${\mathbb{H}}_{p}(K_{i+1})$ ; otherwise, $\sigma_{i}$ is negative.

Besides finding a new harmonic cycle when $\sigma_{i}$ is positive, our algorithm also needs to do the following: (1) update $\mathtt{Cob}^{p}$ (and also $\mathtt{BoC}^{p-1}$ ) because columns of $\mathtt{Cob}^{p}$ may not be coboundaries anymore as we proceed; (2) update $\mathtt{BoC}^{p-1}$ (and also $\mathtt{SC}^{p-1}$ , $\mathtt{Cob}^{p}$ ) to make pivots in $\mathtt{BoC}^{p-1}$ distinct again; (3) add a new coboundary to $\mathtt{Cob}^{p}$ (and new columns to $\mathtt{SC}^{p-1}$ , $\mathtt{BoC}^{p-1}$ ) to form a coboundary basis for $B_{p}(K_{i+1})$ when $\sigma_{i}$ is negative. See the full version for details. We conclude the following:

Theorem 17.

The harmonic chain barcode of $F$ can be computed in $O(m^{3})$ time.

6 Sublevel set harmonic chain barcode and its stability

In this section, we briefly introduce the notion of sublevel set harmonic chain barcodes and present our stability results based on this notion; for details and proofs, refer to the full version of the paper. Our stability proof makes use of the work on the algebraic stability of block decomposable ${\mathbb{R}}^{2}$ -modules [1, 6]. In brief, we “lift” the 1-parameter harmonic zigzag module to an ${\mathbb{R}}^{2}$ -indexed 2-parameter persistence module which is block decomposable. We then show that in the typical setting of sublevel set filtrations, there exists an interleaving between the lifted modules. Our main work here is to construct a concrete extension to ${\mathbb{R}}^{2}$ -modules and an interleaving between the extensions realizing the category-theoretic concepts employed in [1, 6]. From the Isometry Theorem [3, 6], we then deduce the stability of the sublevel set harmonic chain barcode. We also address the disparity between the natural harmonic chain barcode of a sublevel set filtration (which consists of closed-open intervals¹¹1The closed-open intervals over the real values we have here are different from the closed-open intervals of [1, 6] over the integers. Indeed, when considering only integer indices, we only have closed-closed intervals in our setting. The extension of our closed-open interval would be similar to a closed block of [6] but with the right vertical side open.) and common conventions of zigzag persistence (which work with closed-closed intervals in our setting).

We assume, up until now, that a filtration is simplex-wise. This assumption is not true for a sublevel set filtration, but we shall construct a simplex-wise filtration from a general filtration.

Let $\tilde{F}$ be an increasing filtration of $K$ that is not necessarily simplex-wise, i.e., two consecutive complexes in $\tilde{F}$ can differ by more than one simplex. We fix an ordering, once and for all, for vertices of $K$ , which also fixes an ordering for all simplices in $K$ (using, say, the lexicographic ordering of the ordered sequence of vertices in a simplex). Given $\delta>0$ small enough, we expand $\tilde{F}$ into a simplex-wise filtration $\tilde{F}(\delta)$ by expanding each inclusion $K_{t_{i-1}}\hookrightarrow K_{t_{i}}$ in $\tilde{F}$ starting with $i=1$ . To differentiate, denote each complex in $\tilde{F}(\delta)$ as $K^{\prime}_{t}$ where $t\in\mathbb{R}$ is a timestamp. In each iteration, we expand the inclusion $K_{t_{i-1}}\hookrightarrow K_{t_{i}}$ in $\tilde{F}$ into several simplex-wise inclusions in $\tilde{F}(\delta)$ :

K_{t_{i-1}}=K^{\prime}_{s}\hookrightarrow K^{\prime}_{t_{i}-\delta}% \hookrightarrow K^{\prime}_{t_{i}}\hookrightarrow K^{\prime}_{t_{i}+\delta}% \hookrightarrow\cdots\hookrightarrow K^{\prime}_{t_{i}+(k-1)\delta}=K_{t_{i}}.

In the above, $K^{\prime}_{t_{i}-\delta}$ is a “dummy” complex equal to $K^{\prime}_{s}$ (so $K^{\prime}_{s}\hookrightarrow K^{\prime}_{t_{i}-\delta}$ is an identity map) and $k$ is the number of simplices added from $K_{t_{i-1}}$ to $K_{t_{i}}$ in $\tilde{F}$ . We also have that the $k$ number of simplices are added based on their simplex ordering described above.

To see the rationale of introducing $\tilde{F}(\delta)$ , we first define the following:

Definition 18.

Let $\tilde{F}$ be an increasing filtration of complex $K$ that is not necessarily simplex-wise and let $z\in Z_{p}(K)$ be a $p$ -cycle. Let $t_{b(z)}$ be the time when $z$ is born, i.e., $z\in Z_{p}(K_{t_{b(z)}})\setminus Z_{p}(K_{t_{b(z)-1}})$ , and $t_{d(z)}$ be the time when $z$ dies as a harmonic chain, i.e., $\delta(z)\neq 0$ in $K_{t_{d(z)}}$ , but $\delta(z)=0$ in $K_{t}$ for $t_{b(z)}\leq t<t_{d(z)}$ . Define the span of $z$ as $span(z):=[t_{b(z)},t_{d(z)})$ . If $z$ is not harmonic at birth, its span is the empty set (notice that a cycle continues to be non-harmonic once it becomes so). Moreover, define the bar of $z$ as $bar(z):=[t_{b(z)},t_{d(z)-1}]$ .

Based on the construction, we observe a relation between the bar of $z$ in $\tilde{F}(\delta)$ and the span of $z$ in $\tilde{F}$ for a cycle $z$ . Moreover, adding the dummy complexes makes sure that the closed bars of the simplex-wise filtration $\tilde{F}(\delta)$ “induce” the closed-open time intervals in $\tilde{F}$ in which a cycle is harmonic (see full version for details). In particular, for any small $\delta$ , we obtain an obvious mapping $\Gamma:\tilde{F}(\delta)\xrightarrow{}\tilde{F}$ . We then have the following Definition 19.

Definition 19.

Let $F$ be a simplex-wise filtration (as in Sec. 3.2) and let $\breve{\mathsf{B}}^{\mathbb{H}}(F)$ be the closed-open barcode of ${\mathbb{H}}{(F)}$ , i.e., $[t_{b},t_{d})\in\breve{\mathsf{B}}^{\mathbb{H}}(F)$ iff $[t_{b},t_{d-1}]\in\mathsf{B}^{\mathbb{H}}(F)$ . Moreover, let $\tilde{F}$ and $\tilde{F}(\delta)$ be as defined in this section. We define the harmonic chain barcode of $\tilde{F}$ as the set $\breve{\mathsf{B}}^{\mathbb{H}}(\tilde{F}):=\Gamma(\breve{\mathsf{B}}^{\mathbb% {H}}(\tilde{F}(\delta)))$ for $\delta$ small enough.

$\blacktriangleright$ Remark 20.

Note that $\breve{\mathsf{B}}^{\mathbb{H}}(\tilde{F})$ is the limit of $\mathsf{B}^{\mathbb{H}}(\tilde{F}(\delta))$ as $\delta$ approaches 0.

We now state our stability result for sublevel set filtrations. See the full version for the proof of this theorem (and additional observations).

Theorem 21.

Let $\hat{f},\hat{g}:|K|\xrightarrow{}{\mathbb{R}}$ be simplex-wise linear functions, and let $\tilde{F}$ and $\tilde{G}$ be the sublevel set filtrations of $\hat{f}$ and $\hat{g}$ respectively. Then,

d_{B}({\breve{\mathsf{B}}^{\mathbb{H}}(\tilde{F})},{\breve{\mathsf{B}}^{% \mathbb{H}}(\tilde{G}}))\leq||\hat{f}-\hat{g}||_{\infty}.

Inducing the barcode $\breve{\mathsf{B}}^{\mathbb{H}}(\tilde{F})$ from $\breve{\mathsf{B}}^{\mathbb{H}}(\tilde{F}(\delta))$ allows us to use the off-the-shelf results of [6] for proving stability and does not affect the computation of $\breve{\mathsf{B}}^{\mathbb{H}}(\tilde{F})$ . In particular, we have the following.

Theorem 22.

Given a sublevel-set filtration $\tilde{F}$ of the complex $K$ with $m$ simplices, the harmonic chain barcode $\breve{\mathsf{B}}^{\mathbb{H}}(\tilde{F})$ can be computed in $O(m^{3})$ time.

Proof.

The computation of $\breve{\mathsf{B}}^{\mathbb{H}}(\tilde{F})$ is equivalent to the computation of $\mathsf{B}^{\mathbb{H}}(\tilde{F}(\delta))$ for a single $\delta$ small enough, using the algorithm in Sec. 5 and mapping the resulting bars using $\Gamma$ to the filtration $\tilde{F}$ . This simply amounts to changing timestamps of the form $t_{i}\pm\ell\delta$ into $t_{i}$ . $\hfill\blacktriangleleft$

References

[1] Håvard Bakke Bjerkevik. On the stability of interval decomposable persistence modules. Discrete & Computational Geometry, 66(1):92–121, 2021. doi:10.1007/S00454-021-00298-0.
[2] Saugata Basu and Nathanael Cox. Harmonic persistent homology. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 1112–1123. IEEE, 2022.
[3] Ulrich Bauer and Michael Lesnick. Induced matchings of barcodes and the algebraic stability of persistence. In Proceedings of the thirtieth annual symposium on Computational geometry, pages 355–364, 2014.
[4] Paul Bendich, Herbert Edelsbrunner, Dmitriy Morozov, and Amit Patel. Homology and robustness of level and interlevel sets. Homology, homotopy, and applications, 15(1):51–72, 2013.
[5] Glencora Borradaile, William Maxwell, and Amir Nayyeri. Minimum bounded chains and minimum homologous chains in embedded simplicial complexes. In Proceedings of the 36th International Symposium on Computational Geometry (SoCG 2020). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020.
[6] Magnus Botnan and Michael Lesnick. Algebraic stability of zigzag persistence modules. Algebraic & geometric topology, 18(6):3133–3204, 2018.
[7] Oleksiy Busaryev, Tamal K. Dey, and Yusu Wang. Tracking a generator by persistence. In My T. Thai and Sartaj Sahni, editors, Computing and Combinatorics, pages 278–287, 2010. doi:10.1007/978-3-642-14031-0_31.
[8] Gunnar Carlsson and Vin de Silva. Zigzag persistence. Foundations of Computational Mathematics, 10(4):367–405, 2010. doi:10.1007/S10208-010-9066-0.
[9] Gunnar Carlsson, Vin de Silva, and Dmitriy Morozov. Zigzag persistent homology and real-valued functions. In Proceedings of the 25th Annual Symposium on Computational Geometry, pages 247–256, 2009. doi:10.1145/1542362.1542408.
[10] Gunnar Carlsson, Afra J. Zomorodian, Anne Collins, and Leonidas J. Guibas. Persistence barcodes for shapes. Proceedings Eurographs/ACM SIGGRAPH Symposium on Geometry Processing, pages 124–135, 2004. doi:10.2312/SGP/SGP04/127-138.
[11] Erin W. Chambers, Jeff Erickson, Kyle Fox, and Amir Nayyeri. Minimum cuts in surface graphs. SIAM Journal on Computing, 52(1):156–195, 2023. doi:10.1137/19M1291820.
[12] Erin W. Chambers, Jeff Erickson, and Amir Nayyeri. Minimum cuts and shortest homologous cycles. In Proceedings of the 25th International Symposium on Computational Geometry (SoCG 2009). ACM Press, 2009. doi:10.1145/1542362.1542426.
[13] Erin Wolf Chambers, Salman Parsa, and Hannah Schreiber. On complexity of computing bottleneck and lexicographic optimal cycles in a homology class. In Proceedings of the 38th International Symposium on Computational Geometry (SoCG). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022.
[14] Frédéric Chazal, David Cohen-Steiner, Marc Glisse, Leonidas J. Guibas, and Steve Y. Oudot. Proximity of persistence modules and their diagrams. In 25th Annual Symposium on Computational Geometry (SoCG 2009), pages 237–246, New York, NY, USA, 2009. Association for Computing Machinery. doi:10.1145/1542362.1542407.
[15] Frédéric Chazal, Vin De Silva, Marc Glisse, and Steve Oudot. The Structure and Stability of Persistence Modules, volume 10. Springer, 2016. doi:10.1007/978-3-319-42545-0.
[16] Chao Chen and Daniel Freedman. Measuring and computing natural generators for homology groups. Computational Geometry, 43(2):169–181, 2010. Special Issue on the 24th European Workshop on Computational Geometry (EuroCG’08). doi:10.1016/j.comgeo.2009.06.004.
[17] Chao Chen and Daniel Freedman. Hardness results for homology localization. Discrete & Computational Geometry, 45(3):425–448, 2011. doi:10.1007/S00454-010-9322-8.
[18] Jiahui Chen, Yuchi Qiu, Rui Wang, and Guo-Wei Wei. Persistent Laplacian projected Omicron BA. 4 and BA. 5 to become new dominating variants. Computers in Biology and Medicine, 151:106262, 2022. doi:10.1016/J.COMPBIOMED.2022.106262.
[19] David Cohen-Steiner, Herbert Edelsbrunner, and John Harer. Stability of persistence diagrams. In Proceedings of the 21st Annual Symposium on Computational Geometry, pages 263–271, 2005. doi:10.1145/1064092.1064133.
[20] Alessandro De Gregorio, Marco Guerra, Sara Scaramuccia, and Francesco Vaccarino. Parallel decomposition of persistence modules through interval bases. arXiv preprint, 2021. arXiv:2106.11884.
[21] Vin De Silva, Dmitriy Morozov, and Mikael Vejdemo-Johansson. Persistent cohomology and circular coordinates. Discrete & Computational Geometry, 45(4):737–759, 2011. doi:10.1007/S00454-011-9344-X.
[22] Tamal K. Dey, Fengtao Fan, and Yusu Wang. Computing topological persistence for simplicial maps. In Proceedings of the Twenty-Second Annual Symposium on Computational Geometry, pages 345–354, New York, NY, USA, 2014. Association for Computing Machinery. doi:10.1145/2582112.2582165.
[23] Tamal K. Dey, Anil N. Hirani, and Bala Krishnamoorthy. Optimal homologous cycles, total unimodularity, and linear programming. In Proceedings of the 42nd ACM Symposium on Theory of Computing, pages 221–230, 2010. doi:10.1145/1806689.1806721.
[24] Tamal K. Dey and Tao Hou. Computing zigzag persistence on graphs in near-linear time. In 37th International Symposium on Computational Geometry, 2021.
[25] Tamal K Dey, Tao Hou, and Sayan Mandal. Computing minimal persistent cycles: Polynomial and hard cases. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2587–2606. SIAM, 2020. doi:10.1137/1.9781611975994.158.
[26] Tamal K. Dey, Tao Hou, and Dmitriy Morozov. A fast algorithm for computing zigzag representatives. ACM-SIAM Symposium on Discrete Algorithms (SODA) 2025, to appear, 2025.
[27] Tamal Krishna Dey and Yusu Wang. Computational Topology for Data Analysis. Cambridge University Press, 2022.
[28] Beno Eckmann. Harmonische Funktionen und Randwertaufgaben in einem Komplex. Commentarii Mathematici Helvetici, 17(1):240–255, 1944.
[29] Edelsbrunner, Letscher, and Zomorodian. Topological persistence and simplification. Discrete & Computational Geometry, 28:511–533, 2002. doi:10.1007/S00454-002-2885-2.
[30] Herbert Edelsbrunner and John Harer. Computational Topology: An Introduction. Applied Mathematics. American Mathematical Society, 2010.
[31] Robert Ghrist. Barcodes: The persistent topology of data. Bullentin of the American Mathematical Society, 45:61–75, 2008.
[32] Joshua A. Grochow and Jamie Tucker-Foltz. Computational topology and the unique games conjecture. In Proceedings of 34th International Symposium on Computational Geometry (SoCG 2018). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018.
[33] Nicola Guglielmi, Anton Savostianov, and Francesco Tudisco. Quantifying the structural stability of simplicial homology. arXiv preprint, 2023. doi:10.48550/arXiv.2301.03627.
[34] Aziz Burak Gülen, Facundo Mémoli, and Zhengchao Wan. Orthogonal Möbius inversion and Grassmannian persistence diagrams. arXiv preprint, 2024. arXiv:2311.06870.
[35] Davide Gurnari, Aldo Guzmán-Sáenz, Filippo Utro, Aritra Bose, Saugata Basu, and Laxmi Parida. Probing omics data via harmonic persistent homology. arXiv preprint, 2023. arXiv:2311.06357.
[36] Yasuaki Hiraoka, Takenobu Nakamura, Akihiko Hirata, Emerson G Escolar, Kaname Matsue, and Yasumasa Nishiura. Hierarchical structures of amorphous solids characterized by persistent homology. Proceedings of the National Academy of Sciences, 113(26):7035–7040, 2016.
[37] Danijela Horak and Jürgen Jost. Spectra of combinatorial Laplace operators on simplicial complexes. Advances in Mathematics, 244:303–336, 2013.
[38] Parvaneh Joharinad and Jürgen Jost. Mathematical principles of topological and geometric data analysis. Springer, 2023.
[39] Alexandros Keros and Kartic Subr. Spectral coarsening with Hodge Laplacians. In ACM SIGGRAPH 2023 Conference Proceedings, pages 1–11, 2023.
[40] G. Kirchhoff. Ueber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird. Annalen der Physik, 148(12):497–508, 1847. doi:10.1002/andp.18471481202.
[41] Hyekyoung Lee, Moo K Chung, Hongyoon Choi, Hyejin Kang, Seunggyun Ha, Yu Kyeong Kim, and Dong Soo Lee. Harmonic holes as the submodules of brain network and network dissimilarity. In Computational Topology in Image Context: 7th International Workshop, CTIC 2019, Málaga, Spain, January 24-25, 2019, Proceedings 7, pages 110–122. Springer, 2019. doi:10.1007/978-3-030-10828-1_9.
[42] Mao Li, Keith Duncan, Christopher N. Topp, and Daniel H. Chitwood. Persistent homology and the branching topologies of plants. American Journal of Botany, 104(3):349–353, 2017.
[43] Andre Lieutier. Persistent harmonic forms. https://project.inria.fr/gudhi/files/2014/10/Persistent-Harmonic-Forms.pdf.
[44] Jian Liu, Jingyan Li, and Jie Wu. The algebraic stability for persistent Laplacians. arXiv preprint, 2023. arXiv:2302.03902.
[45] Jiajie Luo and Gregory Henselman-Petrusek. Interval decomposition for persistence modules freely generated over PIDs. arXiv preprint, 2023. arXiv:2310.07971.
[46] Clément Maria and Steve Y. Oudot. Zigzag persistence via reflections and transpositions. In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 181–199. SIAM, 2015. doi:10.1137/1.9781611973730.14.
[47] Facundo Mémoli, Zhengchao Wan, and Yusu Wang. Persistent Laplacians: Properties, algorithms and implications. SIAM Journal on Mathematics of Data Science, 4(2):858–884, 2022. doi:10.1137/21M1435471.
[48] Russell Merris. Laplacian matrices of graphs: a survey. Linear Algebra and its Applications, 197-198:143–176, 1994. doi:10.1016/0024-3795(94)90486-3.
[49] Joshua Mike and Jose Perea. Multiscale geometric data analysis via Laplacian eigenvector cascading. In 2019 18th IEEE International Conference On Machine Learning And Applications (ICMLA), pages 1091–1098. IEEE, 2019. doi:10.1109/ICMLA.2019.00183.
[50] Bojan Mohar, Y Alavi, G Chartrand, and OR Oellermann. The Laplacian spectrum of graphs. Graph theory, combinatorics, and applications, 2(871-898):12, 1991.
[51] Ippei Obayashi. Volume-optimal cycle: Tightest representative cycle of a generator in persistent homology. SIAM Journal on Applied Algebra and Geometry, 2(4):508–534, 2018. doi:10.1137/17M1159439.
[52] Rui Wang, Duc Duy Nguyen, and Guo-Wei Wei. Persistent spectral graph. International journal for numerical methods in biomedical engineering, 36(9):e3376, 2020.
[53] Afra J Zomorodian. Topology for computing, volume 16. Cambridge university press, 2005.

[bib.bib1] [1] Håvard Bakke Bjerkevik. On the stability of interval decomposable persistence modules. Discrete & Computational Geometry, 66(1):92–121, 2021. doi:10.1007/S00454-021-00298-0.

[bib.bib2] [2] Saugata Basu and Nathanael Cox. Harmonic persistent homology. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 1112–1123. IEEE, 2022.

[bib.bib3] [3] Ulrich Bauer and Michael Lesnick. Induced matchings of barcodes and the algebraic stability of persistence. In Proceedings of the thirtieth annual symposium on Computational geometry, pages 355–364, 2014.

[bib.bib4] [4] Paul Bendich, Herbert Edelsbrunner, Dmitriy Morozov, and Amit Patel. Homology and robustness of level and interlevel sets. Homology, homotopy, and applications, 15(1):51–72, 2013.

[bib.bib5] [5] Glencora Borradaile, William Maxwell, and Amir Nayyeri. Minimum bounded chains and minimum homologous chains in embedded simplicial complexes. In Proceedings of the 36th International Symposium on Computational Geometry (SoCG 2020). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020.

[bib.bib6] [6] Magnus Botnan and Michael Lesnick. Algebraic stability of zigzag persistence modules. Algebraic & geometric topology, 18(6):3133–3204, 2018.

[bib.bib7] [7] Oleksiy Busaryev, Tamal K. Dey, and Yusu Wang. Tracking a generator by persistence. In My T. Thai and Sartaj Sahni, editors, Computing and Combinatorics, pages 278–287, 2010. doi:10.1007/978-3-642-14031-0_31.

[bib.bib8] [8] Gunnar Carlsson and Vin de Silva. Zigzag persistence. Foundations of Computational Mathematics, 10(4):367–405, 2010. doi:10.1007/S10208-010-9066-0.

[bib.bib9] [9] Gunnar Carlsson, Vin de Silva, and Dmitriy Morozov. Zigzag persistent homology and real-valued functions. In Proceedings of the 25th Annual Symposium on Computational Geometry, pages 247–256, 2009. doi:10.1145/1542362.1542408.

[bib.bib10] [10] Gunnar Carlsson, Afra J. Zomorodian, Anne Collins, and Leonidas J. Guibas. Persistence barcodes for shapes. Proceedings Eurographs/ACM SIGGRAPH Symposium on Geometry Processing, pages 124–135, 2004. doi:10.2312/SGP/SGP04/127-138.

[bib.bib11] [11] Erin W. Chambers, Jeff Erickson, Kyle Fox, and Amir Nayyeri. Minimum cuts in surface graphs. SIAM Journal on Computing, 52(1):156–195, 2023. doi:10.1137/19M1291820.

[bib.bib12] [12] Erin W. Chambers, Jeff Erickson, and Amir Nayyeri. Minimum cuts and shortest homologous cycles. In Proceedings of the 25th International Symposium on Computational Geometry (SoCG 2009). ACM Press, 2009. doi:10.1145/1542362.1542426.

[bib.bib13] [13] Erin Wolf Chambers, Salman Parsa, and Hannah Schreiber. On complexity of computing bottleneck and lexicographic optimal cycles in a homology class. In Proceedings of the 38th International Symposium on Computational Geometry (SoCG). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022.

[bib.bib14] [14] Frédéric Chazal, David Cohen-Steiner, Marc Glisse, Leonidas J. Guibas, and Steve Y. Oudot. Proximity of persistence modules and their diagrams. In 25th Annual Symposium on Computational Geometry (SoCG 2009), pages 237–246, New York, NY, USA, 2009. Association for Computing Machinery. doi:10.1145/1542362.1542407.

[bib.bib15] [15] Frédéric Chazal, Vin De Silva, Marc Glisse, and Steve Oudot. The Structure and Stability of Persistence Modules, volume 10. Springer, 2016. doi:10.1007/978-3-319-42545-0.

[bib.bib16] [16] Chao Chen and Daniel Freedman. Measuring and computing natural generators for homology groups. Computational Geometry, 43(2):169–181, 2010. Special Issue on the 24th European Workshop on Computational Geometry (EuroCG’08). doi:10.1016/j.comgeo.2009.06.004.

[bib.bib17] [17] Chao Chen and Daniel Freedman. Hardness results for homology localization. Discrete & Computational Geometry, 45(3):425–448, 2011. doi:10.1007/S00454-010-9322-8.

[bib.bib18] [18] Jiahui Chen, Yuchi Qiu, Rui Wang, and Guo-Wei Wei. Persistent Laplacian projected Omicron BA. 4 and BA. 5 to become new dominating variants. Computers in Biology and Medicine, 151:106262, 2022. doi:10.1016/J.COMPBIOMED.2022.106262.

[bib.bib19] [19] David Cohen-Steiner, Herbert Edelsbrunner, and John Harer. Stability of persistence diagrams. In Proceedings of the 21st Annual Symposium on Computational Geometry, pages 263–271, 2005. doi:10.1145/1064092.1064133.

[bib.bib20] [20] Alessandro De Gregorio, Marco Guerra, Sara Scaramuccia, and Francesco Vaccarino. Parallel decomposition of persistence modules through interval bases. arXiv preprint, 2021. arXiv:2106.11884.

[bib.bib21] [21] Vin De Silva, Dmitriy Morozov, and Mikael Vejdemo-Johansson. Persistent cohomology and circular coordinates. Discrete & Computational Geometry, 45(4):737–759, 2011. doi:10.1007/S00454-011-9344-X.

[bib.bib22] [22] Tamal K. Dey, Fengtao Fan, and Yusu Wang. Computing topological persistence for simplicial maps. In Proceedings of the Twenty-Second Annual Symposium on Computational Geometry, pages 345–354, New York, NY, USA, 2014. Association for Computing Machinery. doi:10.1145/2582112.2582165.

[bib.bib23] [23] Tamal K. Dey, Anil N. Hirani, and Bala Krishnamoorthy. Optimal homologous cycles, total unimodularity, and linear programming. In Proceedings of the 42nd ACM Symposium on Theory of Computing, pages 221–230, 2010. doi:10.1145/1806689.1806721.

[bib.bib24] [24] Tamal K. Dey and Tao Hou. Computing zigzag persistence on graphs in near-linear time. In 37th International Symposium on Computational Geometry, 2021.

[bib.bib25] [25] Tamal K Dey, Tao Hou, and Sayan Mandal. Computing minimal persistent cycles: Polynomial and hard cases. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2587–2606. SIAM, 2020. doi:10.1137/1.9781611975994.158.

[bib.bib26] [26] Tamal K. Dey, Tao Hou, and Dmitriy Morozov. A fast algorithm for computing zigzag representatives. ACM-SIAM Symposium on Discrete Algorithms (SODA) 2025, to appear, 2025.

[bib.bib27] [27] Tamal Krishna Dey and Yusu Wang. Computational Topology for Data Analysis. Cambridge University Press, 2022.

[bib.bib28] [28] Beno Eckmann. Harmonische Funktionen und Randwertaufgaben in einem Komplex. Commentarii Mathematici Helvetici, 17(1):240–255, 1944.

[bib.bib29] [29] Edelsbrunner, Letscher, and Zomorodian. Topological persistence and simplification. Discrete & Computational Geometry, 28:511–533, 2002. doi:10.1007/S00454-002-2885-2.

[bib.bib30] [30] Herbert Edelsbrunner and John Harer. Computational Topology: An Introduction. Applied Mathematics. American Mathematical Society, 2010.

[bib.bib31] [31] Robert Ghrist. Barcodes: The persistent topology of data. Bullentin of the American Mathematical Society, 45:61–75, 2008.

[bib.bib32] [32] Joshua A. Grochow and Jamie Tucker-Foltz. Computational topology and the unique games conjecture. In Proceedings of 34th International Symposium on Computational Geometry (SoCG 2018). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018.

[bib.bib33] [33] Nicola Guglielmi, Anton Savostianov, and Francesco Tudisco. Quantifying the structural stability of simplicial homology. arXiv preprint, 2023. doi:10.48550/arXiv.2301.03627.

[bib.bib34] [34] Aziz Burak Gülen, Facundo Mémoli, and Zhengchao Wan. Orthogonal Möbius inversion and Grassmannian persistence diagrams. arXiv preprint, 2024. arXiv:2311.06870.

[bib.bib35] [35] Davide Gurnari, Aldo Guzmán-Sáenz, Filippo Utro, Aritra Bose, Saugata Basu, and Laxmi Parida. Probing omics data via harmonic persistent homology. arXiv preprint, 2023. arXiv:2311.06357.

[bib.bib36] [36] Yasuaki Hiraoka, Takenobu Nakamura, Akihiko Hirata, Emerson G Escolar, Kaname Matsue, and Yasumasa Nishiura. Hierarchical structures of amorphous solids characterized by persistent homology. Proceedings of the National Academy of Sciences, 113(26):7035–7040, 2016.

[bib.bib37] [37] Danijela Horak and Jürgen Jost. Spectra of combinatorial Laplace operators on simplicial complexes. Advances in Mathematics, 244:303–336, 2013.

[bib.bib38] [38] Parvaneh Joharinad and Jürgen Jost. Mathematical principles of topological and geometric data analysis. Springer, 2023.

[bib.bib39] [39] Alexandros Keros and Kartic Subr. Spectral coarsening with Hodge Laplacians. In ACM SIGGRAPH 2023 Conference Proceedings, pages 1–11, 2023.

[bib.bib40] [40] G. Kirchhoff. Ueber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird. Annalen der Physik, 148(12):497–508, 1847. doi:10.1002/andp.18471481202.

[bib.bib41] [41] Hyekyoung Lee, Moo K Chung, Hongyoon Choi, Hyejin Kang, Seunggyun Ha, Yu Kyeong Kim, and Dong Soo Lee. Harmonic holes as the submodules of brain network and network dissimilarity. In Computational Topology in Image Context: 7th International Workshop, CTIC 2019, Málaga, Spain, January 24-25, 2019, Proceedings 7, pages 110–122. Springer, 2019. doi:10.1007/978-3-030-10828-1_9.

[bib.bib42] [42] Mao Li, Keith Duncan, Christopher N. Topp, and Daniel H. Chitwood. Persistent homology and the branching topologies of plants. American Journal of Botany, 104(3):349–353, 2017.

[bib.bib43] [43] Andre Lieutier. Persistent harmonic forms. https://project.inria.fr/gudhi/files/2014/10/Persistent-Harmonic-Forms.pdf.

[bib.bib44] [44] Jian Liu, Jingyan Li, and Jie Wu. The algebraic stability for persistent Laplacians. arXiv preprint, 2023. arXiv:2302.03902.

[bib.bib45] [45] Jiajie Luo and Gregory Henselman-Petrusek. Interval decomposition for persistence modules freely generated over PIDs. arXiv preprint, 2023. arXiv:2310.07971.

[bib.bib46] [46] Clément Maria and Steve Y. Oudot. Zigzag persistence via reflections and transpositions. In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 181–199. SIAM, 2015. doi:10.1137/1.9781611973730.14.

[bib.bib47] [47] Facundo Mémoli, Zhengchao Wan, and Yusu Wang. Persistent Laplacians: Properties, algorithms and implications. SIAM Journal on Mathematics of Data Science, 4(2):858–884, 2022. doi:10.1137/21M1435471.

[bib.bib48] [48] Russell Merris. Laplacian matrices of graphs: a survey. Linear Algebra and its Applications, 197-198:143–176, 1994. doi:10.1016/0024-3795(94)90486-3.

[bib.bib49] [49] Joshua Mike and Jose Perea. Multiscale geometric data analysis via Laplacian eigenvector cascading. In 2019 18th IEEE International Conference On Machine Learning And Applications (ICMLA), pages 1091–1098. IEEE, 2019. doi:10.1109/ICMLA.2019.00183.

[bib.bib50] [50] Bojan Mohar, Y Alavi, G Chartrand, and OR Oellermann. The Laplacian spectrum of graphs. Graph theory, combinatorics, and applications, 2(871-898):12, 1991.

[bib.bib51] [51] Ippei Obayashi. Volume-optimal cycle: Tightest representative cycle of a generator in persistent homology. SIAM Journal on Applied Algebra and Geometry, 2(4):508–534, 2018. doi:10.1137/17M1159439.

[bib.bib52] [52] Rui Wang, Duc Duy Nguyen, and Guo-Wei Wei. Persistent spectral graph. International journal for numerical methods in biomedical engineering, 36(9):e3376, 2020.

[bib.bib53] [53] Afra J Zomorodian. Topology for computing, volume 16. Cambridge university press, 2005.

Tracking the Persistence of Harmonic Chains: Barcode and Stability

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

2 Related work

Relation to the work of Basu and Cox.

3 Background

3.1 Harmonic cycles

Definition 1.

Lemma 2 ([28]).

Proposition 3 ([21]).

3.2 Ordinary persistence

Stability of persistence diagram/barcode.

Theorem 4.

3.3 Zigzag persistence

Conventions.

4 Harmonic chain barcodes and representatives

Proposition 5.

Proof.

Definition 6.

Theorem 7.

Proof.

Definition 8 (Harmonic chain barcode).

Harmonic representatives.

Proposition 9.

Proof.

Proposition 10.

Definition 11 (Harmonic representative).

5 A cubic-time algorithm for computing harmonic chain barcode

Definition 12.

Example.

▶ Remark 13.

Proposition 14 (Proposition 9, [24]).

Theorem 15.

Proof.

Implementation.

Proposition 16.

Theorem 17.

6 Sublevel set harmonic chain barcode and its stability

Definition 18.

Definition 19.

▶ Remark 20.

Theorem 21.

Theorem 22.

Proof.

References

$\blacktriangleright$ Remark 13.

$\blacktriangleright$ Remark 20.