TR-2010-07

Two extensions to Manifold Learning Algorithms using \alpha-Complexes

Maia Fraser. 20 October, 2010.
Communicated by John Goldsmith.

Abstract

A large body of work has grown up over the past decade dealing with ways of recovering topological invariants of a submanifold M in R^ N from a point cloud Z associated to M most of these use alpha-complexes and assume Z is from M itself (though some consider base spaces more general than manifolds), Niyogi et al use Cech complexes and consider more general sampling. In addition, most compute exclusively homological invariants, though homotopy equivalence results exist in papers by Niyogi et al and Chazal et al. The purpose of this report is to briefly point out two simple extensions which can be made to some of the above algorithms. The first consists of a simple pre-processing step (due to Niyogi et al) which may be added to many of the other algorithms to extend them to noisy data sampled from a distribution on all of R^ N, centred but not necessarily supported on M. This extension also results in statements regarding the homotopy equivalence of the computed simplicial complex to M. The second extension is a brief comment describing how the fundamental group of a simplicial complex may be computed. In particular, using the homotopy equivalence guarantee obtained by our first extension one obtains a similar guarantee on isomorphism of the computed fundamental group and that of M. We remark, however, that since this group is not in general abelian, its triviality is not decidable.

Original Document

The original document is available in PDF (uploaded 20 October, 2010 by John Goldsmith).