Topological data analysis

Intuition

The premise underlying TDA is that shape matters. Real data in high dimensions is nearly always sparse, and tends to have relevant low dimensional features. One task of TDA is to provide a precise characterization of this fact. An illustrative example is a simple predator-prey system governed by the Lotka–Volterra equations. One can easily observe that the trajectory of the system forms a closed circle in state space. TDA provides tools to detect and quantify such recurrent motion.

Many algorithms for data analysis, including those used in TDA, require the choice of various parameters. Without prior domain knowledge, the correct collection of parameters for a data set is difficult to choose. The main insight of [persistent homology] is that we can use the information obtained from all values of a parameter. Of course this insight alone is easy to make; the hard part is encoding this huge amount of information into an understandable and easy-to-represent form. With TDA, there is a mathematical interpretation when the information is a homology group. In general, the assumption is that features that persist for a wide range of parameters are "true" features. Features persisting for only a short period are presumed to be noise, although the theoretical justification for this is unclear.

Early history

Precursors to the full concept of persistent homology appeared gradually over time. In 1990, Patrizio Frosini introduced the size function, which is equivalent to the 0th persistent homology. Nearly a decade later, Vanessa Robins studied the images of homomorphisms induced by inclusion. Finally, shortly thereafter, Edelsbrunner et al. introduced the concept of persistent homology together with an efficient algorithm and its visualization as a persistence diagram. Carlsson et al. reformulated the initial definition and gave an equivalent visualization method called persistence barcodes, interpreting persistence in the language of commutative algebra.

Concepts

Some widely used concepts are introduced below. Note that some definitions may vary from author to author.

A point cloud is often defined as a finite set of points in some Euclidean space, but may be taken to be any finite metric space.

The Čech complex of a point cloud is the nerve of the cover of balls of a fixed radius around each point in the cloud.

A persistence module U indexed by Z is a vector space U t for each t ∈ Z , and a linear map u t s : U s → U t whenever s ≤ t , such that u t t = 1 for all t and u t s u s r = u t r whenever r ≤ s ≤ t . An equivalent definition is a functor from Z considered as a partially ordered set to the category of vector spaces.

The persistent homology group P H of a persistence module is defined as P H k ( X ) = ∏ H k ( X r ) , where X r is the Čech complex of radius r of the point cloud X and H k is the homology group.

A persistence barcode is a multiset of intervals in R , and a persistence diagram is a multiset of points in Δ ( := { ( u , v ) ∈ R 2 | u , v ≥ 0 , u ≤ v } ).

The Wasserstein distance between two persistence diagrams X and Y is defined as

The bottleneck distance between X and Y is

Structure theorem

The first classification theorem for persistent homology appeared in 2005: for a finitely generated persistence module C with field F coefficients,

Persistent homology is visualized through a barcode or persistence diagram. The barcode has its root in abstract mathematics, though not at first sight; essentially, the derived category of chain complexes over a field is equivalent to the graded category of vector spaces.

Stability

Stability is desirable because it provides robustness against noise. If X is any space which is homeomorphic to a simplicial complex, and f , g : X → R are continuous tame functions, then the persistence vector spaces { H k ( f − 1 ( [ 0 , r ] ) ) } and { H k ( g − 1 ( [ 0 , r ] ) ) } are finitely presented, and W ∞ ( D ( f ) , D ( g ) ) ≤ ∥ f − g ∥ ∞ , where W ∞ refers to the bottleneck distance.

Workflow

The basic workflow in TDA is:

1. If X is a point cloud, replace X with a nested family of simplicial complexes X r (such as the Čech or Vietoris-Rips complex). This process converts the point cloud into a filtration of simplicial complexes. Taking the homology of each complex in this filtration gives a persistence module
2. Apply the structure theorem to provide a parameterized version of Betti number, persistence diagram, or equivalently, barcode.

Graphically speaking,

Computation

The first algorithm for persistent homology over F 2 was given by Edelsbrunner et al. Zomorodian and Carlsson gave the first practical algorithm to compute persistent homology over all fields. Edelsbrunner and Harer's book gives general guidance on computational topology.

One issue that arises in computation is the choice of complex. The Čech complex and Vietoris-Rips complex are most natural at first glance; however, their size grows rapidly with the number of data points. The Vietoris-Rips complex is preferred over Čech complex because its definition is simpler and the Čech complex requires extra effort to define in a general finite metric space. Efficient ways to lower the computational cost of homology have been studied. For example, the α-complex and witness complex are used to reduce the dimension and size of complexes.

Recently, Discrete Morse theory has shown promise for computational homology because it can reduce a given simplicial complex to a much smaller cellular complex which is homotopic to the original one. This reduction can in fact be performed as the complex is constructed by using matroid theory, leading to further performance increases. Another recent algorithm saves time by ignoring the homology classes with low persistence.

Various software packages are available, such as javaPlex, Dionysus, Perseus, PHAT, DIPHA, and Gudhi. A comparison between these tools is done by Otter et al. Also, an R package TDA is capable of calculating recently invented concepts like landscape and the kernel distance estimator.

Visualization

High-dimensional data is impossible to visualize directly. Many methods have been invented to extract a low-dimensional structure from the data set, such as principal component analysis and multidimensional scaling. However, it is important to note that the problem itself is ill-posed, since many different topological features can be found in the same data set. Thus, the study of visualization of high-dimensional spaces is of central importance to TDA, although it does not necessarily involve the use of persistent homology. However, recent attempts have been made to use persistent homology in data visualization.

Carlsson et al. have proposed a general method called MAPPER. It inherits the idea of Serre that a covering preserves homotopy. A generalized formulation of MAPPER is as follows:

Let X and Z be topological spaces and let f : X → Z be a continuous map. Let U = { U α } α ∈ A be a finite open covering of Z . The output of MAPPER is the nerve of the pullback cover M ( U , f ) := N ( f − 1 ( U ) ) , where each preimage is split into its connected components. This is a very general concept, of which the Reeb graph and merge trees are special cases.

This is not quite the original definition. Carlsson et al. choose Z to be R or R 2 , and cover it with open sets such that at most two intersect. This restriction means that the output is in the form of a complex network. Because the topology of a finite point cloud is trivial, clustering methods (such as single linkage) are used to produce the analogue of connected sets in the preimage f − 1 ( U ) when MAPPER is applied to actual data.

Mathematically speaking, MAPPER is a variation of the Reeb graph. If the M ( U , f ) is at most one dimensional, then for each i ≥ 0 ,

Three successful applications of MAPPER can be found in Carlsson et al. A comment on the applications in this paper by J. Curry is that "a common feature of interest in applications is the presence of flares or tendrils."

A free implementation of MAPPER is available online written by Daniel Müllner and Aravindakshan Babu. MAPPER also forms the basis of Ayasdi's data visualization platform.

Multidimensional persistence

Multidimensional persistence is important to TDA. The concept arises in both theory and practice. The first investigation of multidimensional persistence was early in the development of TDA, and is one of the founding papers of TDA. The first application to appear in the literature is a method for shape comparison, similar to the invention of TDA.

The definition of an n-dimensional persistence module in R n is

It might be worth noting that there are controversies on the definition of multidimensional persistence.

One of the advantages of one-dimensional persistence is its representability by a diagram or barcode. However, discrete complete invariants of multidimensional persistence modules do not exist. The main reason for this is that the structure of the collection of indecomposables is extremely complicated by Gabriel's theorem in the theory of quiver representations, although a finitely n-dim persistence module can be uniquely decomposed into a direct sum of indecomposables due to the Kull-Schmidt theorem.

Nonetheless, many results have been established. Carlsson and Zomorodian introduced the rank invariant ρ M ( u , v ) , defined as the ρ M ( u , v ) = r a n k ( x u − v : M u → M v ) , in which M is a finitely generated n-graded module. In one dimension, it is equivalent to the barcode. In the literature, the rank invariant is often referred as the persistent Betti numbers (PBNs). In many theoretical works, authors have used a more restricted definition, an analogue from sublevel set persistence. Specifically, the persistence Betti numbers of a function f : X → R k are given by the function β f : Δ + → N , taking each ( u , v ) ∈ Δ + to β f ( u , v ) := r a n k ( H ( X ( f ≤ u ) → H ( X ( f ≤ v ) ) ) , where Δ + := { ( u , v ) ∈ R × R : u ≤ v } and X ( f ≤ u ) := { x ∈ X : f ( x ) ≤ u } .

Some basic properties include monotonicity and diagonal jump. Persistent Betti numbers will be finite if X is a compact and locally contractible subspace of R n .

Using a foliation method, the k-dim PBNs can be decomposed into a family of 1-dim PBNs by dimensionality deduction. This method has also led to a proof that multi-dim PBNs are stable. The discontinuities of PBNs only occur at points ( u , v ) ( u ≤ v ) where either u is a discontinuous point of ρ M ( ⋆ , v ) or v is a discontinuous point of ρ ( u , ⋆ ) under the assumption that f ∈ C 0 ( X , R k ) and X is a compact, triangulable topological space.

Persistent space, a generalization of persistent diagram, is defined as the multiset of all points with multiplicity larger than 0 and the diagonal. It provides a stable and complete representation of PBNs. An ongoing work by Carlsson et al. is trying to give geometric interpretation of persistent homology, which might provide insights on how to combine machine learning theory with topological data analysis.

The first practical algorithm to compute multidimensional persistence was invented very early. After then, many other algorithms have been proposed, based on such concepts as discrete morse theory and finite sample estimating.

Other persistences

The standard paradigm in TDA is often referred as sublevel persistence. Apart from multidimensional persistence, many works have been done to extend this special case.

Zigzag persistence

The nonzero maps in persistence module are restricted by the preorder relationship in the category. However, mathematicians have found that the unanimousness of direction is not essential to many results. "The philosophical point is that the decomposition theory of graph representations is somewhat independent of the orientation of the graph edges". Zigzag persistence is important to the theoretical side. The examples given in Carlsson's review paper to illustrate the importance of functorality all share some of its features.

Extended persistence and levelset persistence

Some attempts is to lose the stricter restriction of the function. Please refer to the Categorization and cosheaf and Impact on mathematics sections for more information.

It's natural to extend persistence homology to other basic concepts in algebraic topology, such as cohomology and relative homology/cohomology. An interesting application is the computation of circular coordinates for a data set via the first persistent cohomology group.

Circular persistence

Normal persistence homology studies real-valued functions. The circle-valued map might be useful, "persistence theory for circle-valued maps promises to play the role for some vector fields as does the standard persistence theory for scalar fields", as commented in D. Burghelea et al. The main difference is that Jordan cells(very similar in format to the ones in linear algebra) are nontrivial in circle-valued functions, which would be zero in real-valued case, and combing with barcodes give the invariants of a tame map, under moderate conditions.

Two techniques they use are More-Novikov theory and graph representation theory. More recent results can be found in D. Burghelea et al. For example, the tameness requirement can be replaced by the much weaker condition, continuous.

Persistence with torsion

The proof of the structure theorem relies on the base domain being field, so not many attempts have been made on persistence homology with torsion. Frosini defined a pseudometric on this specific module and proved its stability. One of its novelty is that it doesn't depend on some classification theory to define the metric.

Categorization and cosheaves

One advantage of category theory is its ability to lift concrete results to a higher level, showing relationships between seemingly unconnected objects. Bubenik et al. offers a short introduction of category theory fitted for TDA.

Category theory is the language of modern algebra, and has been widely used in the study of algebraic geometry and topology. It has been noted that "the key observation of is that the persistence diagram produced by depends only on the algebraic structure carried by this diagram." The use of category theory in TDA has proved to be fruitful.

Following the notations made in Bubenik et al., the indexing category P is any preordered set (not necessarily N or R ), the target category D is any category (instead of the commonly used V e c t F ), and functors P → D are called generalized persistence modules in D , over P .

One advantage of using category theory in TDA is a clearer understanding of concepts and the discovery of new relationships between proofs. Take two examples for illustration. The understanding of the correspondence between interleaving and matching is of huge importance, since matching has been the method used in the beginning (modified from Morse theory). A summary of works can be found in Vin de Silva et al. Many theorems can be proved much more easily in a more intuitive setting. Another example is the relationship between the construction of different complexes from point clouds. It has long been noticed that Čech and Vietoris-Rips complexes are related. Specifically, V r ( X ) ⊂ C 2 r ( X ) ⊂ V 2 r ( X ) . The essential relationship between Cech and Rips complexes can be seen much more clearly in categorical language.

The language of category theory also helps cast results in terms recognizable to the broader mathematical community. Bottleneck distance is widely used in TDA because of the results on stability with respect to the bottleneck distance. In fact, the interleaving distance is the terminal object in a poset category of stable metrics on multidimensional persistence modules in a prime field.

Sheaves, a central concept in modern algebraic geometry, are intrinsically related to category theory. Roughly speaking, sheaves are the mathematical tool for understanding how local information determines global information. Justin Curry regards level set persistence as the study of fibers of continuous functions. The objects that he studies are very similar to those by MAPPER, but with sheaf theory as the theoretical foundation. Although no breakthrough in the theory of TDA has yet used sheaf theory, it is promising since there are many beautiful theorems in algebraic geometry relating to sheaf theory. For example, a natural theoretical question is whether different filtration methods result in the same output.

Stability

Stability is of central importance to data analysis, since real data carry noises. By usage of category theory, Bubenik et al. have distinguished between soft and hard stability theorems, and proved that soft cases are formal. Specifically, general workflow of TDA is

Soft stability theorem asserts that H F is Lipschitz, and hard stability theorem asserts that J is Lipschitz.

Bottleneck distance is widely used in TDA. The isometry theorem asserts that the interleaving distance d I is equal to the bottleneck distance. Bubenik et al. have abstracted the definition to that between functors F , G : P → D when P is equipped with a sublinear projection or superlinear family, in which still remains a pseudometric. Considering the magnificent characters of interleaving distance, here we introduce the general definition of interleaving distance(instead of the first introduced one): Let Γ , K ∈ T r a n s P Γ , K ∈ T r a n P (a function from P to P which is monotone and satisfies x ≤ Γ ( x ) for all x ∈ P ). A ( Γ , K ) -interleaving between F and F consists of natural transformations φ : F ⇒ G Γ and ψ : G ⇒ F K , such that ( ψ Γ ) φ = F η K Γ and ( φ Γ ) = ψ G η Γ K .

The two main results are

These two results summarize many results on stability of different models of persistence.

For the stability theorem of multidimensional persistence, please refer to the subsection of persistence.

Structure theorem

The structure theorem is of central importance to TDA; as commented by G. Carlsson, "what makes homology useful as a discriminator between topological spaces is the fact that there is a classification theorem for finitely generated abelian groups."

The main argument used in the proof of the original structure theorem is the standard classification theorem for finitely generated modules over a principal ideal domain. However, this argument fails if the indexing set is ( R , ≤ ) . Carlsson gave a detailed discussion in the most influential review paper in TDA.

In general, not every persistence module can be decomposed into intervals. Many attempts have been made loosing the assumptions. The case for pointwise dimensional persistence modules indexed by a locally finite subset of R is solved based on the work of Webb. The most notable result is done by Crawley-Boevey, which solved the case of R . Crawley-Boevey's theorem states that any pointwise finite-dimensional persistence module is a direct sum of interval modules.

To understand the definition of his theorem, some concepts need introducing. An interval in ( R , ≤ ) is defined as a subset I ⊂ R having the property that if r , t ∈ I and if there is an s ∈ R such that r ≤ s ≤ t , then s ∈ I as well. An interval module k I assigns to each element s ∈ I the vector space k and assigns the zero vector space to elements in R / I . All maps ρ s t are the zero map, unless s , t ∈ I and s ≤ t , in which case ρ s t is the identity map. Interval modules are indecomposable.

Although this is a very powerful theorem, it still doesn't extend to the q-tame case. A persistence module is q-tame if the rank( ρ s t ) is finite for all s ≤ t . There are examples that q-tame persistence module fails to be pointwise finite. However, it turns out that similar structure theorem still exists if the features that exist only at one index value are removed. Actually, the infinite dimension wouldn't persist. Specifically, the observable category O b is defined as P e r s / E p h , in which E p h denotes the full subcategory of P e r s whose objects are the ephemeral modules ( ρ s t = 0 whenever s < t ).

Note that all these extended results listed here don't apply to the zigzag persistence. There is some work on the stability of zigzag persistence.

Statistics

Real data is always finite, thus the study of it is stochastic in essence. To distinguish between true nature and artifacts is the power of statistics. Note that persistent homology has no mechanism to distinguish between low-probability features and high-probability features.

One way of statistics is to study statistical properties of summaries on topological features of point cloud. A reference of the works done on "the study of random abstract simplicial complexes generated from stochastic processes and non-asymptotic bounds on the convergence or consistency of topological summaries as the number of points increase" can be found in K. Turner et al.

Another way, and also the more important one, is to study the probability distribution on the persistence space. The persistence space B ∞ is the ∐ n B n / ∽ , where B n are all the barcodes containing exactly n intervals and the equivalences are { [ x 1 , y 1 ] , [ x 2 , y 2 ] , . . . , [ x n , y n ] } ∽ { [ x 1 , y 1 ] , [ x 2 , y 2 ] , . . . , [ x n − 1 , y n − 1 ] } if that x n = y n . This space is fairly complicated, for example, not complete endowed with the bottleneck metric. The first attempt made on is by Y. Mileyko et al. The space of persistence diagrams D p in their paper is defined as

An interesting concept, persistent landscape, invented by Peter Bubenik, has led another direction, namely the different representation of barcode. The persistent landscape over a persistent module M is defined as a function λ : N × R → R ¯ , λ ( k , t ) := sup ( m ≥ 0 | β t − m , t − m ≥ k ) , where R ¯ denotes the extended real line and β a , b = d i m ( i m ( M ( a ≤ b ) ) ) . While it inherits all good properties of barcode representation (stability, easy representation, etc.), its space is very nice: not only statistical inferences can be defined, some problems in Y. Mileyko et al.'s work, such as the expectation is not necessarily unique, can be overcome. Effective algorithm is available. Another approach is to use revised persistence, which is Image, kernel and cokernel persistence.

Classification of applications

More than one way exists to classify the applications of TDA. Perhaps the most natural way is by field. A very incomplete list of successful applications includes data skeletonization, shape study, graph reconstruction, image analysis, material, progression analysis of disease, sensor network, signal analysis, cosmic web, complex network, fractal geometry, viral evolution, and the propagation of contagions on networks.

Another way is by distinguishing the techniques by G. Carlsson,

one being the study of homological invariants of data one individual data sets, and the other is the use of homological invariants in the study of databases where the data points themselves have geometric structure.

Characteristics of TDA in applications

Ayasdi is a data analysis company relying heavily on TDA, cofounded by a number of leading researchers in the field. There are several notable interesting features of the recent applications of TDA:

1. Combining tools from several branches of mathematics. Besides the obvious need for algebra and topology, partial differential equations, algebraic geometry, presentation theory, statistics, combinatorics, and Riemannian geometry have all found use in TDA.
2. Quantitative analysis. Topology is considered to be very soft since many concepts are invariant under homotopy. However, persistent topology is able to record the birth(appearance) and death(disappearance) of topological feature, thus extra geometric information is embedded in it. One evidence in theory is a partially positive result on the uniqueness of reconstruction of curves; two in application are on the quantitative analysis of Fullerene stability and quantitative analysis of self-similarity, separately.
3. The role of short persistence. Short persistence has also been found to be useful, despite the common belief that noise is the cause of the phenomena. This is interesting to the mathematical theory.

One of the main fields of data analysis today is machine learning. Some examples of machine learning in TDA can be found in Adcock et al. A conference is dedicated to the link between TDA and machine learning. In order to apply tools from machine leaning, the information obtained from TDA should be represented in vector form. An ongoing and promising attempt is the persistence landscape discussed above. Another attempt uses the concept of persistence images. However, one problem of this method is the loss of stability, since the hard stability theorem depends on the barcode representation.

Impact on mathematics

Topological data analysis and persistent homology have had impacts on Morse theory. Morse theory has played a very important role in the theory of TDA, including on computation. Some work in persistent homology has extended results about Morse functions to tame functions or, even to continuous functions. A forgotten result of R. Deheuvels long before the invention of persistent homology extends Morse theory to all continuous functions.

One recent result is that the category of Reeb graphs is equivalent to a particular class of cosheaf. This is motivated by theoretical work in TDA, since the Reeb graph is related to Morse theory and MAPPER is derived from it. The proof of this theorem relies on the interleaving distance.

It is evident to mathematicians that persistent homology is closely related to spectral sequences. Zigzag persistence may turn out to be of theoretical importance to spectral sequences.