Stability and minimax optimality of tangential Delaunay complexes for manifold reconstruction

DOI10.1007/S00454-017-9962-ZMaRDI QIDQ1650797zbMATHOpenAlexWikidataFDO

Authors Eddie Aamari, Clément Levrard

Publication date 13 July 2018

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

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)

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.

Recommendations

• Manifold reconstruction using tangential Delaunay complexes
• Manifold reconstruction using tangential Delaunay complexes
• Minimax adaptive estimation in manifold inference
• Minimax manifold estimation
• Nonasymptotic rates for manifold, tangent space and curvature estimation

Cites work

• scientific article; zbMATH DE number 5506223 (Why is no real title available?)
• scientific article; zbMATH DE number 52737 (Why is no real title available?)
• scientific article; zbMATH DE number 3280855 (Why is no real title available?)
• A Bennett concentration inequality and its application to suprema of empirical processes
• Asymptotical minimax recovery of sets with smooth boundaries
• Building triangulations using \({\epsilon}\)-nets
• Community detection in dense random networks
• Concentration inequalities. A nonasymptotic theory of independence
• Convergence of estimates under dimensionality restrictions
• Convergence rates for persistence diagram estimation in topological data analysis
• Curvature Measures
• Curve and Surface Reconstruction
• De-noising by soft-thresholding
• Declutter and resample: towards parameter free denoising
• Finding the homology of submanifolds with high confidence from random samples
• Gauss equation and injectivity radii for subspaces in spaces of curvature bounded above
• Global inversion of functions: An introduction
• Manifold estimation and singular deconvolution under Hausdorff loss
• Manifold reconstruction from point samples
• Manifold reconstruction in arbitrary dimensions using witness complexes
• Manifold reconstruction using tangential Delaunay complexes
• Minimax manifold estimation
• Multiscale dictionary learning: non-asymptotic bounds and robustness
• On boundary estimation
• Rates of convergence for random approximations of convex sets
• Riemannian simplices and triangulations
• Spectral clustering based on local PCA
• The Rotation of Eigenvectors by a Perturbation. III
• Theory of Classification: a Survey of Some Recent Advances
• Tight minimax rates for manifold estimation under Hausdorff loss

Cited in

(21)

• Manifold reconstruction and denoising from scattered data in high dimension
• Measure estimation on manifolds: an optimal transport approach
• The reach of subsets of manifolds
• Nonasymptotic rates for manifold, tangent space and curvature estimation
• Estimating the reach of a manifold via its convexity defect function
• Data analysis from empirical moments and the Christoffel function
• Recovering the homology of immersed manifolds
• On boundary detection
• A \(k\)-points-based distance for robust geometric inference
• scientific article; zbMATH DE number 7625193 (Why is no real title available?)
• Reconstruction of manifold embeddings into Euclidean spaces via intrinsic distances
• The bottleneck degree of algebraic varieties
• Delaunay-like triangulation of smooth orientable submanifolds by \(\ell_1\)-norm minimization
• Tangent space and dimension estimation with the Wasserstein distance
• Manifold reconstruction using tangential Delaunay complexes
• Minimax adaptive estimation in manifold inference
• Manifold reconstruction using tangential Delaunay complexes
• Tangent estimation from point samples
• Minimax boundary estimation and estimation with boundary
• Adversarial manifold estimation
• Universally consistent estimation of the reach

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)