We present a method to estimate the manifold dimension by analyzing the shape of simplices formed by point samples in some small neighborhoods. Approximate tangent spaces at these neighborhoods can also be reported. Let P be a set of point samples drawn from a manifold M ⊂ R^d with dimension m according to a Poisson distribution with parameter λ. Both M and λ are unknown to our algorithm. For sufficiently large λ, given any integer k ≥ 1, our algorithm correctly outputs m in O(kdm³∣P∣ log ∣P∣) time with probability 1-O( λ^-κβ) for some constant β ∈ (0,1). It holds with the same probability that the angular error of each approximate tangent space reported is O(ε), where ε is a value depending on M, λ and m and lim_λ→∞ε= 0. We experimented with a practical variant of our algorithm and demons...[ Read more ]

We present a method to estimate the manifold dimension by analyzing the shape of simplices formed by point samples in some small neighborhoods. Approximate tangent spaces at these neighborhoods can also be reported. Let P be a set of point samples drawn from a manifold M ⊂ R^d with dimension m according to a Poisson distribution with parameter λ. Both M and λ are unknown to our algorithm. For sufficiently large λ, given any integer k ≥ 1, our algorithm correctly outputs m in O(kdm³∣P∣ log ∣P∣) time with probability 1-O( λ^-κβ) for some constant β ∈ (0,1). It holds with the same probability that the angular error of each approximate tangent space reported is O(ε), where ε is a value depending on M, λ and m and lim_λ→∞ε= 0. We experimented with a practical variant of our algorithm and demonstrated that it does not require very high sampling density and it is competitive with several previous methods.