Non-Parametric Estimation of Manifolds from Noisy Data

A common observation in data-driven applications is that high dimensional data has a low intrinsic dimension, at least locally. In this work, we consider the problem of estimating a d dimensional sub-manifold of ℝD from a finite set of noisy samples. Assuming that the data was sampled uniformly from a tubular neighborhood of M∈ Ck, a compact manifold without boundary, we present an algorithm that takes a point r from the tubular neighborhood and outputs hat pn∈ ℝD, and widehatThat pnM an element in the Grassmanian Gr(d, D). We prove that as the number of samples n→∞ the point hat pn converges to p∈ M and widehatThat pnM converges to TpM (the tangent space at that point) with high probability. Furthermore, we show that the estimation yields asymptotic rates of convergence of n^-frack2k + d for the point estimation and n^-frack-12k + d for the estimation of the tangent space. These rates are known to be optimal for the case of function estimation.