Topological data analysis

Motivation:

Topological data analysis computes and analyses topological features of the point clouds by constructing and studying a simplicial representation of the underlying topological structure. The enthusiasm that followed the initial successes of topological data analysis was curbed by the computational cost of constructing such simplicial representations. The lazy witness complex is a computationally feasible approximation of the underlying topological structure of a point cloud. It is built in reference to a subset of points, called landmarks, rather than considering all the points as in the Vietoris-Rips complexes.

Contributions:

In collaboration with Debabrota Basu and Stephane Bressan, I adopt the notion of cover to define \(\epsilon\)-net. We prove that \(\epsilon\)-net, as a choice of landmarks, is an \(\epsilon\)-approximate representation of the point cloud in Hausdorff metric. More importantly, the induced lazy witness complex is a \(3\)-approximation of the induced Vietoris-Rips complex. The implication of this result is that, persistence of topological features computed using \(\epsilon\)-net as landmark is guaranteed to deviate no more than \(\log(3)\) away (in Bottleneck distance) from the same computed using Vietoris-Rips. Finally, we propose three algorithms to construct \(\epsilon\)-net of a point cloud.

In a subsequent paper, we extended our results on graph data. A new bound on the size of \(\epsilon\)-net of a connected unweighted graph is given.

Publication/Preprints:

If you are interested in the details, please refer to my following papers-

• Topological Data Analysis with \(\epsilon\)-net Induced Lazy Witness Complex, DEXA 2019.
• \(\epsilon\)-net Induced Lazy Witness Complexes on Graphs, ATDA workshop, ECML-PKDD 2019.