Remote Access Journal of the American Mathematical Society
Green Open Access

Journal of the American Mathematical Society

ISSN 1088-6834(online) ISSN 0894-0347(print)

   
 
 

 

Testing the manifold hypothesis


Authors: Charles Fefferman, Sanjoy Mitter and Hariharan Narayanan
Journal: J. Amer. Math. Soc. 29 (2016), 983-1049
MSC (2010): Primary 62G08, 62H15; Secondary 55R10, 57R40
DOI: https://doi.org/10.1090/jams/852
Published electronically: February 9, 2016
MathSciNet review: 3522608
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 $ \mathcal {P}$ supported on the unit ball of a separable Hilbert space $ \mathcal {H}$. Let $ \mathcal {G}(d, V, \tau )$ be the set of submanifolds of the unit ball of $ \mathcal {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 $ \tau $. Let $ \mathcal {L}(\mathcal {M}, \mathcal {P})$ denote the mean-squared distance of a random point from the probability distribution $ \mathcal {P}$ to $ \mathcal {M}$. We obtain an algorithm that tests the manifold hypothesis in the following sense.

The algorithm takes i.i.d. random samples from $ \mathcal {P}$ as input and determines which of the following two is true (at least one must be):

  1. There exists $ \mathcal {M} \in \mathcal {G}(d, CV, \frac {\tau }{C})$ such that $ \mathcal {L}(\mathcal {M}, \mathcal {P}) \leq C {\epsilon }.$
  2. There exists no $ \mathcal {M} \in \mathcal {G}(d, V/C, C\tau )$ such that $ \mathcal {L}(\mathcal {M}, \mathcal {P}) \leq \frac {\epsilon }{C}.$
The answer is correct with probability at least $ 1-\delta $.

References [Enhancements On Off] (What's this?)

  • [1] Shun-ichi Amari and Hiroshi Nagaoka, Methods of information geometry, Translations of Mathematical Monographs, vol. 191, American Mathematical Society, Providence, RI; Oxford University Press, Oxford, 2000. Translated from the 1993 Japanese original by Daishi Harada. MR 1800071 (2001j:62023)
  • [2] Richard G. Baraniuk and Michael B. Wakin, Random projections of smooth manifolds, Found. Comput. Math. 9 (2009), no. 1, 51-77. MR 2472287 (2010g:94021), https://doi.org/10.1007/s10208-007-9011-z
  • [3] Mikhail Belkin and Partha Niyogi, Laplacian eigenmaps for dimensionality reduction and data representation, Neural Comput. 15 (2003), no. 6, 1373-1396.
  • [4] Jean-Daniel Boissonnat, Leonidas J. Guibas, and Steve Y. Oudot, Manifold reconstruction in arbitrary dimensions using witness complexes, Discrete Comput. Geom. 42 (2009), no. 1, 37-70. MR 2506737 (2010h:68183), https://doi.org/10.1007/s00454-009-9175-1
  • [5] Olivier Bousquet, Stéphane Boucheron, and Gábor Lugosi, Introduction to statistical learning theory, Advanced Lectures on Machine Learning, 2004, pp. 169-207.
  • [6] P. S. Bradley and O. L. Mangasarian, $ k$-plane clustering, J. Global Optim. 16 (2000), no. 1, 23-32. MR 1770524 (2001g:90095), https://doi.org/10.1023/A:1008324625522
  • [7] M. Brand, Charting a manifold, NIPS 15 (2002), 985-992.
  • [8] Guillermo D. Cañas, Tomaso Poggio, and Lorenzo Rosasco, Learning manifolds with k-means and k-flats, 26th Annual Conference on Neural Information Processing Systems, December 3-6, 2012, Lake Tahoe, Nevada, Proceedings of Advances in Neural Information Processing Systems 25, Curran Associates, Red Hook, NY, 2013, pp. 2474-2482.
  • [9] Gunnar Carlsson, Topology and data, Bull. Amer. Math. Soc. (N.S.) 46 (2009), no. 2, 255-308. MR 2476414 (2010d:55001), https://doi.org/10.1090/S0273-0979-09-01249-X
  • [10] Siu-Wing Cheng, Tamal K. Dey, and Edgar A. Ramos, Manifold reconstruction from point samples, Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, 2005, pp. 1018-1027. MR 2298361
  • [11] Christopher R. Genovese, Marco Perone-Pacifico, Isabella Verdinelli, and Larry Wasserman, Manifold estimation and singular deconvolution under Hausdorff loss, Ann. Statist. 40 (2012), no. 2, 941-963. MR 2985939, https://doi.org/10.1214/12-AOS994
  • [12] Christopher R. Genovese, Marco Perone-Pacifico, Isabella Verdinelli, and Larry Wasserman, Minimax manifold estimation, J. Mach. Learn. Res. 13 (2012), no. 1, 1263-1291.
  • [13] Kenneth L. Clarkson, Tighter bounds for random projections of manifolds, Computational geometry (SCG'08), ACM, New York, 2008, pp. 39-48. MR 2504269, https://doi.org/10.1145/1377676.1377685
  • [14] Ronald R. Coifman, Stephane Lafon, Ann Lee, Mauro Maggioni, Boaz Nadler, Frederick Warner, and Steven Zucker, Geometric diffusions as a tool for harmonic analysis and structure definition of data. Part II: Multiscale methods, Proc. Natl. Acad. Sci. USA 102 (2005), no. 21, 7432-7438.
  • [15] Trevor F. Cox and Michael A. A. Cox, Multidimensional scaling, Monographs on Statistics and Applied Probability, vol. 59, Chapman & Hall, London, 1994. With 1 IBM-PC floppy disk (3.5 inch, HD). MR 1335449 (96g:62118)
  • [16] Sanjoy Dasgupta and Yoav Freund, Random projection trees and low dimensional manifolds, STOC'08, ACM, New York, 2008, pp. 537-546. MR 2582911 (2011b:68036), https://doi.org/10.1145/1374376.1374452
  • [17] Guy David and Stephen Semmes, Analysis of and on uniformly rectifiable sets, Mathematical Surveys and Monographs, vol. 38, American Mathematical Society, Providence, RI, 1993. MR 1251061 (94i:28003)
  • [18] Luc Devroye, Lászlo Györfi, and Gábor Lugosi, A probabilistic theory of pattern recognition, Springer, New York, 1996.
  • [19] David L. Donoho, Aide-memoire. High-dimensional data analysis: The curses and blessings of dimensionality, http://statweb.stanford.edu/$ \sim $donoho/Lectures/CBMS/Curses.pdf (2000).
  • [20] David L. Donoho and Carrie Grimes, Hessian eigenmaps: locally linear embedding techniques for high-dimensional data, Proc. Natl. Acad. Sci. USA 100 (2003), no. 10, 5591-5596 (electronic). MR 1981019 (2004e:62108), https://doi.org/10.1073/pnas.1031596100
  • [21] R. M. Dudley, Uniform central limit theorems, Cambridge Studies in Advanced Mathematics, vol. 63, Cambridge University Press, Cambridge, 1999. MR 1720712 (2000k:60050)
  • [22] Herbert Federer, Curvature measures, Trans. Amer. Math. Soc. 93 (1959), 418-491. MR 0110078 (22 #961)
  • [23] Charles Fefferman, Interpolation and extrapolation of smooth functions by linear operators, Rev. Mat. Iberoam. 21 (2005), no. 1, 313-348. MR 2155023 (2006h:58009), https://doi.org/10.4171/RMI/424
  • [24] Charles Fefferman, The $ C^m$ norm of a function with prescribed jets. II, Rev. Mat. Iberoam. 25 (2009), no. 1, 275-421. MR 2514339 (2011d:46050), https://doi.org/10.4171/RMI/570
  • [25] Christopher R. Genovese, Marco Perone-Pacifico, Isabella Verdinelli, and Larry Wasserman, Nonparametric ridge estimation, Ann. Statist. 42 (2014), no. 4, 1511-1545. MR 3262459, https://doi.org/10.1214/14-AOS1218
  • [26] Trevor Hastie and Werner Stuetzle, Principal curves, J. Amer. Statist. Assoc. 84 (1989), no. 406, 502-516. MR 1010339 (90i:62073)
  • [27] H. Hotelling, Analysis of a complex of statistical variables into principal components, J. Educational Psychology 24 (1933), 417-441, 498-520.
  • [28] Mark A. Iwen and Mauro Maggioni, Approximation of points on low-dimensional manifolds via random linear projections, Inf. Inference 2 (2013), no. 1, 1-31. MR 3311442, https://doi.org/10.1093/imaiai/iat001
  • [29] William B. Johnson and Joram Lindenstrauss, Extensions of Lipschitz mappings into a Hilbert space, Conference in modern analysis and probability (New Haven, Conn., 1982), Contemp. Math., vol. 26, Amer. Math. Soc., Providence, RI, 1984, pp. 189-206. MR 737400 (86a:46018), https://doi.org/10.1090/conm/026/737400
  • [30] Peter W. Jones, Mauro Maggioni, and Raanan Schul, Universal local parametrizations via heat kernels and eigenfunctions of the Laplacian, Ann. Acad. Sci. Fenn. Math. 35 (2010), no. 1, 131-174. MR 2643401 (2011g:58038), https://doi.org/10.5186/aasfm.2010.3508
  • [31] A. Kambhatla and Todd K. Leen, Fast non-linear dimension reduction, IEEE International Conference on Neural Networks, IEEE, New York, 1993, pp. 1213-1218.
  • [32] Balázs Kégl, Adam Krzyzak, Tamás Linder, and Kenneth Zeger, Learning and design of principal curves, IEEE Trans. Pattern Analysis and Machine Intelligence 22 (2000), 281-297.
  • [33] Michel Ledoux, The concentration of measure phenomenon, Mathematical Surveys and Monographs, vol. 89, American Mathematical Society, Providence, RI, 2001. MR 1849347 (2003k:28019)
  • [34] Gilad Lerman and Teng Zhang, Robust recovery of multiple subspaces by geometric $ l_p$ minimization, Ann. Statist. 39 (2011), no. 5, 2686-2715. MR 2906883, https://doi.org/10.1214/11-AOS914
  • [35] Manifold learning theory and applications, CRC Press, Boca Raton, FL, 2012. Edited by Yunqian Ma and Yun Fu. MR 2964193
  • [36] Thomas Martinetz and Klaus Schulten, Topology representing networks, Neural Netw. 7 (1994), no. 3, 507-522.
  • [37] Pascal Massart, Some applications of concentration inequalities to statistics, Ann. Fac. Sci. Toulouse Math. (6) 9 (2000), no. 2, 245-303 (English, with English and French summaries). Probability theory. MR 1813803 (2001m:60012)
  • [38] Andreas Maurer and Massimiliano Pontil, $ K$-dimensional coding schemes in Hilbert spaces, IEEE Trans. Inform. Theory 56 (2010), no. 11, 5839-5846. MR 2808936 (2012a:94107), https://doi.org/10.1109/TIT.2010.2069250
  • [39] Raghavan Narasimhan, Lectures on topics in analysis, Notes by M. S. Rajwade. Tata Institute of Fundamental Research Lectures on Mathematics, No. 34, Tata Institute of Fundamental Research, Bombay, 1965. MR 0212837 (35 #3702)
  • [40] Hariharan Narayanan and Sanjoy Mitter, On the sample complexity of testing the manifold hypothesis, NIPS (2010), 1786-1794.
  • [41] Hariharan Narayanan and Partha Niyogi, On the sample complexity of learning smooth cuts on a manifol, Proc. of the 22nd Annual Conference on Learning Theory (COLT), June 2009, pp. 197-204.
  • [42] Nigel J. Newton, Infinite-dimensional manifolds of finite-entropy probability measures, Geometric science of information, Lecture Notes in Comput. Sci., vol. 8085, Springer, Heidelberg, 2013, pp. 713-720. MR 3126105, https://doi.org/10.1007/978-3-642-40020-9_79
  • [43] Partha Niyogi, Stephen Smale, and Shmuel Weinberger, Finding the homology of submanifolds with high confidence from random samples, Discrete Comput. Geom. 39 (2008), no. 1-3, 419-441. MR 2383768 (2009b:60038), https://doi.org/10.1007/s00454-008-9053-2
  • [44] Umut Ozertem and Deniz Erdogmus, Locally defined principal curves and surfaces, J. Mach. Learn. Res. 12 (2011), 1249-1286. MR 2804600 (2012e:62196)
  • [45] K. Pearson, On lines and planes of closest fit to systems of points in space, Philos. Mag. 2 (1901), 559-572.
  • [46] S. T. Roweis, L. Saul, and G. Hinton, Global coordination of local linear models, Adv. Neural Inf. Process. Syst. 14 (2002), 889-896.
  • [47] Sam T. Roweis and Lawrence K. Saul, Nonlinear dimensionality reduction by locally linear embedding, Science 290 (2000), 2323-2326.
  • [48] M. Rudelson and R. Vershynin, Combinatorics of random processes and sections of convex bodies, Ann. of Math. (2) 164 (2006), no. 2, 603-648. MR 2247969 (2007j:60016), https://doi.org/10.4007/annals.2006.164.603
  • [49] J. Shawe-Taylor and N. Christianini, Kernel methods for pattern analysis, Cambridge University Press, Cambridge, UK, 2004.
  • [50] Alex J. Smola, Robert C. Williamson, Sebastian Mika, and Bernhard Schölkopf, Regularized principal manifolds, Computational learning theory (Nordkirchen, 1999) Lecture Notes in Comput. Sci., vol. 1572, Springer, Berlin, 1999, pp. 214-229. MR 1724991, https://doi.org/10.1007/3-540-49097-3_17
  • [51] Karthik Sridharan and Nathan Srebro, Note on refined Dudley integral covering number bound. Unpublished.
  • [52] J. B. Tenenbaum, V. Silva, and J. C. Langford, A Global Geometric Framework for Nonlinear Dimensionality Reduction, Science 290 (2000), no. 2000, 2319-2323.
  • [53] Pravin M. Vaidya, A new algorithm for minimizing convex functions over convex sets, Math. Programming 73 (1996), no. 3, Ser. A, 291-341. MR 1393123 (97e:90060), https://doi.org/10.1016/0025-5610(92)00021-S
  • [54] Vladimir Vapnik, Estimation of dependences based on empirical data, Springer Series in Statistics, Springer-Verlag, New York-Berlin, 1982. Translated from the Russian by Samuel Kotz. MR 672244 (84a:62043)
  • [55] Kilian Q. Weinberger and Lawrence K. Saul, Unsupervised learning of image manifolds by semidefinite programming, Int. J. Comput. Vision 70 (2006), no. 1, 77-90.
  • [56] Zhenyue Zhang and Hongyuan Zha, Principal manifolds and nonlinear dimensionality reduction via tangent space alignment, SIAM J. Sci. Comput. 26 (2004), no. 1, 313-338 (electronic). MR 2114346 (2005k:65024), https://doi.org/10.1137/S1064827502419154

Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC (2010): 62G08, 62H15, 55R10, 57R40

Retrieve articles in all journals with MSC (2010): 62G08, 62H15, 55R10, 57R40


Additional Information

Charles Fefferman
Affiliation: Department of Mathematics, Princeton University, Princeton, New Jersey 08544
Email: cf@math.princeton.edu

Sanjoy Mitter
Affiliation: Laboratory for Information and Decision Systems, MIT, Cambridge, Massachusetts 02139
Email: mitter@mit.edu

Hariharan Narayanan
Affiliation: Department of Statistics and Department of Mathematics, University of Washington, Seattle, Washington 98195
Email: harin@uw.edu

DOI: https://doi.org/10.1090/jams/852
Received by editor(s): March 9, 2014
Received by editor(s) in revised form: February 3, 2015, and August 9, 2015
Published electronically: February 9, 2016
Additional Notes: The first author was supported by NSF grant DMS 1265524, AFOSR grant FA9550-12-1-0425 and U.S.-Israel Binational Science Foundation grant 2014055.
The second author was supported by NSF grant EECS-1135843.
Article copyright: © Copyright 2016 American Mathmatical Society

American Mathematical Society