Abstract
It is often the case that data is encoded as numeric vectors and hence is naturally embedded in a Euclidean space, with a dimension equal to the number of features. After the classical PCA that fits a linear (flat) subspace so that the total sum of squared distances of the data from the subspace (errors) is minimized, any distance function in this space can be used to endow it with a geometric structure, where ordinary intuition can be particularly powerful tools to reduce dimensionality. The idea can be generalized by changing the flat space to obtain a possibly nonlinear curved object (a so-called manifold) that can be fitted to the data while trying to minimize the deformations of distances as much as possible. Four major methods of this kind are reviewed, namely MDS, ISOMAP, t-SNE, and random projections.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Achlioptas, D. (2003). Database-friendly random projections: Johnson-lindenstrauss with binary coins. Journal of Computer and System Sciences, 66(4), 671–687.
Arriaga, R. I., & Vempala, S. (2006). An algorithmic theory of learning: Robust concepts and random projection. Machine Learning, 63(2), 161–182.
Baraniuk, R. G., & Wakin, M. B. (2009). Random projections of smooth manifolds. Foundations of Computational Mathematics, 9, 51–77.
Clarkson, K. L. (2008). Tighter bounds for random projections of manifolds. In Proceedings of the Twenty-Fourth Annual Symposium on Computational Geometry SCG’08 (pp. 39–48). New York: Association for Computing Machinery.
Cox, T. F., & Cox, M. A. A. (2000). Multidimensional scaling (2nd edn.). Boca Raton: Chapman & Hall CRC.
Dasgupta, S., & Gupta, A. (2003). An elementart proof of a theorem of Johnson and lindenstrauss. Random Structures and Algorithms, 22(1), 60–65.
Feller, W. (1971). An introduction to probability theory and its applications (vol. II, 2nd edn.). New York: Wiley.
Frankl, P., & Maehara, H. (1988). The Johnson-lindenstrauss lemma and the sphericity of some graphs. Journal of Combinatorial Theory, Series B, 44(3), 355–362.
Groenen, P. J. F., & Heiser, W. J. (1996). The tunneling method for global optimization in multidimensional scaling. Psychometrika, 61, 529–550.
Guttman, L. (1968). A general nonmetric technique for finding the smallest coordinate space for a configuration of points. Psychometrika, 33, 469–506.
Hinton, G. E., & Roweis, S. T. (2002). Stochastic neighbor embedding. In Advances in neural information processing systems (vol. 15, pp. 833–840). Cambridge: The MIT Press.
Hogg, R. V., McKean, J. W., & Craig, A. T. (2019). Introduction to mathematical statistics (8th edn.). London: Pearson.
Indyk, P., & Motwani, R. (1998). Approximate nearest neighbors: Towards removing the curse of dimensionality. In Proc. of ACM STOC.
Johnson, W. B., & Lindenstrauss, J. (1984). Extensions of lipschitz map**s into a hilbert space. Contemporary Mathematics, 26, 189–206.
Kumar, V., Grama, A., Gupta, A., & Karypis, G. (1994). Introduction to parallel computing: Design and analysis of algorithms. San Francisco: Benjamin-Cummings.
Lee, J. A., & Verleysen, M. (2007). Nonlinear dimensionality reduction (1st edn.). Berlin: Springer.
Maaten, L., & Hinton, G. E. (2008). Visualizing data using t-SNE. Journal of Machine Learning Research, 9(86), 2579–2605.
Messick, S. M., & Abelson, R. P. (1956). The additive constant problem in multidimensional scaling. Pyschometrika, 21, 1–15.
Nash, J. (1954). c 1 isometric imbeddings. Annals of Mathematics, 60(3), 383–396.
Shepard, R. N. (1962). The analysis of proximities: Multidimensional scaling with an unknown distance function. I. Psychometrika, 27(2), 219–246.
Silva, V., & Tenenbaum, J. B. (2002). Global versus local methods in nonlinear dimensionality reduction. In Proceedings of the 15th International Conference on Neural Information Processing System, NIPS’02 (pp. 721–728).
Tenenbaum, J. B., Silva, V., & Langford, J. C. (2000). A global geometric framework for nonlinear dimensionality reduction. Science, 290(22), 2319–2323.
Torgerson, W. S. (1952). Multidimensional scaling: I. Theory and method. Psychometrika, 17(4), 401–419.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this chapter
Cite this chapter
Kumar, N. (2022). Geometric Approaches. In: Garzon, M., Yang, CC., Venugopal, D., Kumar, N., Jana, K., Deng, LY. (eds) Dimensionality Reduction in Data Science. Springer, Cham. https://doi.org/10.1007/978-3-031-05371-9_5
Download citation
DOI: https://doi.org/10.1007/978-3-031-05371-9_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-05370-2
Online ISBN: 978-3-031-05371-9
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)