Nerves and Towers III: Towers
An introduction to towers, an extension of mapper to the world of persistence.
Once we understand the tower, we will show that it plays nice with all of the other definitions we have constructed so far and how it allows us to naturally define a multiscale mapper.
An example of a tower is a partially ordered set (poset) where each morphism represents inclusion. For a trivial example, say \(X = \{a,b,c\}\), then we could create a tower with \(T_3 = X\), \(T_2 = \{a,b\}\), and \(T_1 = \{a\}\). We can then define inclusions \(T_1 \subset T_2 \subset T_3\), with \(T_1 \subset T_3\).
How can we construct a tower of covers. A tower of sets with inclusion doesn’t necessary have to consist of distinct layers, where each layer is a cover. We could instead be much more general, where each subset is an element and the morphisms are inclusion.
We will define a tower of covers based on inclusion maps.
- Example: Tower of covers
- Let (Ti) objects of the tower, each one a cover of (X). Then for (j>i), we define a map (t{i,j}: T_i \to T_j) if each element of (T_i) is subset of an element of (T_j).
To ensure that this map is well defined, we must set extra conditions of the covers \(T_i\). Specifically, for each element \(\tau \in T_i\), there must be no other \(\gamma \in T_i\) such that \(\tau \subset \gamma\). This ensures that any \(\tau \in T_i\) could only be mapped to one element of \(Tj\) and thus \(t{i,j}\) will be well defined. The composition of these maps holds, \(t{i,j} \circ t{j,k} = t_{i,k}\). These requirements force a sort of telescoping structure on our tower of covers.
We will define two different tower of covers that can be constructed in practice.
- Example: Splitting tower
- Begin with a single element cover of (X). Progressively split each element of the cover in half. Discard an (\mathcal{O}_i) where (\mathcal{O}_i \bigcap X = \emptyset). Continuing for (n) iterations, we have (res (\mathcal{T}) = diam(X)/n).
For ease of visualization, the images below will show the towers of two disjoint intervals.
After a certain point of splitting, there are elements of the cover that don’t contain any elements, these can be discarded.
- Example: Shrinking tower
- Begin with a cover of \(X\) with \(n\) elements each with no overlap. Then for each layer, increase the size of each element until each element individually covers \(X\). We can then use the same inclusion maps.
Note that in the picture above, the inclusion morphisms would go from right to left, i.e., the tower is upside down.
Given a tower of covers \(\mathcal{T}\), we can construct a tower of simplicial complexes by taking the nerve of each element of the cover and considering the simplicial maps induced from the inclusion maps. We will show that the induced simplicial maps do indeed create a tower.
These maps are completely determined by their behavior on the vertices. A simplicial map can be decomposed into inclusions and vertex collapses. That is, for simplicial map \(f: K \to L$, a simplex is either mapped directly into the image, or two vertices are mapped to the same vertex and the associated simplices follow directly.
The image above shows three simplicial complexes connected by simplicial maps. The blue simplicies are included, the red simplices share a preimage, and the green simplices are in the cokernal of the maps (no simplices map to these simplices). A filtration is a tower where each simplicial map is an inclusion, i.e. the sequence of complexes are nested.
We can then define the multiscale mapper as the nerve of the pullback of a tower of covers. Multiscale mapper is a tower analog of the mapper construction introduced by Dey et al in 2015. By considering a tower of covers and constructing the mapper at each layer of this tower, we can construct a tower of simplicial complexes with simplicial maps.
Using techniques developed by Dey et al in 2012, we can convert this tower of simplicial complexes into a filtration. The persistent homology of the multiscale mapper can then be computed using classic methods. Checkout Sophia for a way to compute persistence on towers.
@Book{Munkres93a, Title = {Elements of Algebraic Topology}, Annote = {SIGNATUR = 719.131}, Author = {J. R. Munkres}, Keywords = {FUNDAMENTALS mathematics}, Publisher = {Addison-Wesley}, Year = {1993},
Place = {Favoritenstrasse 9/4th Floor/1863} }
@article{Mapper, author = {G. Singh and F. M{\‘{e}}moli and G. Carlsson}, title = {Topological Methods for the Analysis of High Dimensional Data Sets and 3D Object Recognition}, journal = {Eurographics Symposium on Point-Based Graphs}, year = {2007}, url = {http://brown.edu/Research/kalisnik/mapperPBG.pdf}, timestamp = {Wed, 07 Jun 2017 14:43:09 +0200} }
@article{DBLP:journals/corr/abs-1208-5018, author = {T. K. Dey and F. Fan and Y. Wang}, title = {Computing Topological Persistence for Simplicial Maps}, journal = {CoRR}, volume = {abs/1208.5018}, year = {2012}, url = {http://arxiv.org/abs/1208.5018}, archivePrefix = {arXiv}, eprint = {1208.5018}, timestamp = {Wed, 07 Jun 2017 14:41:22 +0200}, biburl = {http://dblp.org/rec/bib/journals/corr/abs-1208-5018}, bibsource = {dblp computer science bibliography, http://dblp.org} }
@article{DBLP:journals/corr/DeyMW15, author = {T. K. Dey and F. M{\‘{e}}moli and Y. Wang}, title = {Mutiscale Mapper: {A} Framework for Topological Summarization of Data and Maps}, journal = {ArXiv}, volume = {1504.03763}, year = {2015}, url = {http://arxiv.org/abs/1504.03763}, archivePrefix = {arXiv}, eprint = {1504.03763}, timestamp = {Wed, 07 Jun 2017 14:40:57 +0200}, biburl = {http://dblp.org/rec/bib/journals/corr/DeyMW15}, bibsource = {dblp computer science bibliography, http://dblp.org} }
@ARTICLE{2017arXiv170102208K, author = { M. Kerber and H. Schreiber }, title = “{Barcodes of Towers and a Streaming Algorithm for Persistent Homology}”, journal = {ArXiv e-prints}, archivePrefix = “arXiv”, eprint = {1701.02208}, primaryClass = “math.AT”, keywords = {Mathematics - Algebraic Topology, Computer Science - Computational Geometry}, year = 2017, month = jan, adsurl = {http://adsabs.harvard.edu/abs/2017arXiv170102208K}, adsnote = {Provided by the SAO/NASA Astrophysics Data System} }
Share this post
Twitter
Google+
Facebook
Reddit
LinkedIn
StumbleUpon
Pinterest
Email