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 accessAbstract
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.
Integrity signals
Registry
Cites
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.
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?
In the citing paper
“According to the manifold hypothesis [66], most natural data lies on manifolds with significantly reduced intrinsic dimensionality.”
From Diffusion Models: A Comprehensive Survey of Methods and Applications (2024) · cites this paper as [66]
In the citing paper
“Data with manifold structures are ubiquitous in machine learning.As the manifold hypothesis [66] posits, natural data often reside on manifolds with lower intrinsic dimensionality.”
From Diffusion Models: A Comprehensive Survey of Methods and Applications (2024) · cites this paper as [66]
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
Nonlinear Dimensionality Reduction by Locally Linear Embedding
Roweis, S. T., & Saul, L. K. (2000) · Science · doi:10.1126/science.290.5500.2323 · Cited by 14,965
Carlsson, G. (2009) · Bulletin of the American Mathematical Society · doi:10.1090/s0273-0979-09-01249-x · Cited by 2,302
Estimation of Dependences Based on Empirical Data
Vapnik, V. N. (2006) · Information science and statistics · doi:10.1007/0-387-34239-7 · Cited by 2,252
Hessian eigenmaps: Locally linear embedding techniques for high-dimensional data
Donoho, D. L., & Grimes, C. (2003) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1031596100 · Cited by 1,704
Principal Manifolds and Nonlinear Dimensionality Reduction via Tangent Space Alignment
Zhang, Z., & Zha, H. (2004) · SIAM Journal on Scientific Computing · doi:10.1137/s1064827502419154 · Cited by 1,504
Uniform Central Limit Theorems
Dudley, R. M. (1999) · Cambridge University Press eBooks · doi:10.1017/cbo9780511665622 · Cited by 808
Introduction to Statistical Learning Theory
Bousquet, O., Boucheron, S., & Lugosi, G. (2004) · Advanced Lectures on Machine Learning · doi:10.1007/978-3-540-28650-9_8 · Cited by 687
Finding the homology of submanifolds with high confidence from random samples
Niyogi, P., Smale, S., & Weinberger, S. (2008) · Discrete & Computational Geometry · doi:10.1007/s00454-008-9053-2 · Cited by 523
Bradley, P., & Mangasarian, O. L. (2000) · Journal of Global Optimization · doi:10.1023/a:1008324625522 · Cited by 406
Pattern Analysis and Machine Intelligence
Yang, J., Zheng, Y., & Gong, C. (2025) · Communications in computer and information science · doi:10.1007/978-981-96-3349-4 · Cited by 390
Random projection trees and low dimensional manifolds
Dasgupta, S., & Freund, Y. (2008) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1374376.1374452 · Cited by 383
Learning and design of principal curves
Kégl, B., Krzyżak, A., Linder, T., & Zeger, K. (2000) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.841759 · Cited by 346
$K$-Dimensional Coding Schemes in Hilbert Spaces
Maurer, A., & Pontil, M. (2010) · IEEE Transactions on Information Theory · doi:10.1109/tit.2010.2069250 · Cited by 92
Tighter bounds for random projections of manifolds
Clarkson, K. L. (2008) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/1377676.1377685 · Cited by 88
Nonparametric ridge estimation
Genovese, C. R., Perone-Pacifico, M., Verdinelli, I., & Wasserman, L. (2014) · The Annals of Statistics · doi:10.1214/14-aos1218 · Cited by 71
Manifold estimation and singular deconvolution under Hausdorff loss
Genovese, C. R., Perone-Pacifico, M., Verdinelli, I., & Wasserman, L. (2012) · The Annals of Statistics · doi:10.1214/12-aos994 · Cited by 60
Interpolation and extrapolation of smooth functions by linear operators
Fefferman, C. (2005) · Revista Matemática Iberoamericana · doi:10.4171/rmi/424 · Cited by 58
Self-citationRobust recovery of multiple subspaces by geometric lp minimization
Lerman, G., & Zhang, T. (2011) · The Annals of Statistics · doi:10.1214/11-aos914 · Cited by 54
Magic moments for structured output prediction
Smola, A. J., Mika, S., Schölkopf, B., & Williamson, R. C. (2001) · Iris (University of Trento) · doi:10.1162/15324430152748227 · Cited by 52
Combinatorics of random processes and sections of convex bodies
Rudelson, M., & Vershynin, R. (2006) · Annals of Mathematics · doi:10.4007/annals.2006.164.603 · Cited by 38
Manifold Reconstruction in Arbitrary Dimensions Using Witness Complexes
Boissonnat, J.-D., Guibas, L. J., & Oudot, S. (2009) · Discrete & Computational Geometry · doi:10.1007/s00454-009-9175-1 · Cited by 37
Universal local parametrizations via heat kernels and eigenfunctions of the Laplacian
Jones, P. W., Maggioni, M., & Schul, R. (2010) · Annales Academiae Scientiarum Fennicae Mathematica · doi:10.5186/aasfm.2010.3508 · Cited by 34
Approximation of points on low-dimensional manifolds via random linear projections
Iwen, M., & Maggioni, M. (2013) · Information and Inference A Journal of the IMA · doi:10.1093/imaiai/iat001 · Cited by 21
The $C^m$ Norm of a Function with Prescribed Jets II
Fefferman, C. (2009) · Revista Matemática Iberoamericana · doi:10.4171/rmi/570 · Cited by 18
Self-citation
Research works printed but not linked: 28
- Amari, Shun-ichi, 2000, Methods of information geometry, 191, 10.1090/mmono/191 · DOI
- Baraniuk, Richard G., 2009, Random projections of smooth manifolds, Found. Comput. Math., 9, 51, 10.1007/s10208-007-9011-z · DOI
- Belkin, Mikhail, 2003, Laplacian eigenmaps for dimensionality reduction and data representation, Neural Comput., 15, 1373, 10.1162/089976603321780317 · DOI
- Brand, M., 2002, Charting a manifold, NIPS, 15, 985
- Genovese, Christopher R., 2012, Minimax manifold estimation, J. Mach. Learn. Res., 13, 1263
- 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
- Cox, Trevor F., 1994, Multidimensional scaling, 59
- David, Guy, 1993, Analysis of and on uniformly rectifiable sets, 38, 10.1090/surv/038 · DOI
- Devroye, Luc, 1996, A probabilistic theory of pattern recognition, 10.1007/978-1-4612-0711-5 · DOI · Paper page
- Federer, Herbert, 1959, Curvature measures, Trans. Amer. Math. Soc., 93, 418, 10.2307/1993504 · DOI
- Hastie, Trevor, 1989, Principal curves, J. Amer. Statist. Assoc., 84, 502, 10.1080/01621459.1989.10478797 · DOI
- Hotelling, H., 1933, Analysis of a complex of statistical variables into principal components, J. Educational Psychology, 24, 417, 10.1037/h0071325 · DOI
- Johnson, William B., 1984, Extensions of Lipschitz mappings into a Hilbert space, 189, 10.1090/conm/026/737400 · DOI
- Ledoux, Michel, 2001, The concentration of measure phenomenon, 89, 10.1090/surv/089 · DOI
- 2012, Manifold learning theory and applications
- Martinetz, Thomas, 1994, Topology representing networks, Neural Netw., 7, 507, 10.1016/0893-6080(94)90109-0 · DOI
- Massart, Pascal, 2000, Some applications of concentration inequalities to statistics, Ann. Fac. Sci. Toulouse Math. (6), 9, 245, 10.5802/afst.961 · DOI
- Narasimhan, Raghavan, 1965, Lectures on topics in analysis
- Narayanan, Hariharan, 2010, On the sample complexity of testing the manifold hypothesis, NIPS, 1786
- Newton, Nigel J., 2013, Infinite-dimensional manifolds of finite-entropy probability measures, 713, 10.1007/978-3-642-40020-9_79 · DOI
- Ozertem, Umut, 2011, Locally defined principal curves and surfaces, J. Mach. Learn. Res., 12, 1249
- Pearson, K., 1901, On lines and planes of closest fit to systems of points in space, Philos. Mag., 2, 559, 10.1080/14786440109462720 · DOI
- Roweis, S. T., 2002, Global coordination of local linear models, Adv. Neural Inf. Process. Syst., 14, 889
- Shawe-Taylor, J., 2004, Kernel methods for pattern analysis, 10.1017/CBO9780511809682 · DOI
- Smola, Alex J., 1999, Regularized principal manifolds, 214, 10.1007/3-540-49097-3_17 · DOI
- Tenenbaum, J. B., 2000, A Global Geometric Framework for Nonlinear Dimensionality Reduction, Science, 290, 2319, 10.1126/science.290.5500.2319 · DOI · Paper page
- 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
- 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
Diffusion Models: A Comprehensive Survey of Methods and Applications
Yang, L., Zhang, Z., Song, Y., Hong, S., Xu, R., Zhao, Y., Zhang, W., Cui, B., & Yang, M.-H. (2024) · ACM Computing Surveys · doi:10.1145/3626235 · Cited by 1,704
Machine learning in aerodynamic shape optimization
Li, J., Du, X., & Martins, J. R. R. A. (2022) · Progress in Aerospace Sciences · doi:10.1016/j.paerosci.2022.100849 · Cited by 398
Image Data Augmentation Approaches: A Comprehensive Survey and Future Directions
Kumar, T., Brennan, R., Mileo, A., & Bendechache, M. (2024) · IEEE Access · doi:10.1109/access.2024.3470122 · Cited by 399
A Survey of Topological Machine Learning Methods
Hensel, F., Moor, M., & Rieck, B. (2021) · Frontiers in Artificial Intelligence · doi:10.3389/frai.2021.681108 · Cited by 209
Brown, C. F., Kazmierski, M. R., Pasquarella, V. J., Rucklidge, W. J., Samsikova, M., Zhang, C., Shelhamer, E., Lahera, E., Wiles, O., Ilyushchenko, S., et al. (2025) · arXiv · doi:10.48550/arxiv.2507.22291 · Cited by 172
Metadata
- Authors
- Fefferman, C., Mitter, S., & Narayanan, H.
- Affiliations
- Princeton University (US)
- Massachusetts Institute of Technology (US)
- University of Washington (US)
- 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
- 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
- bronze
- doi.org
- 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
