Source-linked AI summary
Zigzag Persistence
Gunnar Carlsson, Vin de Silva
TL;DR
The paper addresses limitations of persistent homology when studying families of spaces whose maps are not uniformly directed. It introduces zigzag persistence, develops its decomposition and algorithmic foundations through quiver theory, and applies the resulting tools to topological settings. The authors report that the Diamond Principle supports isomorphisms among persistence invariants and resolves an open conjecture concerning extended persistence.
Problem
Persistent homology does not cover several situations involving families of spaces or point-cloud data, including diagrams whose linking maps have arbitrary directions.
Method
The paper develops zigzag persistence using quiver-representation theory, including module decompositions, right-filtrations, algorithms, and the Diamond Principle.
Results
The Diamond Principle is used to establish isomorphisms between several persistence-invariant classes and to resolve an open conjecture concerning extended persistence.
Takeaways & Limitations
Zigzag persistence provides a barcode-based framework for studying topological features across families that standard persistence cannot address.
Takeaways & Limitations
The paper omits an algorithm for computing zigzag persistence in a homological setting.
Abstract
from arXiv · showhide
We describe a new methodology for studying persistence of topological features across a family of spaces or point-cloud data sets, called zigzag persistence. Building on classical results about quiver representations, zigzag persistence generalises the highly successful theory of persistent homology and addresses several situations which are not covered by that theory. In this paper we develop theoretical and algorithmic foundations with a view towards applications in topological statistics.
1. Introduction
Zigzag persistence extends persistent homology to families of spaces or point-cloud data with maps whose directions may vary. The paper develops its mathematical, algorithmic, and topological foundations, including barcode decompositions and the Diamond Principle.
- Zigzag persistence studies topological features across families of spaces or point-cloud data sets.
- Unlike ordinary persistence, zigzag diagrams allow each adjacent map to point in either direction.
- The paper develops theoretical foundations, algorithms, and applications for computing and using zigzag persistence.
- Diamond Principle: The Diamond Principle provides a calculational tool for comparing zigzag barcodes of natural diagrams built from simplicial-complex sequences.
- Persistence: Persistent homology produces barcodes with stability and computational advantages but depends crucially on nested families of complexes.
- Zigzag persistence: Zigzag persistence seeks a barcode classification for diagrams with arrows in either direction, using quiver-representation theory.
- Applied topology: The framework addresses applications involving varying density parameters, landmark sets, and sampled point clouds, where natural nested families may not exist.
2. Zigzag Diagrams of Vector Spaces
Zigzag modules are finite-dimensional vector-space diagrams whose adjacent maps may point forward or backward. Their decomposition into interval modules provides a barcode-like invariant, but features must be distinguished from arbitrary submodules.
- Zigzag modules: A zigzag module is a sequence of finite-dimensional vector spaces and linear maps with an orientation type recording each forward or backward map.Persistence modules are the special case in which all maps point forward.
- Zigzag modules: Zigzag modules are representations of an oriented path graph, connecting the framework to quiver representation theory.Gabriel’s theorem gives the relevant classification for these oriented A_n graphs.
- Interval decomposition: The interval multiset is an isomorphism invariant because Krull–Remak–Schmidt makes indecomposable summands unique up to reordering.If two Remak decompositions have M and N summands, then M = N and the summands agree after a permutation.
- Interval decomposition: Every zigzag module decomposes as a direct sum of interval modules I(b, d), which are precisely the indecomposable modules.Interval modules contain copies of F on indices from b through d, with identity maps between adjacent copies and zero maps otherwise.
- Foundations and algorithms: The paper develops a stand-alone proof of interval decomposition to support algorithms that compute interval summands and rigorously characterize their output.The technical development uses decompositions and right-filtrations as foundations for algorithmic zigzag persistence.
- Features and restrictions: A submodule is not necessarily a summand: a module can contain a submodule isomorphic to I(1, 3) without containing it as a complementary feature.Accordingly, the paper defines features using summands, not merely submodules; restricted features correspond to intervals in the full persistence multiset that contain the restricted interval.
3. From Zigzag Modules to Filtrations
The right-filtration encodes the information in a zigzag module that survives to the final time, while the birth-time index records when each filtration level originated. For streamlined modules, this filtration preserves structural information and supports interval decompositions.
- The right-filtration operator: The right-filtration is built iteratively from left to right, with its essential information stored on the rightmost vector space.Forward maps apply images to the filtration, while backward maps prepend zero and use inverse images.
- The right-filtration operator: Each filtration subquotient records information associated with an earliest vector space in the zigzag sequence.For a forward map, surviving vectors and vectors appearing at the final time occupy distinct subquotients.
- Birth-time indices: The birth-time index assigns the birth time of each filtration subquotient and is updated by appending n + 1 for f and prepending n + 1 for g.For length 3, the indices are b(ff) = (1, 2, 3), b(fg) = (3, 1, 2), b(gf) = (2, 1, 3), and b(gg) = (3, 2, 1).
- Interval filtrations: The filtration and birth-time index together encode surviving information and its age, while distinguishing intervals that reach the final time.They do not distinguish intervals ending before the final time because the final vector space is zero for those intervals.
- Decompositions: Filtered vector spaces decompose into interval filtrations J(i, n), with multiplicity determined by the dimension of the corresponding successive subquotient.For streamlined modules, decompositions of the right-filtration induce unique compatible decompositions of the zigzag module.
4. The Interval Decomposition Algorithm
The interval decomposition algorithm first separates a zigzag module into streamlined summands and then decomposes those summands into interval modules. It provides an abstract procedure and a matrix-based implementation using elementary row and column operations.
- The matrix algorithm: For matrix-presented modules, the algorithm returns the interval decomposition from the matrices representing the forward and backward maps.The input spaces are F^ai and the maps are supplied as matrices Mi or Ni.
- The interval decomposition theorem: The decomposition theorem states that every τ-module is a direct sum of interval modules, with the multiplicity of each interval explicitly determined.The algorithmic development is based on this constructive decomposition result.
- The abstract algorithm: The strategy proceeds from left to right, removing streamlined summands and using filtration dimensions to determine their interval factors.At each stage, the filtration, birth-time index, and dimensions are computed for the truncated module.
- The abstract algorithm: The abstract algorithm computes right-filtrations, birth-time indices, and filtration dimensions for successive truncations, with separate cases for forward and backward maps.The terminal step reads the interval multiplicities from the final filtration dimensions.
- The matrix algorithm: Matrix computation implements basis changes through elementary row and column operations while maintaining the effects on adjacent maps.Row operations are applied to forward-map matrices and column operations to backward-map matrices, with corresponding operations on neighboring matrices.
5. Further Algebraic Techniques
This section develops localization and diamond principles for zigzag persistence, using filtrations to recover intervals and exact diamonds to relate persistence modules. It concludes by positioning the theory as an algorithmic extension of persistent homology while identifying missing homological algorithms and undeveloped applications.
- Localization at an index: Intervals containing index k can be determined from paired right- and left-filtrations on Vk, without computing all of Pers(V).The localization theorem identifies each interval [bi, dj] containing k through bifiltration subquotients.
- Localization at an index: The localization theorem equates interval multiplicities with dimensions of subquotients formed from intersections of the two filtrations.Equivalently, cij = dim((Ri ∩Lj)/((Ri−1 ∩Lj) + (Ri ∩Lj−1))).
- The Diamond Principle: Under an exact middle diamond, persistence intervals in Pers(V+) and Pers(V−) admit a partial matching, while [k, k] intervals remain unmatched.The matching shifts intervals adjacent to k and preserves all other interval types.
- The Diamond Principle: Removing index k leaves equal restricted persistence multisets for V+ and V−.The unmatched [k, k] intervals are the only exceptions to the restricted equality.
- The Strong Diamond Principle: The Strong Diamond Principle gives a complete bijection between Pers(H∗(X+)) and Pers(H∗(X−)), including a homological-dimension shift for [k, k] intervals.The [k, k] interval in Hℓ+1(X+) matches the corresponding interval in Hℓ(X−); other cases preserve homological dimension and follow the stated endpoint rules.
- Concluding Remarks: The paper establishes mathematical and algorithmic foundations for zigzag persistence, but omits a homological computation algorithm and leaves proposed applications undeveloped.The authors distinguish their vector-space algorithm from the missing homological algorithm and defer applications to future work.