2015/12/09 by Eddie Aamari, Aamari, Eddie, Clément Levrard +1
Computer Science · Earth and Planetary Sciences · Mathematics · #Computational Geometry and Mesh Generation #Cryospheric studies and observations #FOS: Mathematics #G.1.2 #G.3 #I.3.5 #Point processes and geometric inequalities #Statistics Theory (math.ST) #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.1512.02857
openalex publication_date 2015/12/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the problem of optimality in manifold reconstruction. A random sample \mathbbXn = \X1,…,Xn\⊂ ℝD composed of points close to a d-dimensional submanifold M, with or without outliers drawn in the ambient space, is observed. Based on the Tangential Delaunay Complex, we construct an estimator M that is ambient isotopic and Hausdorff-close to M with high probability. The estimator M is built from existing algorithms. In a model with additive noise of small amplitude, we show that this estimator is asymptotically minimax optimal for the Hausdorff distance over a class of submanifolds satisfying a reach constraint. Therefore, even with no a priori information on the tangent spaces of M, our estimator based on Tangential Delaunay Complexes is optimal. This shows that the optimal rate of convergence can be achieved through existing algorithms. A similar result is also derived in a model with outliers. A geometric interpolation result is derived, showing that the Tangential Delaunay Complex is stable with respect to noise and perturbations of the tangent spaces. In the process, a decluttering procedure and a tangent space estimator both based on local principal component analysis (PCA) are studied.