Abstract: Harnessing the power of data has been a driving force for computing, especially in recent years when breakthroughs in Data Science enable computers to perform tasks never seen before. However, the non-vectorized or even non-Euclidean nature of certain data with complex structures poses new challenges to the community, calling for techniques that can reveal hidden structures and high-order connectivity for data. In this talk, I will discuss our recent work on Topological Data Analysis (TDA), an emerging research field aiming at understanding data through the lens of topology.

 

Firstly, we investigate the problem of computing optimal representatives for persistent homology (a cornerstone in TDA). This work is motivated by the observation that traditional persistent homology only marks the birth and death of homological features without concrete representatives for the features. We thereby introduce the definition of persistent cycles as the representatives, which provide helpful visualization and reveal the geometry for the topological summaries. For computing optimal persistent cycles (providing the tightest representation), we prove the NP-hardness in general dimensions and propose algorithms for a special but useful class of inputs called manifolds.

 

Secondly, we look into a powerful extension of persistent homology called zigzag persistence, which enables shrinking of topological spaces besides growing and is especially useful when deletions of pieces are needed (e.g., a dynamical sequence of changing graphs). In this line of work, we propose near-linear algorithms for graphs, improving the previously known super-quadratic complexity. We also propose update algorithms for local changes on input filtrations, generating more advanced signatures called vines and vineyard.

 

As an application of the topological signatures, I will also discuss a collaborative work with researchers from Materials Science, where we devised a topological noise filter for microstructure segmentation for 3D images.

 

(These are joint work with my PhD advisor Tamal Dey.)

Short Bio: Tao Hou is a PhD candidate in the Department of Computer Science at Purdue University under the supervision of Prof. Tamal Dey. His research interest is computational topology and topological data analysis, a field at the intersection of computer science and mathematics. His research combines topology, geometry, algebra with algorithms and data analysis. Before transferring to Purdue with his advisor, he spent four years as a PhD student in the Department of Computer Science and Engineering at The Ohio State University. Prior to that, he got his bachelor’s and master’s degrees, and worked in the industry as an engineer, in China. Please see Tao Hou’s homepage: https://taohou01.github.io/ for more information about him.