F. Chazal, S. Y. Oudot. Towards Persistence-Based Reconstruction in Euclidean Spaces. Proc. 24th ACM Sympos. on Comput. Geom., pages 232-241, 2008 (full version).
Manifold reconstruction has been extensively studied
for the last decade or so, especially in two and three
dimensions. Recent advances in higher dimensions have led to new
methods to reconstruct large classes of compact subsets of
$R^d$. However, the complexities of these methods scale up
exponentially with d, making them impractical in medium or high
dimensions, even on data sets of low intrinsic dimensionality.
In this paper, we introduce a novel approach that stands in-between
classical reconstruction and topological estimation, and whose
complexity scales up with the intrinsic dimension of the data. Our
algorithm combines two paradigms: greedy refinement, and topological
persistence. Given a point cloud in $R^d$, we build a set of
landmarks iteratively, while maintaining a nested pair of abstract
complexes, whose images in $R^d$ lie close to the data, and whose
persistent homology eventually coincides with the homology of the
underlying shape. When the data points are densely
sampled from a smooth $m$-submanifold $sss$ of $R^d$, our method
retrieves the homology of $sss$ in time at most $c(m)n^5$, where $n$
is the size of the input and $c(m)$ is a constant depending solely on~$m$.
To prove the correctness of our algorithm, we investigate on v Cech,
Rips, and witness complex filtrations in Euclidean spaces. More
precisely, we show how previous results on unions of balls can be
transposed to v Cech filtrations, and from there to Rips and witness
complex filtrations. Finally, investigating further on witness
complexes, we quantify a conjecture of Carlsson and de Silva, which
states that witness complex filtrations should have cleaner
persistence barcodes than v Cech or Rips filtrations, at least on
smooth submanifolds of Euclidean spaces.
@inproceedings{co-tpbr-08 , author = "F. Chazal and S. Y. Oudot" , title = "Towards Persistence-Based Reconstruction in {Euclidean} Spaces" , booktitle = "Proc. 24th ACM Sympos. Comput. Geom." , year = 2008 , pages = "232--241" } |