Non-Parametric Estimation of Manifolds from Noisy Data

Code

• github.com/aizeny/manapprox
  OfficialIn papernone★ 10

Abstract

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 R^D from a finite set of noisy samples. Assuming that the data was sampled uniformly from a tubular neighborhood of M C^k, a compact manifold without boundary, we present an algorithm that takes a point r from the tubular neighborhood and outputs p_n R^D, and T_ p_nM an element in the Grassmanian Gr(d, D). We prove that as the number of samples n the point p_n converges to p M and T_ p_nM converges to T_pM (the tangent space at that point) with high probability. Furthermore, we show that the estimation yields asymptotic rates of convergence of n^-k2k + d for the point estimation and n^-k-12k + d for the estimation of the tangent space. These rates are known to be optimal for the case of function estimation.

Tasks

Reproductions