Reconstruction of a Riemannian Manifold from Noisy Intrinsic Distances

We consider the reconstruction of a manifold (or, invariant manifold learning), where a smooth Riemannian manifold M is determined from the intrinsic distances (that is, geodesic distances) of points in a discrete subset of M. In the studied problem, the Riemannian manifold (M, g) is considered as an abstract metric space with intrinsic distances, not as an embedded submanifold of an ambient Euclidean space. Let {X₁, X₂, . . ., X_N} be a set of N sample points sampled randomly from an unknown Riemannian M manifold. We assume that we are given the numbers D_jk = d_M(X_j, X_k) + η_jk, where j, k ∊ {1, 2, . . ., N}. Here, d_M(X_j, X_k) are geodesic distances, and η_jk are independent, identically distributed random variables such that the exponential moment Εe^|ηjk| is finite. We show that when N ∼ C₀δ^-3n(log(1/δ))⁵ log(1/θ), with the probability 1 - θ, it is possible to construct a manifold that approximates the Riemannian manifold (M, g) with the error δ. Here, C₀ depends on the intrinsic dimension n of M and the bounds for the diameter, sectional curvature, the injectivity radius of (M, g), and the the exponential moment of the noise. This problem is a generalization of the geometric Whitney problem with random measurement errors. We also consider the case when the information on the noisy distance D_jk of points X_j and X_k is missing with a certain probability. In particular, we consider the case when we have no information on points that are far away.