About Reach Estimation: Geometric Stability and Minimax Bounds


Seminar Modèles et Algorithmes Déterministes: EDP-MOISE-MGMI

19/01/2017 - 11:00 Mr Eddie Aamari (Université Paris Sud & INRIA) Salle 106 - Batiment IMAG

Various problems within computational geometry and manifold learning encode geometric regularity through the so-called reach, a generalized convexity parameter. The reach $\\tau_M$ of a submanifold $M \\subset \\R^D$ is the maximal offset radius on which the projection onto $M$ is well defined. The quantity $\\tau_M$ renders a certain minimal scale of $M$, giving bounds on both maximum curvature and possible bottleneck structures. In this talk, we will study the geometry of the reach through an approximation theory perspective. We present new geometric results on the reach of submanifolds without boundary. An estimator $\\hat{\\tau}_n$ of $\\tau_M$ will be described, in an idealized i.i.d. framework where tangent spaces are known. The estimator $\\hat{\\tau}_n$ is showed to achieve uniform expected loss bounds over a $\\mathcal{C}^3$-like model. Minimax upper and lower bounds are derived. We will conclude with an extension to a model in which tangent spaces are unknown.