Topological data analysis

Topological data analysis (TDA) is a new and vastly growing branch of applied mathematics.

Data analysis is of extreme importance in almost all areas of modern applied science. However, to extract information from real data which are usually large, high-dimensional, incomplete and noisy is challenging. TDA provides a general framework to analyze data, being successful in coordinate-freeness, insensitive to particular metric, dimension reduction and robustness to noise. Beyond, it inherits functorality, one of the keys to the modern mathematics, from its topological nature, which makes it adaptive to new tools from mathematics.

The initial motivation is to study the shape of data. TDA has combined algebraic topology and other tools from pure mathematics to give mathematically strict and quantitative study of "shape". The main tool is persistent homology, a modified concept of homology group. Nowadays, this area has been proven to be successful in practice. It has been applied to many types of data input, and different data resources. Moreover, its mathematical foundation is also of theoretical importance to mathematics itself. Its unique features makes it a promising bridge between topology and geometry.

Basic theory

Basic concepts and theoretical results in TDA will be introduced. Specially, the focus would be on the standard paradigm, namely the barcode of point clouds. These results are widely used in applications. For the basic concepts of algebraic topology, please refer to section 2 of Carlsson for a short introduction, or to the standard textbooks, such as Hatcher.

Brief history

The idea of persistence emerged independently in three groups. Patrizio introduced size function, which is equivalent to the 0th persistent homology. Vanessa Robins studied the images of homomorphisms induced by inclusion.

Edelsbunnar etc. introduced persistent homology together with a fast algorithm and the presentation as persistent diagram. Carlsson etc. reformulated their definition of persistent homology and gave an equivalent visualization method called persistent barcodes. Carlsson has interpreted it into the language of commutative algebra.

Intuition

Suppose given a large number of randomly selected points from a circle with noise, how can we cover the

One illustrative example is a predator-prey system governed by a Lotka-Volterra equation. One can easily observe that data forms a closed circle, which is intuitively the shape of this data. TDA provides tools to detect such recurrent movement.

A common believe is that true features would last longer(this is the meaning of PERSISTENT), and short ones are caused by noises.

A common belief in this community is that short persistence is nothing but noisy, though no mathematical justification is made. However,

Concepts

Persistent homology

Persistent module $\mathbb {U}$ indexed by $\mathbb {Z}$ is defined as: a vector space $U_{t}$ for each $t\in \mathrm {Z}$, and a linear map $u_{t}^{s}:U_{s}\to U_{t}$ whenever $s\leq t$, such that $u_{t}^{t}=1$ for all $t$ and $u_{t}^{s}u_{s}^{r}=u_{s}^{r}$ whenever $r\leq s\leq t.$

Wasserstein distance between two persistent diagram $X$ and $Y$ is defined as

$$W_{p}[L_{q}](X,Y):=\inf _{\phi :X\to Y}[\sum _{x\in X}\Vert x-\phi (x)\Vert _{q}]^{\frac {1}{p}}$$

where $1\leq p,q\leq \infty$ and $\phi$ ranges over bijections between $X$ and $Y$. Please refer to figure 3.1 in Munch for illustration.

Bottleneck distance is defined as

$$W_{\infty }[L_{q}](X,Y):=\inf _{\phi :X\to Y}\sup _{x\in X}\Vert x-\phi (x)\Vert _{q}$$

which clearly is a special case when $p=\infty$ in Wasserstein distance.

One of the main advantages is that under mild condition, barcode whose structure is extremely easy is a discrete complete invariant of persistent homology.

Basic Property

Structure theorem

The first form of classification theorem for persistent homology appeared in 2005:

For a finitely generated persistent module $C$ with field $F$ coefficients, ${\textstyle H_{\star }(C;F)\simeq \oplus _{i}x^{t_{i}}F[x](\oplus _{j}x^{r_{j}}(F[x]/(x^{s_{j}}F[x])))}$

#This theorem also has an intuitive explanation

Stability

Persistent homology essentially calculates homology groups at different spatial resolutions to see which features persist over a wide range of length scales. It is assumed that important features and structures are the ones that persist. We define persistent homology as follows: Let $K^{l}$ be a filtration. The p-persistent kth homology group of $K^{l}$ is $H_{k}^{l,p}=Z_{k}^{l}/(B_{k}^{l+p}\cap Z_{k}^{l})$.

Let $z$ be a nonbounding $k$-cycle created at time $I$ by simplex $\sigma$ and let $z'\sim z$ be a homologous $k$-cycle that becomes a boundary cycle at time $J$ by simplex $\tau$. Then we can define the persistence interval associated to $z$ as $(I,J)$. We call $\sigma$ the creator of $z$ and $\tau$ the destroyer of $z$. If $z$ does not have a destroyer, its persistence is $\infty$. Instead of using an index-based filtration, we can use a time-based filtration. Let $K$ be a simplicial complex and $K^{\rho }=\{\sigma ^{i}\in K\mid \rho (\sigma ^{i})\leq \rho \}$ be a filtration defined for an associated map $\rho :S(K)\rightarrow \mathbb {R}$ that maps simplices in the final complex to real numbers. Then for all real numbers $\pi \geq 0$, the $\pi$-persistent kth homology group of $K^{\rho }$ is $H_{k}^{\rho ,\pi }=Z_{k}^{\rho }/(B_{k}^{\rho +\pi }\cap Z_{k}^{\rho })$. The persistence of a $k$-cycle created at time $\rho _{i}$ and destroyed at $\rho _{j}$ is $\rho _{j}-\rho _{i}$.

Workflow

point cloud

${\stackrel {F}{\longrightarrow }}$

filtered complexes

${\stackrel {H}{\longrightarrow }}$

persistent module

${\stackrel {J}{\longrightarrow }}$

barcode or diagram

The basic method in TDA is:

refer to curry

1. Replace a point cloud with a nested family of simplicial complexes, indexed by a parameter. This process converts the point cloud into global topological objects.
2. Analyze these topological complexes via persistent homology.
3. Encode the persistent homology of the point cloud in the form of a parameterized version of Betti number, persistence diagram, or equivalently, barcode.

Computation

The applied mathematics has to face the issue of computational complexity. The first algorithm of persistent homology over $F_{2}$ is given by Edelsbrunnar etc. Carlsson etc. gives the first practical algorithm to compute the persistent homology over all fields. Edelsbrunner and Harer's book serves as a great general guidance on computational topology.

One issue concerning computation is the choice of complex. Čech complex and Vietoris-Rips complex are most natural at first glance, however, the computation complexity would be same as matrix multiplication. It is straightforward that Vietoris-Rips complex is preferred over Čech complex by their definitions, and Čech complex does require some efforts to make a general definition in metric space. Efficient ways to lower the computational cost have been studied. For example, α-complex and witness complex are invented to reduce the dimension of complexes. Another approach is to reduce ???

Two methods of theoretical novelty appeared recently. Discrete morse theory has shown its potential in the computation because it may reduce a given complex to a much smaller cellular complex which is homotopic to the original one. The basic idea of another algorithm is to ignore the homology classes of low persistence.

Various software packages are available, such as javaPlex, Dionysus, Perseus (which uses discrete Morse theory to simplify the matrix algebra), PHAT, and Gudhi. A comparison between these tool is done by Otter etc. Also, an R package TDA is capable of calculating recently invented concepts like landscape and 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 very question is ill-posed, since different topological features can be found in the same data set. Thus, this technique is of central importance to TDA, although it doesn't involve the use of persistent homology(though attempts have been made on this direction).

Carlsson etc. have proposed a general method called MAPPER. It inherits the idea of Serré that covering homotopy. A generalized definition of MAPPER is that

Let $X$ and $Z$ be topological spaces and let $f:X\to Z$ be a continuous map. Let $\mathbb {U} =\{U_{\alpha }\}_{\alpha \in A}$ be a finite open covering of $Z$. The mapper is defined as the nerve of the pullback cover ${\textstyle M(\mathbb {U} ,f):=N(f^{-1}(\mathbb {U} ))}$.

Note that this is not that original definition. Carlsson etc. choose $Z$ as $\mathbb {R}$ or $\mathbb {R} ^{2}$, and covers it with at most two would intersect. By doing so, the mapper would be in the form of a complex network. Because the samples would be finite, some clustering methods, for example, single linkage clustering, are required to form components of the inverse map of a single cover, which is similar to the connected components of $f^{-1}(U_{\alpha })$.

A mathematical justification is that if the ${\textstyle M(\mathbb {U} ,f)}$ is at most one dimensional, then for each $i\geq 0$,

$$H_{i}(X)\simeq H_{0}(N(\mathbb {U} );{\hat {F}}_{i})\oplus H_{1}(N(\mathbb {U} );{\hat {F}}_{i-1})$$

The flexibility also has disadvantages. One problem is instability, that some change of the choice of the cover can lead to major change of the mapper.

The successful applications of MAPPER can be found in Carlsson etc. A comment of these applications by J. Curry is that "a common feature of interest in applications [of MAPPER in Carlsson etc.] is the presence of flares or tendrils."

Mathematical Foundation

Although persistent homology is a "21st child of algebraic homology", its mathematical foundation has been vastly developed. An incomplete list of active mathematicians working on this field may include leading figures Gunnar Carlsson, Herbert Edelsbrunner, Vin De Silva, Peter Bubenik, Frédéric Chazal,Robert Christ, and rising scholars such as Micheal Lesnick, Justin Curry, Jonathan Scott.

Multidimensional Persistence

Without exaggeration, multidimensional persistence is of the utmost importance to TDA. It naturally arise from both theory and practice. The first investigation of multidimensional persistence was at the very easy stage of TDA, and is considered in one of the founding paper of modern TDA. Its first application appeared in literature is also on shape comparison, similar to the invention of TDA.

Definition of an n-dimensional persistence module in $\mathbb {R} ^{n}$ is

• vector space $V_{s}$ is assigned to each point in $s=(s_{1},...,s_{n})$
• map $\rho _{s}^{t}:V_{s}\to V_{t}$ is assigned if $s\leq t$($s_{i}\leq t_{i},i=1,...,n)$
• maps satisfy $\rho _{r}^{t}=\rho _{s}^{t}\circ \rho _{r}^{s}$ for all $r\leq s\leq t$

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

One of the advantages of 1-dim persistence is its representability, namely diagram or barcode. However, it has been proved that discrete complete invariants don't exist. The main argument is that, the collection of isomorphism classes of the indecomposables are 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 etc. introduced the rank invariant $\rho _{M}(u,v)$, defined as the $\rho _{M}(u,v)=\mathrm {rank} (x^{u-v}:M_{u}\to M_{v})$, in which $M$ is a finitely generated n-graded module. In 1-D, it is equivalent to ??. In literature, it is often referred as PBNs(persistent Betti numbers). In many theoretical works, authors would use more restricted definition, an analogue from the sublevel persistence. Specifically, PBNs (the persistence Betti numbers) of function $f:X\to \mathrm {R} ^{k}$ is the function $\beta _{f}:\Delta ^{+}\to \mathrm {N}$, taking each $(u,v)\in \Delta ^{+}$ to $\beta _{f}(u,v):=\mathrm {rank} (H(X(f\leq u)\to H(X(f\leq v)))$, where $\Delta ^{+}:=\{(u,v)\in \mathbb {R} \times \mathbb {R} :u\leq v\}$ and $X(f\leq u):=\{x\in X:f(x)\leq u\}$.

Some basic properties include monotony and diagonal jump. PBNs will be finite if $X$ is assumed to be a compact and locally contractible subspace of $\mathbb {R} ^{n}$.

Based on a so-called 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 prove the stability of multi-dim PBNs are stable. the discontinuities of PBNs only occur in point $(u,v)(u\leq v)$ if either $u$ is a discontinuous point of $\rho _{M}(\star ,v)$ or $v$ is a discontinuous point of $\rho (u,\star )$ under the assumption that $f\in C^{0}(X,\mathrm {R} ^{k})$ and $X$ is a compact, triangulable topological space.

Persistent space, a generalization of persistent diagram, is defined as multiset of all points with multiplicity larger than 0 and the diagonal. It provides a stable and complete representation of PBNs.

The first practical algorithm to compute multidimensional persistence was invented very early. After then, many works have been laid, such as discrete morse theory, 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.

Image, kernel and cokernel persistence

dd

Extended Persistence and Levelset Persistence

whether filtration methods result the same outcoming.

Circular Persistence

Normal persistence homology studies real-valued functions. The circle-valued map might be useful

More recent results can be found in D. Burghelea etc.

Categorization and Cosheafilization

One advantage of category theory is that the truth can be elevated to a formal point. It usually provides a general platform to treat results that are seemingly unrelated. Bubenik etc. offers a short introduction of category theory fitted for TDA; and for general techniques please refer to the standard textbook.

Category 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 etc., the indexing category ${\textstyle P}$ is any preordered set (instead of the normally used $\mathbb {N}$ or $\mathbb {R}$), the target category $D$ is any category (instead of the commonly used ${\textstyle \mathrm {Vect} _{\mathbb {F} }}$), and functors ${\textstyle P\to D}$ are called generalized persistence modules, in $D$, over ${\textstyle P}$.

The correspondence between interleaving and matching is of

Cech and Rips

It has long been noticed that Čech and Vietoris-Rips complexes are related. Specifically, $V_{r}(X)\subset C_{{\sqrt {2}}r}(X)\subset V_{2r}(X)$.

Roughly speaking, sheaf is the mathematical tool to view how local information determines the global. Level set persistence is

Bottleneck distance is widely used in TDA because of the first stability theorem and other results on stability. A mathematical jurisdiction is that the interleaving distance(refer to the section of stability for definition) is the terminal object in a poset category of stable metrics on multidimensional persistence modules in a prime field.

Stability

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

data

${\stackrel {F}{\longrightarrow }}$

generalized persistence module

${\stackrel {H}{\longrightarrow }}$

generalize persistence module

${\stackrel {J}{\longrightarrow }}$

discrete invariant

Soft stability theorem asserts that $HF$ 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 etc. have abstracted the definition to that between functors $F,G:P\to D$ when ${\textstyle 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 $\Gamma ,K\in \mathrm {Trans_{P}}$$\Gamma ,K\in \mathrm {Tran_{P}}$(a function from ${\textstyle P}$ to ${\textstyle P}$ which is monotone and satisfies $x\leq \Gamma (x)$ for all ${\textstyle x\in P}$). A $(\Gamma ,K)$-interleaving between F and F consists of natural transformations $\varphi :F\Rightarrow G\Gamma$ and $\psi :G\Rightarrow FK$, such that $(\psi \Gamma )\varphi =F\eta _{K\Gamma }$ and $(\varphi \Gamma )=\psi G\eta _{\Gamma K}$.

The two main results are

• Let ${\textstyle P}$ be a preordered set with a sublinear projection or superlinear family. Let ${\textstyle H:D\to E}$ be a functor between arbitrary categories ${\textstyle D,E}$. Then for any two functors ${\textstyle F,G:P\to D}$, we have ${\textstyle d_{I}(HF,HG)\leq d_{I}(F,G)}$.
• Let ${\textstyle P}$ be a poset of a metric space ${\textstyle Y}$ , ${\textstyle X}$ be a topological space. And let${\textstyle f,g:X\to Y}$ (not necessarily continuous) be functions, and ${\textstyle F,G}$ to be the corresponding persistence diagram. Then $d_{I}(F,G)\leq d_{\infty }(f,g):=\sup _{x\in X}d_{Y}(f(x),g(x))$.

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 in $(\mathbb {R} ,\leq )$ since $\mathbb {R}$ is not a PID. 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 $\mathbb {R}$ is solved based on the work of Webb. The most notable result is done by Crawley-Boevey, which solved the case of $\mathbb {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 $(\mathbb {R} ,\leq )$ is defined as a subset $I\subset \mathbb {R}$ having the property that if $r,t\in I$ and if there is an $s\in \mathbb {R}$ such that $r\leq s\leq t$, then $s\in I$ as well. An interval module $k_{I}$ assigns to each element $s\in I$ the vector space $k$ and assigns the zero vector space to elements in $\mathbb {R} /I$. All maps $\rho _{s}^{t}$ are the zero map, unless $s,t\in I$ and $s\leq t$, in which case $\rho _{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($\rho _{s}^{t}$) is finite for all $s\leq 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 $\mathrm {Ob}$ is defined as $\mathrm {Pers} /\mathrm {Eph}$, in which $\mathrm {Eph}$ denotes the full subcategory of $\mathrm {Pers}$ whose objects are the ephemeral modules($\rho _{s}^{t}=0$ whenever $s<t$).

Note that all these extended results listed here don't apply to the 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.

Application

More than one way exist to classify the library of applications by TDA.

One way is by its filed. An very incomplete list of successful applications includes shape study, image analysis, material, progression analysis of disease, sensor network, signal analysis, cosmic web, complex network, fractal geometry, viral evolution,

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 dat apoints themselves have geometric structure.

There are several notable interesting features of the recent applications of TDA:

1. Combining tools from all main branches of mathematics. Besides obvious need for algebra and topology, PDE, algebraic geometry, presentation theory, statistics, combination, Riemannian geometry are all applied. Utilizing so many tools is rare in applied mathematics.
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 useful, against the common belief that noise is the cause of the phenomena. This is interesting to the mathematical theory.

TDA has also made huge impact on the industry. Cofounded by many leading scholars in TDA, Ayasdi is a data analysis company relying heavily on TDA.

As mentioned above, New representation of barcode

As noted in the section of stability, hard stability.

A comment is on Morse theory. Morse theory has played a very important role in the theory of TDA, including on computation(mentioned above). A forgotten effort done by R, Deheuvels is to extent morse theory to all continuous functions.

Essentially, the derived category of chain complexes over a field is equivalent to the graded category of vector spaces.

In order to apply tools from

See also

• Dimensionality reduction
• Data mining
• Computer vision
• Computational topology
• Discrete Morse Theory
• Shape analysis
• Size theory
• Algebraic Topology

Further reading

Brief Introduction

• Studying the Shape of Data Using Topology, by Michael Lesnick

• Why Topological Data Analysis Works, by Gunnar Carlsson

• Deep Dive: Topological Data Analysis, by Ayasdi Company
• Source Material for Topological Data Analysis by Mikael Vejdemo-Johansson

Video Lecture

• Introduction to Persistent Homology and Topology for Data Analysis, by Matthew Wright
• The Shape of Data, by Gunnar Carlsson

Textbook on Topology

• Algebraic Topology, by Allen Hatcher

• Computational Topology: An Introduction, by Herbert Edelsbrunner and John L. Harer
• Elementary Applied Topology, by Robert Ghrist

Other Resources of TDA

• Blog of Ayasdi

• Applied Topology, by Stanford

• Applied algebraic topology research network , by the Institute for Mathematics and its Applications.