Testing the manifold hypothesis
Journal of the American Mathematical Society · 09.02.2016 · 29 (4) · 983-1049
DOI: 10.1090/jams/852 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of the American Mathematical Society, online erschienen am 09.02.2016. Verfasst von Charles Fefferman und 2 weiteren Autor:innen. Die Arbeit wurde bisher 363-mal zitiert (Crossref) und nennt 56 Literaturangaben. Gefördert von: National Science Foundation.
Abstract (Originalsprache)
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 \mathcal {P} supported on the unit ball of a separable Hilbert space H \mathcal {H} . Let G ( d , V , τ ) \mathcal {G}(d, V, \tau ) be the set of submanifolds of the unit ball of H \mathcal {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 τ \tau . Let L ( M , P ) \mathcal {L}(\mathcal {M}, \mathcal {P}) denote the mean-squared distance of a random point from the probability distribution P \mathcal {P} to M \mathcal {M} . We obtain an algorithm that tests the manifold hypothesis in the following sense. The algorithm takes i.i.d. random samples from P \mathcal {P} as input and determines which of the following two is true (at least one must be): There exists M ∈ G ( d , C V , τ C ) \mathcal {M} \in \mathcal {G}(d, CV, \frac {\tau }{C}) such that L ( M , P ) ≤ C ϵ . \mathcal {L}(\mathcal {M}, \mathcal {P}) \leq C {\epsilon }. There exists no M ∈ G ( d , V / C , C τ ) \mathcal {M} \in \mathcal {G}(d, V/C, C\tau ) such that L ( M , P ) ≤ ϵ C . \mathcal {L}(\mathcal {M}, \mathcal {P}) \leq \frac {\epsilon }{C}. The answer is correct with probability at least 1 − δ 1-\delta .
Förderung
- National Science Foundation
Zitieren
APA
Fefferman, C., Mitter, S., & Narayanan, H. (2016). Testing the manifold hypothesis. Journal of the American Mathematical Society, 29(4), 983-1049. https://doi.org/10.1090/jams/852
Vancouver
Fefferman C, Mitter S, Narayanan H. Testing the manifold hypothesis. Journal of the American Mathematical Society. 2016;29(4):983-1049. doi:10.1090/jams/852
BibTeX
@article{Fefferman2016,
author = {Fefferman, Charles and Mitter, Sanjoy and Narayanan, Hariharan},
title = {Testing the manifold hypothesis},
journal = {Journal of the American Mathematical Society},
year = {2016},
volume = {29},
number = {4},
pages = {983--1049},
doi = {10.1090/jams/852}
}
EUVIMED