CoChat
Sign Up
Cited by 430Machine Learning and AlgorithmsTopological and Geometric Data AnalysisGeometric Analysis and Curvature Flows

The DOI matches its Crossref record; 24 of the 24 references it cites were found in a registry or an index.

Testing the manifold hypothesis

Open access
Fefferman, Charles, Mitter, Sanjoy, Narayanan, Hariharan·2016·Journal of the American Mathematical Society
DOI 10.1090/jams/852
Open this paper in CoChat — free accountOpen PDF

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 , τ ) be the set of submanifolds of the unit ball of H whose volume is at most V and reach (which is the supremum of all r such that any point at a distance less than r has a unique nearest point on the manifold) is at least τ . Let L ( M , P ) denote the mean-squared distance of a random point from the probability distribution P to M . We obtain an algorithm that tests the manifold hypothesis in the following sense. The algorithm takes i.i.d. random samples from 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 ) such that L ( M , P ) ≤ C ϵ . There exists no M ∈ G ( d , V / C , C τ ) such that L ( M , P ) ≤ ϵ C . The answer is correct with probability at least 1 − δ .

Overview

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1090/jams/852

Cites

24 of 24 references verified0 citation errors · 0 not checkable

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

Flagged first, then by citations

Show all 11 references

Research works printed but not linked: 28

  1. Amari, Shun-ichi, 2000, Methods of information geometry, 191, 10.1090/mmono/191 · DOI
  2. Baraniuk, Richard G., 2009, Random projections of smooth manifolds, Found. Comput. Math., 9, 51, 10.1007/s10208-007-9011-z · DOI
  3. Belkin, Mikhail, 2003, Laplacian eigenmaps for dimensionality reduction and data representation, Neural Comput., 15, 1373, 10.1162/089976603321780317 · DOI
  4. Brand, M., 2002, Charting a manifold, NIPS, 15, 985
  5. Genovese, Christopher R., 2012, Minimax manifold estimation, J. Mach. Learn. Res., 13, 1263
  6. Coifman, Ronald R., 2005, Geometric diffusions as a tool for harmonic analysis and structure definition of data. Part II: Multiscale methods, Proc. Natl. Acad. Sci. USA, 102, 7432, 10.1073/pnas.0500896102 · DOI
  7. Cox, Trevor F., 1994, Multidimensional scaling, 59
  8. David, Guy, 1993, Analysis of and on uniformly rectifiable sets, 38, 10.1090/surv/038 · DOI
  9. Devroye, Luc, 1996, A probabilistic theory of pattern recognition, 10.1007/978-1-4612-0711-5 · DOI · Paper page
  10. Federer, Herbert, 1959, Curvature measures, Trans. Amer. Math. Soc., 93, 418, 10.2307/1993504 · DOI
  11. Hastie, Trevor, 1989, Principal curves, J. Amer. Statist. Assoc., 84, 502, 10.1080/01621459.1989.10478797 · DOI
  12. Hotelling, H., 1933, Analysis of a complex of statistical variables into principal components, J. Educational Psychology, 24, 417, 10.1037/h0071325 · DOI
  13. Johnson, William B., 1984, Extensions of Lipschitz mappings into a Hilbert space, 189, 10.1090/conm/026/737400 · DOI
  14. Ledoux, Michel, 2001, The concentration of measure phenomenon, 89, 10.1090/surv/089 · DOI
  15. 2012, Manifold learning theory and applications
  16. Martinetz, Thomas, 1994, Topology representing networks, Neural Netw., 7, 507, 10.1016/0893-6080(94)90109-0 · DOI
  17. Massart, Pascal, 2000, Some applications of concentration inequalities to statistics, Ann. Fac. Sci. Toulouse Math. (6), 9, 245, 10.5802/afst.961 · DOI
  18. Narasimhan, Raghavan, 1965, Lectures on topics in analysis
  19. Narayanan, Hariharan, 2010, On the sample complexity of testing the manifold hypothesis, NIPS, 1786
  20. Newton, Nigel J., 2013, Infinite-dimensional manifolds of finite-entropy probability measures, 713, 10.1007/978-3-642-40020-9_79 · DOI
  21. Ozertem, Umut, 2011, Locally defined principal curves and surfaces, J. Mach. Learn. Res., 12, 1249
  22. Pearson, K., 1901, On lines and planes of closest fit to systems of points in space, Philos. Mag., 2, 559, 10.1080/14786440109462720 · DOI
  23. Roweis, S. T., 2002, Global coordination of local linear models, Adv. Neural Inf. Process. Syst., 14, 889
  24. Shawe-Taylor, J., 2004, Kernel methods for pattern analysis, 10.1017/CBO9780511809682 · DOI
  25. Smola, Alex J., 1999, Regularized principal manifolds, 214, 10.1007/3-540-49097-3_17 · DOI
  26. Tenenbaum, J. B., 2000, A Global Geometric Framework for Nonlinear Dimensionality Reduction, Science, 290, 2319, 10.1126/science.290.5500.2319 · DOI · Paper page
  27. Vaidya, Pravin M., 1996, A new algorithm for minimizing convex functions over convex sets, Math. Programming, 73, 291, 10.1016/0025-5610(92)00021-S · DOI
  28. Weinberger, Kilian Q., 2006, Unsupervised learning of image manifolds by semidefinite programming, Int. J. Comput. Vision, 70, 77, 10.1007/s11263-005-4939-z · DOI

Cited by

Sorted by citations

Items 401–426 of 426

Related

See all

Metadata

Authors
Fefferman, C., Mitter, S., & Narayanan, H.
Affiliations
  • Princeton University (US)
  • Massachusetts Institute of Technology (US)
  • University of Washington (US)
ORCID
Venue
Journal of the American Mathematical Society
Publisher
American Mathematical Society (AMS)
Published
2016-02-09
Volume
29
Issue
4
Pages
983-1049
ISSN
  • 0894-0347 (ISSN-L)
  • 1088-6834
DOI
10.1090/jams/852
OpenAlex
W1593775104
Cited by
430
References
11
Citations by year
2026: 50 · 2025: 72 · 2024: 57 · 2023: 63 · 2022: 49 · 2021: 62 · 2020: 34 · 2019: 29 · 2018: 8 · 2017: 3
FWCI
4.20
Type
journal article
Language
en
Open access
Licence
www.ams.org/publications/copyright-and-permissions (am, 366 d)
Locations
  • Journal of the American Mathematical Society (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Funders
National Science Foundation (EECS -1135843 " Smart Power Systems of the Future : Foundations for Understanding Volatility and Improving Operational Reliabili)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and Algorithms
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Topological and Geometric Data Analysis
  • Physical Sciences › Mathematics › Applied Mathematics › Geometric Analysis and Curvature Flows
Keywords
manifold hypothesis, manifold learning, separable Hilbert space, i.i.d. samples, high-dimensional data

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review