Persistence module

Last updated

A persistence module is a mathematical structure in persistent homology and topological data analysis that formally captures the persistence of topological features of an object across a range of scale parameters. A persistence module often consists of a collection of homology groups (or vector spaces if using field coefficients) corresponding to a filtration of topological spaces, and a collection of linear maps induced by the inclusions of the filtration. The concept of a persistence module was first introduced in 2005 as an application of graded modules over polynomial rings, thus importing well-developed algebraic ideas from classical commutative algebra theory to the setting of persistent homology. [1] Since then, persistence modules have been one of the primary algebraic structures studied in the field of applied topology. [2] [3] [4] [5] [6] [7]

Contents

Definition

Single Parameter Persistence Modules

Let be a partially ordered set (poset) and let be a field. The poset is sometimes called the indexing set. Then a persistence module is a functor from the poset category of to the category of vector spaces over and linear maps. [8] A persistence module indexed by a discrete poset such as the integers can be represented intuitively as a diagram of spaces:

To emphasize the indexing set being used, a persistence module indexed by is sometimes called a -persistence module, or simply a -module. [9]

One can alternatively use a set-theoretic definition of a persistence module that is equivalent to the categorical viewpoint: A persistence module is a pair where is a collection of -vector spaces and is a collection of linear maps where for each , such that for any (i.e., all the maps commute). [4]

Multiparameter Persistence Modules

In the case of a -module where is a single partially ordered set (e.g., , etc.), we say that is a single- or 1-parameter persistence module. However, if is instead a product of totally ordered sets, i.e., for some totally ordered sets , then by endowing with the product partial order given by only if for all , we can define a multiparameter persistence module indexed by .

In this case, a -persistence module is referred to as an -dimensional or -parameter persistence module, or simply a multiparameter or multidimensional module if the number of parameters is already clear from context. [10]

An example of a two-parameter persistence module indexed over the 5x5 grid, considered as a finite poset. Two-Parameter Persistence Module.png
An example of a two-parameter persistence module indexed over the 5x5 grid, considered as a finite poset.

Multidimensional persistence modules were first introduced in 2009 by Carlsson and Zomorodian. [11] Since then, there has been a significant amount of research into the theory and practice of working with multidimensional modules, since they provide more structure for studying the shape of data. [12] [13] [14] Namely, multiparameter modules can have greater density sensitivity and robustness to outliers than single-parameter modules, making them a potentially useful tool for data analysis. [15] [16] [17]

One downside of multiparameter persistence is its inherent complexity. This makes performing computations related to multiparameter persistence modules difficult. In the worst case, the computational complexity of multidimensional persistent homology is exponential. [18]

The most common way to measure the similarity of two multiparameter persistence modules is using the interleaving distance, which is an extension of the bottleneck distance. [19]

Examples

Homology Modules

When using homology with coefficients in a field, a homology group has the structure of a vector space. Therefore, given a filtration of spaces , by applying the homology functor at each index we obtain a persistence module for each called the (th-dimensional) homology module of . The vector spaces of the homology module can be defined index-wise as for all , and the linear maps are induced by the inclusion maps of . [1]

Homology modules are the most ubiquitous examples of persistence modules, as they encode information about the number and scale of topological features of an object (usually derived from building a filtration on a point cloud) in a purely algebraic structure, thus making understanding the shape of the data amenable to algebraic techniques, imported from well-developed areas of mathematics such as commutative algebra and representation theory. [5] [20] [21]

Interval Modules

A primary concern in the study of persistence modules is whether modules can be decomposed into "simpler pieces", roughly speaking. In particular, it is algebraically and computationally convenient if a persistence module can be expressed as a direct sum of smaller modules known as interval modules. [1]

Let be a nonempty subset of a poset . Then is an interval in if

Now given an interval we can define a persistence module index-wise as follows:

; .

The module is called an interval module. [9] [22]

Free Modules

Let . Then we can define a persistence module with respect to where the spaces are given by

, and the maps defined via .

Then is known as a free (persistence) module. [23]

One can also define a free module in terms of decomposition into interval modules. For each define the interval , sometimes called a "free interval." [9] Then a persistence module is a free module if there exists a multiset such that . [22] In other words, a module is a free module if it can be decomposed as a direct sum of free interval modules.

Properties

Finite Type Conditions

A persistence module indexed over is said to be of finite type if the following conditions hold for all :

  1. Each vector space is finite-dimensional.
  2. There exists an integer such that the map is an isomorphism for all .

If satisfies the first condition, then is commonly said to be pointwise finite-dimensional (p.f.d.). [24] [25] [26] The notion of pointwise finite-dimensionality immediately extends to arbitrary indexing sets.

The definition of finite type can also be adapted to continuous indexing sets. Namely, a module indexed over is of finite type if is p.f.d., and contains a finite number of unique vector spaces. [27] Formally speaking, this requires that for all but a finite number of points there is a neighborhood of such that for all , and also that there is some such that for all . [4] A module satisfying only the former property is sometimes labeled essentially discrete, whereas a module satisfying both properties is known as essentially finite. [28] [23] [29]

An -persistence module is said to be semicontinuous if for any and any sufficiently close to , the map is an isomorphism. Note that this condition is redundant if the other finite type conditions above are satisfied, so it is not typically included in the definition, but is relevant in certain circumstances. [4]

Structure Theorem

One of the primary goals in the study of persistence modules is to classify modules according to their decomposability into interval modules. A persistence module that admits a decomposition as a direct sum of interval modules is often simply called "interval decomposable." One of the primary results in this direction is that any p.f.d. persistence module indexed over a totally ordered set is interval decomposable. This is sometimes referred to as the "structure theorem for persistence modules." [24]

An example of a 2-D persistence module in the plane with its interval decompositions. Interval Decomposable 2-D Persistence Module.png
An example of a 2-D persistence module in the plane with its interval decompositions.

The case when is finite is a straightforward application of the structure theorem for finitely generated modules over a principal ideal domain. For modules indexed over , the first known proof of the structure theorem is due to Webb. [30] The theorem was extended to the case of (or any totally ordered set containing a countable subset that is dense in with the order topology) by Crawley-Boevey in 2015. [31] The generalized version of the structure theorem, i.e., for p.f.d. modules indexed over arbitrary totally ordered sets, was established by Botnan and Crawley-Boevey in 2019. [32]

Related Research Articles

<span class="mw-page-title-main">Abelian group</span> Commutative group (mathematics)

In mathematics, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on the order in which they are written. That is, the group operation is commutative. With addition as an operation, the integers and the real numbers form abelian groups, and the concept of an abelian group may be viewed as a generalization of these examples. Abelian groups are named after early 19th century mathematician Niels Henrik Abel.

<span class="mw-page-title-main">Partially ordered set</span> Mathematical set with an ordering

In mathematics, especially order theory, a partial order on a set is an arrangement such that, for certain pairs of elements, one precedes the other. The word partial is used to indicate that not every pair of elements needs to be comparable; that is, there may be pairs for which neither element precedes the other. Partial orders thus generalize total orders, in which every pair is comparable.

<span class="mw-page-title-main">Ring (mathematics)</span> Algebraic structure with addition and multiplication

In mathematics, rings are algebraic structures that generalize fields: multiplication need not be commutative and multiplicative inverses need not exist. In other words, a ring is a set equipped with two binary operations satisfying properties analogous to those of addition and multiplication of integers. Ring elements may be numbers such as integers or complex numbers, but they may also be non-numerical objects such as polynomials, square matrices, functions, and power series.

In mathematics, homology is a general way of associating a sequence of algebraic objects, such as abelian groups or modules, with other mathematical objects such as topological spaces. Homology groups were originally defined in algebraic topology. Similar constructions are available in a wide variety of other contexts, such as abstract algebra, groups, Lie algebras, Galois theory, and algebraic geometry.

In mathematics, specifically in homology theory and algebraic topology, cohomology is a general term for a sequence of abelian groups, usually one associated with a topological space, often defined from a cochain complex. Cohomology can be viewed as a method of assigning richer algebraic invariants to a space than homology. Some versions of cohomology arise by dualizing the construction of homology. In other words, cochains are functions on the group of chains in homology theory.

A CW complex is a kind of a topological space that is particularly important in algebraic topology. It was introduced by J. H. C. Whitehead to meet the needs of homotopy theory. This class of spaces is broader and has some better categorical properties than simplicial complexes, but still retains a combinatorial nature that allows for computation. The C stands for "closure-finite", and the W for "weak" topology.

In mathematics, Kähler differentials provide an adaptation of differential forms to arbitrary commutative rings or schemes. The notion was introduced by Erich Kähler in the 1930s. It was adopted as standard in commutative algebra and algebraic geometry somewhat later, once the need was felt to adapt methods from calculus and geometry over the complex numbers to contexts where such methods are not available.

In mathematics, the Lasker–Noether theorem states that every Noetherian ring is a Lasker ring, which means that every ideal can be decomposed as an intersection, called primary decomposition, of finitely many primary ideals. The theorem was first proven by Emanuel Lasker (1905) for the special case of polynomial rings and convergent power series rings, and was proven in its full generality by Emmy Noether (1921).

In mathematics, Hochschild homology (and cohomology) is a homology theory for associative algebras over rings. There is also a theory for Hochschild homology of certain functors. Hochschild cohomology was introduced by Gerhard Hochschild (1945) for algebras over a field, and extended to algebras over more general rings by Henri Cartan and Samuel Eilenberg (1956).

Size functions are shape descriptors, in a geometrical/topological sense. They are functions from the half-plane to the natural numbers, counting certain connected components of a topological space. They are used in pattern recognition and topology.

In applied mathematics, topological data analysis (TDA) is an approach to the analysis of datasets using techniques from topology. Extraction of information from datasets that are high-dimensional, incomplete and noisy is generally challenging. TDA provides a general framework to analyze such data in a manner that is insensitive to the particular metric chosen and provides dimensionality reduction and robustness to noise. Beyond this, it inherits functoriality, a fundamental concept of modern mathematics, from its topological nature, which allows it to adapt to new mathematical tools.

In mathematics, the Farrell–Jones conjecture, named after F. Thomas Farrell and Lowell E. Jones, states that certain assembly maps are isomorphisms. These maps are given as certain homomorphisms.

Persistent homology is a method for computing topological features of a space at different spatial resolutions. More persistent features are detected over a wide range of spatial scales and are deemed more likely to represent true features of the underlying space rather than artifacts of sampling, noise, or particular choice of parameters.

In algebraic geometry, a mixed Hodge structure is an algebraic structure containing information about the cohomology of general algebraic varieties. It is a generalization of a Hodge structure, which is used to study smooth projective varieties.

The degree-Rips bifiltration is a simplicial filtration used in topological data analysis for analyzing the shape of point cloud data. It is a multiparameter extension of the Vietoris–Rips filtration that possesses greater stability to data outliers than single-parameter filtrations, and which is more amenable to practical computation than other multiparameter constructions. Introduced in 2015 by Lesnick and Wright, the degree-Rips bifiltration is a parameter-free and density-sensitive vehicle for performing persistent homology computations on point cloud data.

<span class="mw-page-title-main">Offset filtration</span>

The offset filtration is a growing sequence of metric balls used to detect the size and scale of topological features of a data set. The offset filtration commonly arises in persistent homology and the field of topological data analysis. Utilizing a union of balls to approximate the shape of geometric objects was first suggested by Frosini in 1992 in the context of submanifolds of Euclidean space. The construction was independently explored by Robins in 1998, and expanded to considering the collection of offsets indexed over a series of increasing scale parameters, in order to observe the stability of topological features with respect to attractors. Homological persistence as introduced in these papers by Frosini and Robins was subsequently formalized by Edelsbrunner et al. in their seminal 2002 paper Topological Persistence and Simplification. Since then, the offset filtration has become a primary example in the study of computational topology and data analysis.

<span class="mw-page-title-main">Multicover bifiltration</span>

The multicover bifiltration is a two-parameter sequence of nested topological spaces derived from the covering of a finite set in a metric space by growing metric balls. It is a multidimensional extension of the offset filtration that captures density information about the underlying data set by filtering the points of the offsets at each index according to how many balls cover each point. The multicover bifiltration has been an object of study within multidimensional persistent homology and topological data analysis.

In topological data analysis, the Vietoris-Rips filtration is the collection of nested Vietoris-Rips complexes on a metric space created by taking the sequence of Vietoris-Rips complexes over an increasing scale parameter. Often, the Vietoris-Rips filtration is used to create a discrete, simplicial model on point cloud data embedded in an ambient metric space. The Vietoris-Rips filtration is a multiscale extension of the Vietoris-Rips complex that enables researchers to detect and track the persistence of topological features, over a range of parameters, by way of computing the persistent homology of the entire filtration.

In persistent homology, a persistent homology group is a multiscale analog of a homology group that captures information about the evolution of topological features across a filtration of spaces. While the ordinary homology group represents nontrivial homology classes of an individual topological space, the persistent homology group tracks only those classes that remain nontrivial across multiple parameters in the underlying filtration. Analogous to the ordinary Betti number, the ranks of the persistent homology groups are known as the persistent Betti numbers. Persistent homology groups were first introduced by Herbert Edelsbrunner, David Letscher, and Afra Zomorodian in a 2002 paper Topological Persistence and Simplification, one of the foundational papers in the fields of persistent homology and topological data analysis, based largely on the persistence barcodes and the persistence algorithm, that were first described by Serguei Barannikov in the 1994 paper. Since then, the study of persistent homology groups has led to applications in data science, machine learning, materials science, biology, and economics.

In topological data analysis, a persistence barcode, sometimes shortened to barcode, is an algebraic invariant of a persistence module that characterizes the stability of topological features throughout a growing family of spaces. Formally, a persistence barcode consists of a multiset of intervals in the extended real line, where the length of each interval corresponds to the lifetime of a topological feature in a filtration, usually built on a point cloud, a graph, a function, or, more generally, a simplicial complex or a chain complex. Generally, longer intervals in a barcode correspond to more robust features, whereas shorter intervals are more likely to be noise in the data. A persistence barcode is a complete invariant that captures all the topological information in a filtration. In algebraic topology, the persistence barcodes were first introduced by Sergey Barannikov in 1994 as the "canonical forms" invariants consisting of a multiset of line segments with ends on two parallel lines, and later, in geometry processing, by Gunnar Carlsson et al. in 2004.

References

  1. 1 2 3 Zomorodian, Afra; Carlsson, Gunnar (2005). "Computing Persistent Homology". Discrete & Computational Geometry. 33 (2): 249–274. doi: 10.1007/s00454-004-1146-y . ISSN   0179-5376.
  2. ↑ The structure and stability of persistence modules. Frédéric Chazal, Vin De Silva, Marc Glisse, Steve Y. Oudot. Switzerland. 2016. ISBN   978-3-319-42545-0. OCLC   960458101.{{cite book}}: CS1 maint: location missing publisher (link) CS1 maint: others (link)
  3. ↑ Oudot, Steve Y. (2015). Persistence theory : from quiver representations to data analysis. Providence, Rhode Island. ISBN   978-1-4704-2545-6. OCLC   918149730.{{cite book}}: CS1 maint: location missing publisher (link)
  4. 1 2 3 4 Polterovich, Leonid (2020). Topological persistence in geometry and analysis. Daniel Rosen, Karina Samvelyan, Jun Zhang. Providence, Rhode Island. ISBN   978-1-4704-5495-1. OCLC   1142009348.{{cite book}}: CS1 maint: location missing publisher (link)
  5. 1 2 Schenck, Hal (2022). Algebraic foundations for applied topology and data analysis. Cham. ISBN   978-3-031-06664-1. OCLC   1351750760.{{cite book}}: CS1 maint: location missing publisher (link)
  6. ↑ Dey, Tamal K. (2022). Computational topology for data analysis. Yusu Wang. Cambridge, United Kingdom. ISBN   978-1-009-09995-0. OCLC   1281786176.{{cite book}}: CS1 maint: location missing publisher (link)
  7. ↑ Rabadan, Raul; Blumberg, Andrew J. (2019). Topological Data Analysis for Genomics and Evolution: Topology in Biology. Cambridge: Cambridge University Press. doi:10.1017/9781316671665. ISBN   978-1-107-15954-9. S2CID   242498045.
  8. ↑ Bubenik, Peter; Scott, Jonathan A. (2014-04-01). "Categorification of Persistent Homology". Discrete & Computational Geometry. 51 (3): 600–627. arXiv: 1205.3669 . doi:10.1007/s00454-014-9573-x. ISSN   1432-0444. S2CID   254027425.
  9. 1 2 3 Bakke Bjerkevik, Håvard (2021). "On the Stability of Interval Decomposable Persistence Modules". Discrete & Computational Geometry. 66 (1): 92–121. doi: 10.1007/s00454-021-00298-0 . ISSN   0179-5376. S2CID   243797357.
  10. ↑ Botnan, Magnus Bakke; Lesnick, Michael (2022-03-27). "An Introduction to Multiparameter Persistence". arXiv: 2203.14289 [math.AT].
  11. ↑ Carlsson, Gunnar; Zomorodian, Afra (2009-07-01). "The Theory of Multidimensional Persistence". Discrete & Computational Geometry. 42 (1): 71–93. doi: 10.1007/s00454-009-9176-0 . ISSN   1432-0444.
  12. ↑ Cerri, Andrea; Landi, Claudia (2013). "The Persistence Space in Multidimensional Persistent Homology". In Gonzalez-Diaz, Rocio; Jimenez, Maria-Jose; Medrano, Belen (eds.). Discrete Geometry for Computer Imagery. Lecture Notes in Computer Science. Vol. 7749. Berlin, Heidelberg: Springer. pp. 180–191. doi: 10.1007/978-3-642-37067-0_16 . ISBN   978-3-642-37067-0.
  13. ↑ Cagliari, F.; Di Fabio, B.; Ferri, M. (2008-07-28). "One-Dimensional Reduction of Multidimensional Persistent Homology". arXiv: math/0702713 .
  14. ↑ Allili, Madjid; Kaczynski, Tomasz; Landi, Claudia (2017-01-01). "Reducing complexes in multidimensional persistent homology theory". Journal of Symbolic Computation. Algorithms and Software for Computational Topology. 78: 61–75. doi:10.1016/j.jsc.2015.11.020. hdl: 11380/1123249 . ISSN   0747-7171. S2CID   14185228.
  15. ↑ Blumberg, Andrew J.; Lesnick, Michael (2022-10-17). "Stability of 2-Parameter Persistent Homology". Foundations of Computational Mathematics. arXiv: 2010.09628 . doi:10.1007/s10208-022-09576-6. ISSN   1615-3383. S2CID   224705357.
  16. ↑ Cerri, Andrea; Fabio, Barbara Di; Ferri, Massimo; Frosini, Patrizio; Landi, Claudia (2013). "Betti numbers in multidimensional persistent homology are stable functions". Mathematical Methods in the Applied Sciences. 36 (12): 1543–1557. Bibcode:2013MMAS...36.1543C. doi:10.1002/mma.2704. S2CID   9938133.
  17. ↑ Cerri, Andrea; Di Fabio, Barbara; Ferri, Massimo; Frosini, Patrizio; Landi, Claudia (2009-08-01). "Multidimensional persistent homology is stable". arXiv: 0908.0064 [math.AT].
  18. ↑ Skryzalin, Jacek; Vongmasa, Pawin (2017). "The Computational Complexity of Multidimensional Persistence". Proposed Journal Article, Unpublished. 2017. OSTI   1429696.
  19. ↑ Lesnick, Michael (2015). "The Theory of the Interleaving Distance on Multidimensional Persistence Modules". Foundations of Computational Mathematics. 15 (3): 613–650. arXiv: 1106.5305 . doi:10.1007/s10208-015-9255-y. ISSN   1615-3375. S2CID   254158297.
  20. ↑ Carlsson, Gunnar (2009). "Topology and data". Bulletin of the American Mathematical Society. 46 (2): 255–308. doi: 10.1090/S0273-0979-09-01249-X . ISSN   0273-0979.
  21. ↑ Chazal, Frédéric; Michel, Bertrand (2021). "An Introduction to Topological Data Analysis: Fundamental and Practical Aspects for Data Scientists". Frontiers in Artificial Intelligence. 4: 667963. doi: 10.3389/frai.2021.667963 . ISSN   2624-8212. PMC   8511823 . PMID   34661095.
  22. 1 2 Botnan, Magnus; Lesnick, Michael (2018-10-18). "Algebraic stability of zigzag persistence modules". Algebraic & Geometric Topology. 18 (6): 3133–3204. arXiv: 1604.00655 . doi:10.2140/agt.2018.18.3133. ISSN   1472-2739. S2CID   14072359.
  23. 1 2 Lesnick, Michael (2022). "Lecture Notes for AMAT 840: Multiparameter Persistence" (PDF). University at Albany, SUNY.
  24. 1 2 Botnan, Magnus Bakke; Crawley-Boevey, William (2019-10-04). "Decomposition of persistence modules". arXiv: 1811.08946 [math.RT].
  25. ↑ Schmahl, Maximilian (2022). "Structure of semi-continuous $q$-tame persistence modules". Homology, Homotopy and Applications. 24 (1): 117–128. arXiv: 2008.09493 . doi:10.4310/HHA.2022.v24.n1.a6. ISSN   1532-0081. S2CID   221246111.
  26. ↑ Hanson, Eric J.; Rock, Job D. (2020-07-17). "Decomposition of Pointwise Finite-Dimensional S^1 Persistence Modules". arXiv: 2006.13793 [math.RT].
  27. ↑ Carlsson, Gunnar; Zomorodian, Afra; Collins, Anne; Guibas, Leonidas (2004-07-08). "Persistence barcodes for shapes". Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing. Nice France: ACM. pp. 124–135. doi:10.1145/1057432.1057449. ISBN   978-3-905673-13-5. S2CID   456712.
  28. ↑ Lesnick, Michael (2012-06-06). "Multidimensional Interleavings and Applications to Topological Inference". arXiv: 1206.1365 [math.AT].
  29. ↑ "3. Mathematical Preliminaries — RIVET 1.0 documentation". rivet.readthedocs.io. Retrieved 2023-02-27.
  30. ↑ Webb, Cary (1985). "Decomposition of graded modules". Proceedings of the American Mathematical Society. 94 (4): 565–571. doi: 10.1090/S0002-9939-1985-0792261-6 . ISSN   0002-9939. S2CID   115146035.
  31. ↑ Crawley-Boevey, William (2015-06-01). "Decomposition of pointwise finite-dimensional persistence modules". Journal of Algebra and Its Applications. 14 (5): 1550066. arXiv: 1210.0819 . doi:10.1142/S0219498815500668. ISSN   0219-4988. S2CID   119635797.
  32. ↑ Botnan, Magnus; Crawley-Boevey, William (2020). "Decomposition of persistence modules". Proceedings of the American Mathematical Society. 148 (11): 4581–4596. arXiv: 1811.08946 . doi:10.1090/proc/14790. ISSN   0002-9939. S2CID   119711245.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.