Testing the manifold hypothesis

The hypothesis that high dimensional data tend to lie in the vicinity of a low dimensional manifold is the basis of manifold learning. The goal of this paper is to develop an algorithm (with accompanying complexity guarantees) for testing the existence of a manifold that fits a probability distribution supported in a separable Hilbert space, only using i.i.d. samples from that distribution. More precisely, our setting is the following. Suppose that data are drawn independently at random from a probability distribution P P supported on the unit ball of a separable Hilbert space H H . Let G ( d , V , τ ) G(d, V, τ ) be the set of submanifolds of the unit ball of H H whose volume is at most V V and reach (which is the supremum of all r r such that any point at a distance less than r r has a unique nearest point on the manifold) is at least τ τ . Let L ( M , P ) L(M, P) denote the mean-squared distance of a random point from the probability distribution P P to M M . We obtain an algorithm that tests the manifold hypothesis in the following sense. The algorithm takes i.i.d. random samples from P P as input and determines which of the following two is true (at least one must be): There exists