Category Archives: appliedtopology

ATMCS 6 open for registration

Dear ALGTOP-L,

Algebraic Topology- Methods, Computation and Science 6 (ATMCS6) is now open for registration. The conference takes place at PIMS University of British Columbia May 26-30.

Confirmed speakers include:

Amit Patel
Donald Sheehy
Jeff Erickson
Jose Perea
Liz Munch
Michael Robinson
Omer Bobrowski
Peter Bubenik
Radmilla Sazdanovic
Sayan Mukerjhee
Vanessa Robbins
Yuliy Baryshnikov
Tamal Dey
Shmuel Weinberger
Raul Rabadan
Chris Hoffman
Vin de Silva

For more details, see:
http://www.pims.math.ca/scientific-event/140526-atmcs

Applied and computational topology refers to the adaptation of topological ideas and techniques to study problems in science and engineering. A particular focus is on using invariants and methods of algebraic topology to understand large high-dimensional data sets. The further development of topological techniques for use in applications and the creation of new areas of application in the subject are amongst the goals of this workshop.

The workshop will bring together leading researchers in this emerging discipline as well as providing an opportunity for young mathematicians to get involved in it. In past years, the ATMCS conference has been very successful in providing a forum for cutting-edge research to be disseminated; attendance tends to represent a broad swath of the diverse research community which works in this area.

Workshop Format:
The workshop will feature lectures and discussion in the morning and afteroon. Mid-Morning and Afternoon refreshments will be provided during the conference.

On behalf of the organizers
Andrew Blumberg, U Texas
Matthew Kahle, Ohio State
Mikael Vejdemo-Johansson, KTH / IMA / IJS

Source material for Topological Data Analysis

To start off the feature articles at appliedtopology.org, I figured it might be worth while collecting good entry points to the field. One of the most common questions I get about persistent homology and topological data analysis is how to get started with our techniques and ideas.

Overview articles and books

First off in the list of entry points is the written word. There are survey articles, overview articles and books written about topological data analysis as a whole, as well as focusing on specific parts.

Topology and Data by Gunnar Carlsson. This survey article came soon after Ghrist's survey, and covers persistent homology, as well as Mapper for topological simplification and modeling. It also comes with a good discussion of the underlying philosophy of the field.
Start here.

Barcodes: the persistent topology of data by Robert Ghrist. This is the first major survey article to come out, and covers persistent homology and some of its applications.

Topology for computing by Afra Zomorodian. This is the first book format exposition of persistent homology for applied and computational topology. It is a good and self-contained introduction to the field, if ever so slightly dated: in particular, it does not cover anything about zigzag persistence or multi-dimensional persistence.

Computational Topology: an introduction by Herbert Edelsbrunner and John Harer. This book covers the state of the art as of 2010 of computational topology, with some focus on persistent homology: one third of the book is devoted to persistence and its applications. Throughout, the book discusses the underlying theory, the most obvious algorithm, and the fastest known algorithm.

Software packages

So you understand what the underlying ideas of the field are. Next up, you'll want to try them out on your own data. There are some ways you can go to do this, and they all have their specific strengths and weaknesses.

Plex, jPlex, javaPlex: this sequence of libraries were developed in the Stanford group, and with an explicit aim at always interoperating smoothly and easily with Matlab. Of the three, we currently recommend javaPlex unless this library does not cover your exact use case — in which case some methods may exist in jPlex. Plex is written in C++, and connects to Matlab through a MEX interface, while jPlex and javaPlex are both Java libraries.

Dionysus: this library, written and maintained by Dmitriy Morozov, provides a platform for developing and experimenting with computational topology algorithms in C++ or in Python. It interfaces with CGAL for low dimensional geometric constructions, and has example applications provided for persistent homology, cohomology, vineyards, alphashapes and numerous other common techniques.

Perseus: this package, developed by Vidit Nanda, provides a platform for computing persistent homology for cubical and simplicial complexes generated in a number of different ways. It specifically uses methods based on discrete morse theory for speeding up computations.

pHat: this package, created by Ulrich Bauer, Michael Kerber and Jan Reininghaus builds on results by the authors that speeds up persistence computation by specific tricks that use structures in a persistence boundary matrix. Currently only using Z/2-coefficients and not constructing the complex for you, it seems to be the fastest publicly available package.

CHomP: this software package came out of the CHomP research project, and consists of a rich collection of tools to work persistently or statically with cubical complex data. For homology on image or voxel collection data, CHomP forms the fastest and most complete analysis system available right now.

We warmly appreciate suggestions for more papers, software, or other resources if you have anything to add to this list.

Exact sequence of a pair: Computing the connecting map

Given a pair of spaces (X,A), with A \subset X, the short exact sequence of the pair is a relationship between the chains C_*(A),C_*(X/A) and C_*(X). The sequence that looks like this:

(1)   \begin{equation*} 0 \longrightarrow C_*(A) \xlongrightarrow{i} C_*(X) \xlongrightarrow{j} C_*(X/A) \longrightarrow 0 \end{equation*}

is short exact, or that: \Ker{j} = \Im{i}. If you want to know more about exact sequences I recommend reading this.

It turns out that on the level of homology this short exact sequence turns into a long exact sequence:

(2)   \begin{equation*} \ldots \longrightarrow H_*(A) \xlongrightarrow{i_*} H_*(X) \xlongrightarrow{j_*} H_*(X/A) \xlongrightarrow{\delta} H_{*-1}(A) \ldots \end{equation*}

and the map \delta is called the connecting homomorphism.

The natural question to ask is: What is \delta([x])? The answer is that
that \delta([x]) = [\partial[x]]. However, if you read the aforementioned authoritative text on the subject you will see that \delta is not explicitly defined, but its existence is merely proved.

However, given a particular X and A, one is able to come up with an idea of what the map does. I’ll go over the basic diagram chase and then show how this works by example.

Since we are given a representation of H_*(X/A) we can begin by taking a homology class \hat{c} which is relative cycle. Any chain c in X which is in the class \hat{c} has the property that j(c) = \hat{c} in H_*(X/A). Such a chain c is called a lift.

Assuming we have found a lift we can compute z = \partial(c), and it turns out that z \in Z_{*-1}(A) (because \partial{j} = j\partial), which means that [z] \in H_{*-1}(A). So our mapping sends \hat{c} \in H_*(X/A) to [z] \in H_{*-1}(A). So you now just need to prove that this process is well defined and this ends your diagram chase as well as your interest in the details of this sequence. Unless of course you are Mr. Cooperman, or, a computer scientist.

If you are a computer scientist you might be dissatisfied because it is not entirely clear how [z] is presented. Indeed z itself is not unique as it depends on our choice of lift, z is likely itself not even a member of our given representative for homology on H_{*-1}(A).

The problem we have is that so far our cycle z is written down as a linear combination of cells. We want an equivalent representation in terms of cycles. Noether says we can write down Z_{*}(A) \simeq H_{*}(A) \oplus B_{*}(A).
This tells us that we can use our homology basis to form a basis for our cycle group, and its not to hard to see that we can extend the cycle group to a basis for all chains. However in our case we want to take a cycle expressed in the chain basis, and write it as a linear combination of given cycles. This amounts to being able to write down a rectangular “change of basis” matrix between the cell basis and the given cycle basis on Z_{*-1}(A).

The column space of this matrix would be given by our given cycle basis, and the row space would be given by the canonical cell basis for C_{*-1}(A). We then look to “solve Ax = z” over \mathbb{Z}_p (in this blog p = 2), in the sense that we want to write down a linear combination of the cycles in Z_{*-1}(A) apply our matrix and end up with the z we computed.

Consider this space A:

Rendered by QuickLaTeX.com

which is homotopic to an annulus.

We can imagine that A \subset X, and that X is obtained by gluing a disc onto the boundary of A, so that X is itself homotopic to a disc, X/A is then homotopic to a sphere, with exactly one non-trivial 2nd homology class. The boundary of this class would be the outermost cycle of A.

Lets say that we are provided a basis for H_1(A) = \langle \alpha = bc + cd + db \rangle and B_1 = \langle \beta = ab + bc + ca \rangle. If I want to express the outer bounding cycle ab + bd + dc +ca in this basis, I begin by writing down the change of basis matrix, in order to solve Ax=z I augment the matrix with the identity matrix on the right and z on the bottom.

    \[ A' = \left( \begin{array}{c|ccccc|cc} & ab & ac & bc & bd & cd & \alpha & \beta \\ \hline \alpha & 0 & 0 & 1 & 1 & 1 & 1 & 0 \\ \beta & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ \hline & 1 & 1 & 0 & 1 & 1 & 0 & 0 \end{array} \right) \]

Now you can see that modulo our extra row for z our matrix is in row echelon form, and it suffices to perform one Gaussian elimination (over Z_2) in this last column to achieve our result:

    \[ \left( \begin{array}{c|ccccc|cc} & ab & ac & bc & bd & cd & \alpha & \beta \\ \hline \alpha & 0 & 0 & 1 & 1 & 1 & 1 & 0 \\ \beta & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ \hline z & 1 & 1 & 0 & 1 & 1 & 0 & 0 \end{array} \right) \]

    \[ z \rightarrow z + \beta \]

    \[ \left( \begin{array}{c|ccccc|cc} & ab & ac & bc & bd & cd & \alpha & \beta \\ \hline \alpha & 0 & 0 & 1 & 1 & 1 & 1 & 0 \\ \beta & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ \hline z=\beta & 0 & 0 & 1 & 1 & 1 & 0 & 1 \end{array} \right) \]

    \[ z \rightarrow z + \alpha \]

    \[ \left( \begin{array}{c|ccccc|cc} & ab & ac & bc & bd & cd & \alpha & \beta \\ \hline \alpha & 0 & 0 & 1 & 1 & 1 & 1 & 0 \\ \beta & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ \hline z=\alpha+\beta & 0 & 0 & 0 & 0 & 0 & 1 & 1 \end{array} \right) \]

Notice how the right hand side now contains our vector x and indeed Ax = z = \partial(j(c)).