3
$\begingroup$

I know different type of simplicial complexes like Rips, Alpha, witness, etc. I like to know more about if we have a point cloud which one of them should I use? How do we compare their performance on a point cloud? and I wonder whether they have different applications? and I can make different barcode plot based on these filteration on the same point cloud which I don't know which one is valid.

New contributor
abolfazl taghribi is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
  • 1
    $\begingroup$ In higher dimensions the answer is easy: alpha and cech are a pain to compute because the smallest-enclosing-ball problem and hyperplane intersections get difficult to compute. On the other hand, Rips is easy to compute but huge (particularly when compared to alpha, which has its dimension bounded by the ambient one). $\endgroup$ – Vidit Nanda May 14 at 14:39
3
$\begingroup$

Piggybacking on the answers by Vidit Nanda and APR, my summary would be as follows:

The Cech complex and the alpha are typically what one would like to be able to compute. This is because the persistent homology of either the Cech complex or the alpha complex is exactly the same as the persistent homology of the union of the balls. The same is true for homotopy types: by the nerve lemma, either the Cech complex or the alpha complex have the same homotopy type as the union of the balls. The difference between the Cech complex and the alpha complex is that the alpha complex is smaller: it is also a subset of the Delaunay triangulation, and hence of dimension bounded from above by the dimension of the ambient space.

However, as the ambient dimension grows (say prior to reaching ambient dimension 10 I would guess), it becomes prohibitively difficult to compute the Cech or the alpha complex, as Vidit Nanda writes. For this reason, people nowadays often compute Vietoris-Rips complexes instead. Vietoris-Rips complexes are not homotopy equivalent to the union of the balls anymore. Although there is no such nerve lemma for Vietoris-Rips complexes, there are partial reconstruction results along these lines, starting with research by Hausmann and Latschev, and continuing to present-day research. The Vietoris-Rips complex computations are much easier because the ambient dimension does not hinder computations, as the Vietoris-Rips complex depends only on pairwise distances.

Witness complexes are an approximation to Cech, Alpha, or Vietoris-Rips complexes which only use a subset of the data points as vertices --- the remaining data points are used to help decide when higher-dimensional simplices are added. Witness complexes can produce much smaller simplicial complexes, which one still hopes approximate the persistent homology of Cech, Alpha, or Vietoris-Rips. A decade ago witness complexes were necessary to do large computations; this is perhaps less the case now as we have gotten more efficient at computing the persistent homology of Vietoris-Rips complexes.

$\endgroup$
3
$\begingroup$

The state of the art on this question is, for better or worse, more art than science (at least to the best of my knowledge). If you compute persistent homology with any of these complexes (using some sort of filtration), then it is 'valid' as the persistent homology of the particular complex and filtration that you chose. Whether the features you're interested in are somehow reflected in that persistent homology, however, is another question.

That said, the Rips complex currently seems to be most widely used when computing persistent homology of point clouds, due to fast, available software (https://github.com/Ripser/ripser), scalability with respect to the ambient dimension, and the lack of choices involved (one doesn't need to choose witness points, for instance, as in the witness complex).

$\endgroup$

Your Answer

abolfazl taghribi is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.