Book : Computational Topology for Data Analysis
(To be published by Cambridge University Press)

Tamal K Dey
Department of Computer Science, Purdue University, IN

Yusu Wang
Halicioglu Data Science Institute, UC San Diego, CA

Copyright: Tamal Dey and Yusu Wang 2016-2021

Get an electronic copy

This material has been / will be published by Cambridge University Press as Computational Topology for Data Analysis by Tamal Dey and Yusu Wang. This pre-publication version is free to view and download for personal use only. Not for re-distribution, re-sale, or use in derivative works.

Computational topology has played a synergistic role in bringing together research work from computational geometry, algebraic topology, data analysis, and many other related scientific areas. In recent years, the field has undergone an explosieve growth in the area of data analysis. The application of topological techniques to traditional data analysis, which has earlier developed mostly on a statistical setting, has opened up new opportunities. This book is intended to cover this aspect of computational topology along with the developments of generic techniques for various topology-centered problems. Since the development of persistent homology, the area has grown both in its methodology and applicability. One consequence of this growth has been the development of various algorithms which intertwine with the discoveries of various mathematical structures in the context of processing data. The purpose of this book is to capture these algorithmic developments with the associated mathematical guarantees.

  • Contents
  • Chapter 1: Basic Topology
    a. Topological spaces, metric space topology
    b. Maps: homeomorphisms, homotopy equivalence, isotopy
    c. Manifolds
    d. Functions on smooth manifolds
    e. Notes and Exercises

    Chapter 2 (i) . Complexes
    a. Simplicial complexes
    b. Nerves, Cech and Vietoris-Rips complexes
    c. Sparse complexes (Delaunay, Alpha, Witness)
    d. Graph induced complexes
    e. Notes and Exercises

    Chapter 2 (ii). Homology
    a. Chains, cycles, boundaries, homology groups, Betti numbers
    b. Induced maps among homology groups
    c. Relative homology groups
    d. Singular homology groups
    e. Cohomology groups
    f. Notes and Exercises

    Chapter 3. Topological persistence
    a. Filtrations, Persistent homology
    b. Persistence diagram
    c. Bottleneck distance and its computation
    d. Persistence algorithm, matrix reduction, clearing, cohomology algorithm
    e. Persistence modules
    f. Persistence for PL-functions
    g. Notes and Exercises

    Chapter 4. General Persistence (Zigzag)
    a. Towers, Persistence modules from simplicial maps
    b. Algorithm for towers with annotations
    c. Zigzag persistence and algorithms
    d. Level Set persistence
    e. Extended persistence
    f. Notes and Exercises

    Chapter 5. Generators and Optimality
    a. Greedy algorithm for optimal (H_1)-basis
    b. Computing optimal cycle in a given class
    d. Computing optimal persistent cycles
    e. Notes and Exercises

    Chapter 6. Topological analysis of point clouds
    a. Rips and Cech filtrations on PCD
    b. Sparsified Rips filtrations
    c. Homology inference from PCD
    d. Homology inference for scalar fields
    e. Notes and Exercises

    Chapter 7. Reeb graphs

    a. Reeb graphs: Definitions and properties
    b. Algorithms in the PL-setting
    c. Homology groups for Reeb graphs
    d. Distances for Reeb graphs
    e. Notes and Exercises

    Chapter 8. Topological analysis of graphs
    a. Topological summaries for graphs
    b. Graph comparisons
    c. Topological invariants for directed graphs
    d. Computing persistent path homology
    e. Notes and Exercises

    Chapter 9. Nerve, Cover, Mapper
    a. Cover and Nerve
    b. Persistent H_1-classes
    c. Mapper and multiscale mapper
    d. Stability of (multiscale) mapper
    e. Approximating multiscale mapper
    f. Notes and Exercises

    Chapter 10. Discrete Morse Theory and Applications a. Discrete Morse function
    b. Discrete Morse Vector Field (DMVF)
    c. Persistence Based DMVF
    d. Stable and unstable manifolds
    e. Graph reconstruction using DMVF
    f. Application to road network and neuronal reconstrcution
    g. Notes and Exercises

    Chapter 11. Multiparameter persistence and decomposition
    a. Multiparameter persistence modules
    b. Presentation
    c. Presentation matrix: simplification and diagonalization
    d. Total diagonalization algorithm
    e. Computing presentations
    f. Invariants
    g. Notes and Exercises

    Chapter 12. Multiparameter persistence and distances
    a. Persistence modules from categorial viewpoint
    b. Interleaving distance
    c. Matching distance and its computation
    d. Bottleneck distance and its computation
    e. Notes and Exercises

    Chapter 13. Topological persistence and Machine learning
    a. Feature vectorization of persistence diagrams
    b. Optimizing topological loss function
    c. Statistical treatment of topological summaries
    d. Notes and Exercises
  • For errata, please communicate to and