Home
Research pages(TBA)
List of Papers (partially constructed)
Class Schedule
Time: SP 2017, Mon 10:2012: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 topologycentered 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, AddisonWesley
4. Algebraic Topology, Allen Hatcher, Cambridge U. Press
5. Class materials and notes posted on this website

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, VietorisRips complexes [Notes]
c. Witness complexes [deSilvaCarlsson04 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, CVII EdelsbrunnerHarer book]
b. Persistence algorithm [Notes, CVII EdelsbrunnerHarer book, EdelsbrunneLetscherZomorodian02 paper introduced topological persistence, ZomorodianCarlsson04 paper brings algebra into persistence]
c. Persistence diagram [Notes, CVIII EdelsbrunnerHarer H book, CohenSteinerEdelsbrunnerHarer07 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, Deybook]
b.Curve reconstruction from data [Notes, Chapter 2, Deybook, AmentaBernEppstein98 paper introduces LFS, epsilonsampling, DeyKumar99 paper on a very simple algorithm for curve reconstruction]
c. Surface reconstruction in three dimensions from data [Notes, Chapter 34, Deybook, AmentaBern99 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, ChazalCohenSteinerLieutier09 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, CMEHNP 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%

