Tracking the Persistence of Harmonic Chains: Barcode and Stability

Tao Hou, Salman Parsa, Bei Wang · 2024

Read Tracking the Persistence of Harmonic Chains: Barcode and Stability by Tao Hou, Salman Parsa, Bei Wang (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-15419.txt.

Introduction

Data's shape can be tracked as features are born and die across scales, but standard barcodes miss a finer signal. Tao Hou, Salman Parsa, and Bei Wang define a new barcode built from harmonic chains. It follows those special cycles through a growing data complex. The authors prove the new barcode is stable, so small data noise cannot wreck it. An algorithm computes it in cubic time in the size of the complex.

The descriptor joins the standard barcode as a companion for feature building and learning. Wherever persistence methods already serve, such as shape and network analysis, the harmonic version may add detail. Stability plus a concrete algorithm make it usable, not just definable. The paper is a tool-building contribution to topological data analysis.

Catalog record

CREATORTao Hou, Salman Parsa, Bei Wang
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE85 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-15419

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Tracking the Persistence of Harmonic Chains: Barcode and Stability Tao Hou, Salman Parsa, Bei Wang 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 m , we present an algorithm to compute its harmonic chain barcode in O ⁡ ( m 3 ) 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. 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 Figures 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 [ 37 ] 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 barcode is 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 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. Guglielmi et al. [ 33 ] studied the stability of higher-order Laplacians. Horak and Jost [ 38 ] defined a weighted Laplacian for simplicial complexes. Already their theoretical results on Laplacian [ 38 ] anticipated the possibility of applications, as the harmonic chains are thought to contain important geometric information. This has been validated by recent

Read the complete text