CSE 5559: Computational Topology and Data Analysis

Tamal K Dey

Home
Research pages(TBA)
List of Papers (partially constructed)
Class Schedule



Time: SP 2017, Mon 10:20--12:25pm, DL 480

Final Presentations
TBA
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 particular growth in the area of data analysis. The application of topological techniques to traditional data analysis, which before has mostly developed on a statistical setting, has opened up new opportunities. This course is intended to cover this aspect of computational topology along with the developments of generic techniques for various topology-centered problems.

  • Objectives
    • Be familiar with basics in topology that are useful for computing with data
    • Master a subset of algorithms for computing: Betti number, topological persistence, homology cycles, Reeb graphs, Laplace spectra from data
    • Be familiar with how to design algorithms for problems in applications dealing with data
    • Be familiar with how to research the background of a topic in data analysis, machine learning
  • Prerequisites: CSE6331; or grad standing and permission of instructor
  • Materials (Transparencies)
  • Text and class material 1. Computational topology, Herbert Edelsbrunner and John L. Harer, AMS
    2. Curve and surface reconstruction: Algorithms with mathematical analysis, Tamal K. Dey, Cambridge U. Press
    3. Elements of Algebraic Topology, James R. Munkres, Addison-Wesley
    4. Algebraic Topology, Allen Hatcher, Cambridge U. Press
    5. Class materials and notes posted on this web-site
    Topics

    1. Basics of Topology;

    a. Topological spaces, metric space topology [Chapter 1 & 12 of this book] [Notes]
    b. Maps: homeomorphisms, homotopy equivalence, isotopy [Notes]
    c. Manifolds [Notes]

    2. Complexes on data
    a. Simplicial complexes [Munkres][Notes]
    b. Chech complexes, Vietoris-Rips complexes [Notes]
    c. Witness complexes [deSilva-Carlsson04 paper][Notes]
    d. Graph induced complexes  [DeyFanWang13 paper][Notes]

    3. Homology
    a. Chains, boundaries, homology groups, betti numbers [Notes, Munkres book]
    c. Induced maps among homology groups [Notes, Munkres book]
    d. Relative homology groups [Notes, Munkres book]
    e. Local homology groups [Notes, Munkres book]
    f. Cohomology groups [Notes, Hatcher book]

    4. Topological persistence
    a. Filtrations, Persistent homology [Notes, C-VII Edelsbrunner-Harer book]
    b. Persistence algorithm [Notes, C-VII Edelsbrunner-Harer book, EdelsbrunneLetscherZomorodian02 paper introduced topological persistence, ZomorodianCarlsson04 paper brings algebra into persistence]
    c. Persistence diagram [Notes, C-VIII Edelsbrunner-Harer H book, Cohen-SteinerEdelsbrunnerHarer07 paper proves the stabilty of persistence]
    d. Variations on persistence algorithm [Notes, CarlssonSilvaMorozov09 paper on zigzag persistence, DeyFanWang13SM paper on cohomology persistence]

    5. Computing Betti numbers
    a. Data from surfaces and volumes in three dimensions [Notes]
    b. Data from manifolds in higher dimesnions [Notes]

    6. Reconstruction from data
    a. Basics of reconstruction [ Notes, Chapter 1, Dey-book]
    b.Curve reconstruction from data [Notes, Chapter 2, Dey-book, AmentaBernEppstein98 paper introduces LFS, epsilon-sampling, DeyKumar99 paper on a very simple algorithm for curve reconstruction]
    c. Surface reconstruction in three dimensions from data [Notes, Chapter 3-4, Dey-book, Amenta-Bern99 paper pioneering provable surface reconstruction, AmentaChoiDeyLeekha01 paper proving the homeomorphism for Cocone algorithm]
    d. Manifold reconstruction in high dimensions from data [Notes, NiyogiSmaleWeinberger06 paper on probabilistic setting, ChazalCohen-SteinerLieutier09 paper on theory of compacts, ChengDeyRamos05 paper on anomalies of restricted Delaunay and its rectification by weighted Delaunay]

    7. Topology inference from data
    a. Computing homology from data [Notes, ChazalOudot08 paper on homology inference, CCGGO09 paper on interleaving of persistence modules]
    b. Sparsification to handle big data [Presentation slides][Sheehy12 paper on sparsified Rips complex, DeyFanWang13 paper on subsampling]

    8. Computing optimized homology cycles
    a. Computing shortest basis cycles on surfaces [EricksonWhittlesey05 paper on greedy basis construction]
    b. Computing shortest basis cycles from data points [Presentation slides, DeySunWang09 paper on shortest basis from point data]
    c. Localizing a cycle class [Presentation slides, DeyHiraniKrishnamoorthy10 paper on LP algorithm for shortest homologous cycle]

    9. Reeb graphs from data
    a. Reeb graphs [Notes, C-MEHNP paper on loops in Reeb graphs]
    b. Approximating Reeb graphs from data [Notes, DeyWang11 paper on approximation of Reeb graphs from data]

    10. Topology of Laplace operators, spectra approximation
    a. Laplace operator [Notes]
    b. Approximating Laplace from data [Notes, BelkinNiyogi03 paper on approximating Laplace, BelkinSunWang09 paper on PCD Laplace]
    c. Stabilty of Laplace spectra [Notes, DeyWang10 paper on spectra stability]

  • Grading
  • A presentation on a TDA topic
    50%
    Midterm
    40%
    Participation
    10%