Testing the manifold hypothesis

Charles Fefferman, Sanjoy Mitter, Hariharan Narayanan

Research output: Contribution to journalArticlepeer-review

43 Scopus citations

Abstract

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 supported on the unit ball of a separable Hilbert space H. Let G(d.V.T)be the set of submanifolds of the unit ball of H whose volume is at most Vand reach (which is the supremum of all rsuch that any point at a distance less than rhas a unique nearest point on the manifold) is at least T. Let L(M.P) denote the mean-squared distance of a random point from the probability distribution Pto M. We obtain an algorithm that tests the manifold hypothesis in the following sense. The algorithm takes i.i.d. random samples from Pas input and determines which of the following two is true (at least one must be): There exists M ∈ G(d,CV,T/C) such that L(M,P)≤C∈ There exists no M ∈ G(d,V/C,CT) such that L(M,P) ≤ ∈/C The answer is correct with probability at least 1-δ.

Original languageEnglish (US)
Pages (from-to)983-1049
Number of pages67
JournalJournal of the American Mathematical Society
Volume29
Issue number4
DOIs
StatePublished - Oct 2016

All Science Journal Classification (ASJC) codes

  • Mathematics(all)
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Testing the manifold hypothesis'. Together they form a unique fingerprint.

Cite this