PaperlayerView exact revision on arXiv

Source-linked AI summary

Persistent 1-Cycles: Definition, Computation, and Its Application

Tamal K. Dey, Tao Hou, Sayan Mandal

arXiv:1810.04807v2cs.CGmath.AT

TL;DR

Computing representative cycles for persistent H1 features matters in applications that need more than the intervals in a persistence diagram, but their relation to persistence homology has not been explicitly explained. The paper defines persistent 1-cycles using interval module decomposition and gives a polynomial-time algorithm for meaningful cycles. It proves optimal-cycle computation is NP-hard and reports that its algorithm is more time-efficient without worse results than an optimal cycle-generating algorithm.

  • Problem

    Some applications need representative cycles for persistence intervals, and their relation to persistent homology has not been explicitly explained.

    Source: §1 · p. 2

  • Method

    The paper defines persistent 1-cycles through interval module decomposition and computes meaningful cycles with a polynomial-time algorithm.

    Source: §1 · p. 2

  • Results

    The computation of optimal persistent 1-cycles is NP-hard, while the proposed polynomial-time algorithm is no worse than an optimal cycle-generating algorithm and is more time-efficient.

    Source: §1 · pp. 2–3, §4 · p. 5

  • Takeaways & Limitations

    PersLoop lets users click a barcode interval from a 2D image or 3D point-cloud filtration to obtain its persistent 1-cycle.

    Source: §6 · p. 8

    A single switch in vertex order, the smallest possible lower-star filtration perturbation, can make the minimal cycle for [b, d) differ arbitrarily.

    Source: §4.1 · p. 5

Abstract

from arXiv · show

Persistence diagrams, which summarize the birth and death of homological features extracted from data, are employed as stable signatures for applications in image analysis and other areas. Besides simply considering the multiset of intervals included in a persistence diagram, some applications need to find representative cycles for the intervals. In this paper, we address the problem of computing these representative cycles, termed as persistent 1-cycles, for $\text{H}_1$-persistent homology with $\mathbb{Z}_2$ coefficients. The definition of persistent cycles is based on the interval module decomposition of persistence modules, which reveals the structure of persistent homology. After showing that the computation of the optimal persistent 1-cycles is NP-hard, we propose an alternative set of meaningful persistent 1-cycles that can be computed with an efficient polynomial time algorithm. We also inspect the stability issues of the optimal persistent 1-cycles and the persistent 1-cycles computed by our algorithm with the observation that the perturbations of both cannot be properly bounded. We design a software which applies our algorithm to various datasets. Experiments on 3D point clouds, mineral structures, and images show the effectiveness of our algorithm in practice.

1 Introduction

Persistence diagrams provide stable signatures, but some applications also need representative cycles for individual intervals. The paper defines persistent 1-cycles for H1 with Z2 coefficients, proves optimal computation is NP-hard, and proposes a more efficient polynomial-time alternative.

1 Introduction

  • Representative cycles matter because some applications need them in addition to the intervals in a persistence diagram.Prior approaches include birth-index representatives that do not account for what dies at the death index, integer programming, and an algorithm with worst-case complexity exponential in diagram cardinality.Source: §1 · p. 2
  • The paper defines persistent 1-cycles for H1-persistent homology with Z2 coefficients and shows that computing optimal cycles is NP-hard.It proposes meaningful alternatives computable in polynomial time, based directly on interval module structure.Source: §1 · p. 2
  • The paper studies representative persistent 1-cycles for H1-persistent homology with Z2 coefficients, finds optimal-cycle computation NP-hard, proposes polynomial-time alternatives, and reports unstable perturbations for minimal and algorithm-computed cycles.The algorithm generates tight persistent 1-cycles on 3D point clouds and 2D images using PersLoop.Source: §1 · pp. 2–3
  • The proposed polynomial-time algorithm is not worse than an optimal cycle-generating algorithm and is much more time-efficient.The passage gives no quantitative runtime comparison.Source: §1 · p. 3

2 Background

The background presents persistence modules as functors from an index category to vector spaces, induced by a filtration and homology. For finite complexes, these modules decompose uniquely into interval modules whose intervals form the persistence diagram.

2 Background

  • A persistence module is a functor from Z+ to vector spaces over Z2, mapping indices and their order relations to vector spaces and linear maps.The paper also identifies categories of simplicial complexes and simplicial maps as the setting for filtrations.Source: §2 · p. 3
  • A filtration adds one simplex at each step, and composing it with the homology functor yields the Hq-persistence module.At each index i, the module assigns Hq(K_i); inclusion induces the maps between homology spaces.Source: §2 · p. 3
  • For a finite complex, the Hq-persistence module has a unique decomposition into interval modules.An interval module is Z2 on its interval and zero elsewhere, with identity maps within the interval and zero maps otherwise.Source: §2 · p. 3
  • The intervals in that decomposition form the persistence diagram, also called the barcode.The paper denotes this set by D(PFq), and sometimes writes Dq(F) when referring to the filtration.Source: §2 · p. 3

3 Persistent basis and cycles

This section defines persistent bases and persistent cycles in terms of how cycle classes represent the interval-module decomposition. It characterizes when an indexed set of cycles forms such a basis and relates each persistent cycle to an interval module.

3 Persistent basis and cycles

  • An indexed set of q-cycles is a persistent q-basis when the persistence module decomposes into their associated interval modules and each cycle represents its interval throughout its lifespan.For each active index k, the corresponding interval module contains 0 and the cycle's homology class.Source: §3 · pp. 3–4
  • For a finite interval [b, d), a persistent q-cycle is born in K_b containing the birth simplex, is not a boundary in K_(d-1), and becomes a boundary in K_d.The paper states that its finite-interval definition matches earlier definitions.Source: §3 · p. 4
  • Theorem 1 characterizes a persistent q-basis by requiring the persistence module to decompose as the direct sum of its indexed interval modules.The proof tracks the cycle classes as simplices are added: positive simplices add a basis class, while negative simplices remove one.Source: §3 · p. 4
  • The proof establishes that the active cycle classes form a basis at each filtration index, so their interval modules reproduce the persistence module's maps.At a death index, the departing class becomes zero and the remaining classes span the homology group.Source: §3 · p. 4
  • Every persistent q-cycle for an interval can serve as a representative cycle for that interval's interval module.Conversely, a persistent-basis cycle must contain its birth simplex and, for a finite interval, its class is nonzero just before death and zero at death.Source: §3 · p. 4

4 Minimal persistent q-basis and their limitations

Minimal persistent 1-cycles are defined by minimizing cycle weight for each persistence interval, but computing an optimal cycle is NP-hard. Their representatives can also be unstable: even a single vertex-order swap can make the difference between minimal cycles arbitrary.

4 Minimal persistent q-basis and their limitations

  • A minimal persistent 1-cycle has the least weight among persistent cycles for its interval.The weight of a cycle is the sum of the weights of its edges.Source: §4 · p. 5
  • The least-edge persistent 1-cycle problem for a finite interval is NP-hard.It asks for a cycle born in K_b and becoming a boundary in K_d.Source: §4 · p. 5

4.1 Instability of minimal persistent 1-cycles

  • Minimal persistent 1-cycles are unstable even when comparing only their lengths under lower-star vertex-sequence perturbations.The analysis associates cycles from a corresponding insertion filtration to intervals in the lower-star filtration.Source: §4.1 · p. 5
  • A single swap of two vertices can make the difference between minimal cycles c1 and c2 arbitrary.For the constructed interval, switching the order of v1 and v2 changes the minimal cycle from c1 to c2.Source: §4.1 · p. 5, Figure 2 · p. 6

5 Computing meaningful persistent 1-cycles in polynomial time

The section develops a polynomial-time framework for computing meaningful persistent 1-cycles, using persistence-module structure to guide representatives. Its algorithms combine shortest cycles, with limited optimality guarantees and a faster option for selected intervals.

5 Computing meaningful persistent 1-cycles in polynomial time

  • The general framework has no guaranteed properties by itself, but it underlies an algorithm that assigns interval representatives from cycle relations in a maintained homology basis.At a negative simplex, the algorithm assigns the sum of related basis cycles to an interval and removes the cycle with greatest index; remaining cycles represent infinite intervals.Source: §5 · pp. 6–7
  • Algorithm 2 represents a finite interval by summing shortest cycles born at different indices, with each shortest cycle built using a shortest path in the 1-skeleton.The authors motivate the sum as a good representative because shortest cycles are usually good representatives of their homology classes.Source: §5 · p. 7
  • When the sum contains one component, Algorithm 2 returns a minimal persistent 1-cycle; this occurs for nearly all computed cycles in the larvae and nerve datasets.The authors report that these single-component cases occur quite frequently in their experiments.Source: §5 · p. 7
  • Algorithm 3 addresses the resource cost of computing tiny intervals regarded as noise when users care only about significantly large intervals.The interval-selection strategy limits shortest-cycle computations to a subset associated with the input interval.Source: §5 · p. 7
  • Algorithm 3 computes shortest cycles only at birth indices whose intervals contain the input interval, making it faster than Algorithm 2 in practice.The authors explain that a long input interval is usually contained in only a small subset of all intervals.Source: §5 · p. 7
  • For Algorithm 2 and Algorithm 3, no non-empty proper subset of component cycles sums to zero in homology at the associated interval’s death index.This is the stated minimality property of the computed persistent 1-cycles.Source: §5 · p. 7
  • Algorithm 2’s persistent 1-cycles are not stable under perturbation, and the example shows their difference can be arbitrary under the same insertion filtration.The construction allows the length of cycle c—and therefore the difference between the two possible representatives—to be arbitrary.Source: §5 · pp. 7–8

6 Results and experiments

PersLoop applies the algorithm to point clouds and images, letting users obtain cycles by selecting barcode intervals. Experiments show cycles that capture geometric structure, correspond to image membranes and hemorrhages, and reveal local and global structure in silicate glass.

6 Results and experiments

  • PersLoop plots a filtration's barcode, and users can click a bar to obtain its persistent 1-cycle.The software implements Algorithm 3 and accepts 2D images or 3D point clouds with a filtration.Source: §6 · p. 8

6.1 Persistent 1-cycles for 3D point clouds

  • The three point-cloud examples produce tight cycles that capture essential geometric features; 50 Botijo cycles took 0.3 seconds on a commodity laptop.The Botijo point cloud contained 10,000 points.Source: Figure 4 · p. 9, §6.1 · p. 9

6.2 Image segmentation and characterization using cubical complex

  • For image analysis, pixel values define a piecewise-linear function on a cubical complex, and its lower-star filtration is fed to the software.The complex connects horizontally or vertically adjacent pixel vertices and fills holes with squares.Source: §6.2 · p. 9
  • Image cycles correspond to nerve membranes and segment nerve regions; on retinal images, tight cycles form around dark hemorrhage blobs even with noisy input.The top 200 longest intervals on a Drosophila larvae image indicate proper segmentation; on nerve images, longer intervals tend to have longer cycles.Source: §6.2 · pp. 9–10, Figure 5 · p. 10

6.3 Hexagonal structure of crystalline solids

  • Cycles for medium-sized intervals match quartz's hexagonal structure, while longer-interval cycles span the larger lattice and reflect its long-range order.As the input point cloud grows, the larger cycles grow to span the entire lattice.Source: §6.3 · p. 10, Figure 6 · p. 11

A Proof of Theorem 2

The proof reduces MAX-2SAT to LST-PERS-CYC by encoding clause satisfaction in cycle length. It constructs a filtration interval whose minimum persistent cycle solves the MAX-2SAT instance, establishing NP-hardness.

A Proof of Theorem 2

  • The reduction starts from MAX-2SAT, which seeks a Boolean assignment satisfying the greatest number of clauses, and builds variable cylinders and clause cycles.The two ends of each variable cylinder represent the variable and its negation; clause cycles share designated edges with those end cycles.Source: A Proof of Theorem 2 · p. 13
  • A Boolean assignment satisfies k clauses if and only if the constructed cycle in [z] has 3MN + 3M − 2k edges.Thus the constructed cycle length encodes the number of satisfied clauses.Source: A Proof of Theorem 2 · p. 13
  • The proof decomposes z into simple cycles, attaches a cylinder from each to a quadrilateral, then glues those quadrilaterals into a complex with an outer cycle.Figure 7 illustrates a cylinder joining a dodecagon and quadrilateral, and the complex whose boundary combines three quadrilaterals with the outer cycle.Source: A Proof of Theorem 2 · p. 13, Figure 7 · p. 14
  • In the constructed filtration, e and the last triangle t pair so that [b, d) is a persistence interval containing z, which becomes a boundary at Kd.The proof identifies e as unpaired when t is added, so the persistence algorithm pairs them.Source: A Proof of Theorem 2 · p. 13
  • The polynomial-time reduction makes LST-PERS-CYC NP-hard by equating its minimum persistent cycle with the solution to MAX-2SAT.For the constructed interval, every persistent 1-cycle is homologous to z, so minimizing it in Kb is equivalent to minimizing the cycle in [z].Source: A Proof of Theorem 2 · pp. 13–14
Loading 1810.04807v2…