Multicover bifiltration

Last updated
The 2- and 3-fold covers of 7 points in the plane with respect to a particular scale parameter. Example of the Multicover Bifiltration.webp
The 2- and 3-fold covers of 7 points in the plane with respect to a particular scale parameter.

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. [1] The multicover bifiltration has been an object of study within multidimensional persistent homology and topological data analysis. [2] [3] [4] [5] [6] [7]

Contents

Definition

Following the notation of Corbet et al. (2022), given a finite set , the multicover bifiltration on is a two-parameter filtration indexed by defined index-wise as , where denotes the non-negative integers. [8] Note that when is fixed we recover the Offset Filtration.

Properties

The multicover bifiltration admits a topologically equivalent polytopal model of polynomial size, called the "rhomboid bifiltration." [8] The rhomboid bifiltration is an extension of the rhomboid tiling introduced by Edelsbrunner and Osang in 2021 for computing the persistent homology of the multicover bifiltration along one axis of the indexing set. [2] The rhomboid bifiltration on a set of points in a Euclidean space can be computed in polynomial time. [8]

An example of the rhomboid tiling on a set of five points. Rhomboid Tiling.webp
An example of the rhomboid tiling on a set of five points.

The multicover bifiltration is also topologically equivalent to a multicover nerve construction due to Sheehy called the subdivision-Čech bifiltration, which considers the barycentric subdivision on the nerve of the offsets. [9] In particular, the subdivision-Čech and multicover bifiltrations are weakly equivalent, and hence have isomorphic homology modules in all dimensions. [4] However, the subdivision-Čech bifiltration has an exponential number of simplices in the size of the data set, and hence is not amenable to efficient direct computations. [8]

Related Research Articles

Carathéodory's theorem is a theorem in convex geometry. It states that if a point lies in the convex hull of a set , then can be written as the convex combination of at most points in . More sharply, can be written as the convex combination of at most extremal points in , as non-extremal points can be removed from without changing the membership of in the convex hull.

<span class="mw-page-title-main">Thomas Callister Hales</span> American mathematician

Thomas Callister Hales is an American mathematician working in the areas of representation theory, discrete geometry, and formal verification. In representation theory he is known for his work on the Langlands program and the proof of the fundamental lemma over the group Sp(4). In discrete geometry, he settled the Kepler conjecture on the density of sphere packings and the honeycomb conjecture. In 2014, he announced the completion of the Flyspeck Project, which formally verified the correctness of his proof of the Kepler conjecture.

<span class="mw-page-title-main">Vietoris–Rips complex</span> Topological space formed from distances

In topology, the Vietoris–Rips complex, also called the Vietoris complex or Rips complex, is a way of forming a topological space from distances in a set of points. It is an abstract simplicial complex that can be defined from any metric space M and distance δ by forming a simplex for every finite set of points that has diameter at most δ. That is, it is a family of finite subsets of M, in which we think of a subset of k points as forming a (k − 1)-dimensional simplex (an edge for two points, a triangle for three points, a tetrahedron for four points, etc.); if a finite set S has the property that the distance between every pair of points in S is at most δ, then we include S as a simplex in the complex.

Given a size pair where is a manifold of dimension and is an arbitrary real continuous function defined on it, the -th size functor, with , denoted by , is the functor in , where is the category of ordered real numbers, and is the category of Abelian groups, defined in the following way. For , setting , , equal to the inclusion from into , and equal to the morphism in from to ,

Discrete Morse theory is a combinatorial adaptation of Morse theory developed by Robin Forman. The theory has various practical applications in diverse fields of applied mathematics and computer science, such as configuration spaces, homology computation, denoising, mesh compression, and topological data analysis.

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.

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.

<span class="mw-page-title-main">Topological graph</span>

In mathematics, a topological graph is a representation of a graph in the plane, where the vertices of the graph are represented by distinct points and the edges by Jordan arcs joining the corresponding pairs of points. The points representing the vertices of a graph and the arcs representing its edges are called the vertices and the edges of the topological graph. It is usually assumed that any two edges of a topological graph cross a finite number of times, no edge passes through a vertex different from its endpoints, and no two edges touch each other. A topological graph is also called a drawing of a graph.

<span class="mw-page-title-main">Cubical complex</span>

In mathematics, a cubical complex is a set composed of points, line segments, squares, cubes, and their n-dimensional counterparts. They are used analogously to simplicial complexes and CW complexes in the computation of the homology of topological spaces.

In algebraic topology, homological connectivity is a property describing a topological space based on its homology groups.

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.

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 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. Since then, persistence modules have been one of the primary algebraic structures studied in the field of applied topology.

In topological data analysis, a subdivision bifiltration is a collection of filtered simplicial complexes, typically built upon a set of data points in a metric space, that captures shape and density information about the underlying data set. The subdivision bifiltration relies on a natural filtration of the barycentric subdivision of a simplicial complex by flags of minimum dimension, which encodes density information about the metric space upon which the complex is built. The subdivision bifiltration was first introduced by Donald Sheehy in 2011 as part of his doctoral thesis as a discrete model of the multicover bifiltration, a continuous construction whose underlying framework dates back to the 1970s. In particular, Sheehy applied the construction to both the Vietoris-Rips and Čech filtrations, two common objects in the field of topological data analysis. Whereas single parameter filtrations are not robust with respect to outliers in the data, the subdivision-Rips and -Cech bifiltrations satisfy several desirable stability properties.

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. It is named after Leopold Vietoris and Eliyahu Rips.

In topological data analysis, the interleaving distance is a measure of similarity between persistence modules, a common object of study in topological data analysis and persistent homology. The interleaving distance was first introduced by Frédéric Chazal et al. in 2009. since then, it and its generalizations have been a central consideration in the study of applied algebraic topology and topological data analysis.

In persistent homology, a persistent Betti number is a multiscale analog of a Betti number that tracks the number of topological features that persist over multiple scale parameters in a filtration. Whereas the classical Betti number equals the rank of the homology group, the persistent Betti number is the rank of the persistent homology group. The concept of a persistent Betti number was introduced by Herbert Edelsbrunner, David Letscher, and Afra Zomorodian in the 2002 paper Topological Persistence and Simplification, one of the seminal papers in the field of persistent homology and topological data analysis. Applications of the persistent Betti number appear in a variety of fields including data analysis, machine learning, and physics.

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 associated with a filtered chain complex or 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.

In discrete mathematics and theoretical computer science, the flip distance between two triangulations of the same point set is the number of flips required to transform one triangulation into another. A flip removes an edge between two triangles in the triangulation and then adds the other diagonal in the edge's enclosing quadrilateral, forming a different triangulation of the same point set.

References

  1. Botnan, Magnus Bakke; Lesnick, Michael (2022). "An Introduction to Multiparameter Persistence". p. 26. arXiv: 2203.14289 [math.AT].
  2. 1 2 Edelsbrunner, Herbert; Osang, Georg (2021). "The Multi-Cover Persistence of Euclidean Balls". Discrete & Computational Geometry. 65 (4): 1296–1313. doi:10.1007/s00454-021-00281-9. ISSN   0179-5376. PMC   8550220 . PMID   34720303.
  3. Corbet, René; Kerber, Michael; Lesnick, Michael; Osang, Georg (2023-02-20). "Computing the Multicover Bifiltration". Discrete & Computational Geometry. arXiv: 2103.07823 . doi:10.1007/s00454-022-00476-8. ISSN   0179-5376.
  4. 1 2 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-3375. S2CID   224705357.
  5. Botnan, Magnus B.; Hirsch, Christian (2022-12-22). "On the consistency and asymptotic normality of multiparameter persistent Betti numbers". Journal of Applied and Computational Topology. arXiv: 2109.05513 . doi:10.1007/s41468-022-00110-9. ISSN   2367-1726. S2CID   237491663.
  6. Kerber, Michael (2022-07-29). "Multi-Parameter Persistent Homology is Practical (Extended Abstract)".{{cite journal}}: Cite journal requires |journal= (help)
  7. Corbet, Rene (2020). "Improvements to the Pipeline of Multiparameter Persistence".{{cite journal}}: Cite journal requires |journal= (help)
  8. 1 2 3 4 Corbet, René; Kerber, Michael; Lesnick, Michael; Osang, Georg (2023-02-20). "Computing the Multicover Bifiltration". Discrete & Computational Geometry. arXiv: 2103.07823 . doi:10.1007/s00454-022-00476-8. ISSN   0179-5376.
  9. D. R. Sheehy, “A multicover nerve for geometric inference,” in CCCG: Canadian conference in computational geometry, 2012.