Topological data analysis

Approximating Persistence homological features using \(\epsilon\)-net and lazy witness complex

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-

<!-- See https://www.debugbear.com/blog/responsive-images#w-descriptors-and-the-sizes-attribute and 
  https://developer.mozilla.org/en-US/docs/Learn/HTML/Multimedia_and_embedding/Responsive_images for info on defining 'sizes' for responsive images-->

  <source class = "responsive-img-srcset" srcset="
  /naheed/assets/img/1-480.webp 480w,
  /naheed/assets/img/1-800.webp 800w,
  /naheed/assets/img/1-1400.webp 1400w,
  " 
   sizes="95vw" 
  type="image/webp"/>

<img
  src="/naheed/assets/img/1.jpg"
  class="img-fluid rounded z-depth-1"
  width="100%"
  height="auto"
  
  
  
  
  
  title="example image"
  
  onerror="this.onerror=null; $('.responsive-img-srcset').remove();"
/>

</picture>

</figure>

</div>
<div class="col-sm mt-3 mt-md-0">
    <figure>

</figure>

</div>
<div class="col-sm mt-3 mt-md-0">
    <figure>

</figure>

</div>

</div>

Caption photos easily. On the left, a road goes through a tunnel. Middle, leaves artistically fall in a hipster photoshoot. Right, in another hipster photoshoot, a lumberjack grasps a handful of pine needles.
This image can also have a caption. It's like magic.

You can also put regular text between your rows of images. Say you wanted to write a little bit about your project before you posted the rest of the images. You describe how you toiled, sweated, bled for your project, and then… you reveal its glory in the next row of images.

You can also have artistically styled 2/3 + 1/3 images, like these.

The code is simple. Just wrap your images with <div class="col-sm"> and place them inside <div class="row"> (read more about the Bootstrap Grid system). To make images responsive, add img-fluid class to each; for rounded corners and shadows use rounded and z-depth-1 classes. Here’s the code for the last row of images above:

<div class="row justify-content-sm-center">
    <div class="col-sm-8 mt-3 mt-md-0">
        {% include figure.html path="assets/img/6.jpg" title="example image" class="img-fluid rounded z-depth-1" %}
    </div>
    <div class="col-sm-4 mt-3 mt-md-0">
        {% include figure.html path="assets/img/11.jpg" title="example image" class="img-fluid rounded z-depth-1" %}
    </div>
</div>