Stability and minimax optimality of tangential Delaunay complexes for manifold reconstruction

DOI10.1007/S00454-017-9962-ZzbMATH Open1408.62103arXiv1512.02857OpenAlexW2963162615WikidataQ130194604 ScholiaQ130194604MaRDI QIDQ1650797FDOQ1650797

Clément Levrard, Eddie Aamari

Publication date: 13 July 2018

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Abstract: We consider the problem of optimality in manifold reconstruction. A random sample $mathbb{X}_n=left{X}_1,ldots,X_{n}ightsubsetmathbb{R}^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 $hatM$ that is ambient isotopic and Hausdorff-close to $M$ with high probability. The estimator $hatM$ 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.

Full work available at URL: https://arxiv.org/abs/1512.02857

zbMATH Keywords

principal component analysisminimax optimalitysubmanifoldsmanifold reconstructiondeclutteringlocal principal component analysistangent space estimationtangential Delaunay complexes

Mathematics Subject Classification ID

Factor analysis and principal components; correspondence analysis (62H25) Estimation in multivariate analysis (62H12) Global submanifolds (53C40)

Cites Work

• Asymptotical minimax recovery of sets with smooth boundaries
• Finding the homology of submanifolds with high confidence from random samples
• Convergence rates for persistence diagram estimation in topological data analysis
• Curvature Measures
• On boundary estimation
• The Rotation of Eigenvectors by a Perturbation. III
• Title not available (Why is that?)
• Convergence of estimates under dimensionality restrictions
• Title not available (Why is that?)
• A Bennett concentration inequality and its application to suprema of empirical processes
• Community detection in dense random networks
• Manifold reconstruction in arbitrary dimensions using witness complexes
• De-noising by soft-thresholding
• Title not available (Why is that?)
• Building triangulations using ε-nets
• Rates of convergence for random approximations of convex sets
• Global inversion of functions: An introduction
• Theory of Classification: a Survey of Some Recent Advances
• Manifold estimation and singular deconvolution under Hausdorff loss
• Gauss equation and injectivity radii for subspaces in spaces of curvature bounded above
• Manifold reconstruction from point samples
• Title not available (Why is that?)
• Curve and Surface Reconstruction
• Minimax Manifold Estimation
• Tight minimax rates for manifold estimation under Hausdorff loss
• Riemannian Simplices and Triangulations
• Manifold reconstruction using tangential Delaunay complexes
• Title not available (Why is that?)
• Multiscale dictionary learning: non-asymptotic bounds and robustness
• Title not available (Why is that?)

Cited In (15)

• Reconstruction of manifold embeddings into Euclidean spaces via intrinsic distances
• Universally consistent estimation of the reach
• On boundary detection
• Estimating the reach of a manifold via its convexity defect function
• Nonasymptotic rates for manifold, tangent space and curvature estimation
• The reach of subsets of manifolds
• Tangent space and dimension estimation with the Wasserstein distance
• A \(k\)-points-based distance for robust geometric inference
• Measure estimation on manifolds: an optimal transport approach
• Data analysis from empirical moments and the Christoffel function
• Minimax boundary estimation and estimation with boundary
• Title not available (Why is that?)
• Minimax adaptive estimation in manifold inference
• The Bottleneck Degree of Algebraic Varieties
• Adversarial manifold estimation

This page was built for publication: Stability and minimax optimality of tangential Delaunay complexes for manifold reconstruction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1650797)