Note to users. If you're seeing this message, it means that your browser cannot find this page's style/presentation instructions -- or possibly that you are using a browser that does not support current Web standards. Find out more about why this message is appearing, and what you can do to make your experience of our site the best it can be.

Science 22 December 2000:
Vol. 290. no. 5500, pp. 2319 - 2323
DOI: 10.1126/science.290.5500.2319
Prev | Table of Contents | Next

Reports

A Global Geometric Framework for Nonlinear Dimensionality Reduction

Joshua B. Tenenbaum,1* Vin de Silva,2 John C. Langford3

Scientists working with large volumes of high-dimensional data, such as global climate patterns, stellar spectra, or human gene distributions, regularly confront the problem of dimensionality reduction: finding meaningful low-dimensional structures hidden in their high-dimensional observations. The human brain confronts the same problem in everyday perception, extracting from its high-dimensional sensory inputs--30,000 auditory nerve fibers or 106 optic nerve fibers--a manageably small number of perceptually relevant features. Here we describe an approach to solving dimensionality reduction problems that uses easily measured local metric information to learn the underlying global geometry of a data set. Unlike classical techniques such as principal component analysis (PCA) and multidimensional scaling (MDS), our approach is capable of discovering the nonlinear degrees of freedom that underlie complex natural observations, such as human handwriting or images of a face under different viewing conditions. In contrast to previous algorithms for nonlinear dimensionality reduction, ours efficiently computes a globally optimal solution, and, for an important class of data manifolds, is guaranteed to converge asymptotically to the true structure.

1 Department of Psychology and
2 Department of Mathematics, Stanford University, Stanford, CA 94305, USA.
3 Department of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15217, USA.
*   To whom correspondence should be addressed. E-mail: jbt{at}psych.stanford.edu

Read the Full Text


THIS ARTICLE HAS BEEN CITED BY OTHER ARTICLES:
Statistical challenges of high-dimensional data.
I. M. Johnstone and D. M. Titterington (2009)
Phil Trans R Soc A 367, 4237-4253
   Abstract »    Full Text »    PDF »
On landmark selection and sampling in high-dimensional data analysis.
M.-A. Belabbas and P. J. Wolfe (2009)
Phil Trans R Soc A 367, 4295-4312
   Abstract »    Full Text »    PDF »
Identification of characteristic plant co-occurrences in neotropical secondary montane forests.
M. D. Mahecha, A. Martinez, H. Lange, M. Reichstein, and E. Beck (2009)
J Plant Ecol 2, 31-41
   Abstract »    Full Text »    PDF »
Functional Differentiation of Macaque Visual Temporal Cortical Neurons Using a Parametric Action Space.
J. Vangeneugden, F. Pollick, and R. Vogels (2009)
Cereb Cortex 19, 593-611
   Abstract »    Full Text »    PDF »
Spectral methods in machine learning and new strategies for very large datasets.
M.-A. Belabbas and P. J. Wolfe (2009)
PNAS 106, 369-374
   Abstract »    Full Text »    PDF »
Manifold parametrizations by eigenfunctions of the Laplacian and heat kernels.
P. W. Jones, M. Maggioni, and R. Schul (2008)
PNAS 105, 1803-1808
   Abstract »    Full Text »    PDF »
Quantification of Health States with Rank-Based Nonmetric Multidimensional Scaling.
P. F. M. Krabbe, J. A. Salomon, and C. J. L. Murray (2007)
Med Decis Making 27, 395-405
   Abstract »    PDF »
Object Category Structure in Response Patterns of Neuronal Population in Monkey Inferior Temporal Cortex.
R. Kiani, H. Esteky, K. Mirpour, and K. Tanaka (2007)
J Neurophysiol 97, 4296-4309
   Abstract »    Full Text »    PDF »
From the Cover: Adaptive reconfiguration of fractal small-world human brain functional networks.
D. S. Bassett, A. Meyer-Lindenberg, S. Achard, T. Duke, and E. Bullmore (2006)
PNAS 103, 19518-19523
   Abstract »    Full Text »    PDF »
Appearance-Based Topological Bayesian Inference for Loop-Closing Detection in a Cross-Country Environment.
C. Chen and H. Wang (2006)
The International Journal of Robotics Research 25, 953-983
   Abstract »    PDF »
Reducing the dimensionality of data with neural networks..
G. E. Hinton and R. R. Salakhutdinov (2006)
Science 313, 504-507
   Abstract »    Full Text »    PDF »
Low-dimensional, free-energy landscapes of protein-folding reactions by nonlinear dimensionality reduction.
P. Das, M. Moll, H. Stamati, L. E. Kavraki, and C. Clementi (2006)
PNAS 103, 9885-9890
   Abstract »    Full Text »    PDF »
Non-linear PCA: a missing data approach.
M. Scholz, F. Kaplan, C. L. Guy, J. Kopka, and J. Selbig (2005)
Bioinformatics 21, 3887-3895
   Abstract »    Full Text »    PDF »
Temporal Dynamics of Shape Analysis in Macaque Visual Area V2.
J. Hegde and D. C. Van Essen (2004)
J Neurophysiol 92, 3030-3042
   Abstract »    Full Text »    PDF »
Protein ranking: From local to global structure in the protein similarity network.
J. Weston, A. Elisseeff, D. Zhou, C. S. Leslie, and W. S. Noble (2004)
PNAS 101, 6559-6563
   Abstract »    Full Text »    PDF »
Temporally Irregular Mnemonic Persistent Activity in Prefrontal Neurons of Monkeys During a Delayed Response Task.
A. Compte,, C. Constantinidis, J. Tegner, S. Raghavachari, M. V. Chafee, P. S. Goldman-Rakic, and X.-J. Wang (2003)
J Neurophysiol 90, 3441-3454
   Abstract »    Full Text »    PDF »
Local Context Finder (LCF) reveals multidimensional relationships among mRNA expression profiles of Arabidopsis responding to pathogen infection.
F. Katagiri and J. Glazebrook (2003)
PNAS 100, 10842-10847
   Abstract »    Full Text »    PDF »
Hessian eigenmaps: Locally linear embedding techniques for high-dimensional data.
D. L. Donoho and C. Grimes (2003)
PNAS 100, 5591-5596
   Abstract »    Full Text »    PDF »
A self-organizing principle for learning nonlinear manifolds.
D. K. Agrafiotis and H. Xu (2002)
PNAS 99, 15869-15872
   Abstract »    Full Text »    PDF »
Predicting Protein Cellular Localization Using a Domain Projection Method.
R. Mott, J. Schultz, P. Bork, and C. P. Ponting (2002)
Genome Res. 12, 1168-1174
   Abstract »    Full Text »    PDF »
Sensor-independent stimulus representations.
D. N. Levin (2002)
PNAS 99, 7346-7351
   Abstract »    Full Text »    PDF »
Core Biopsies Can Be Used to Distinguish Differences in Expression Profiling by cDNA Microarrays.
C. Sotiriou, C. Khanna, A. A. Jazaeri, D. Petersen, and E. T. Liu (2002)
J. Mol. Diagn. 4, 30-36
   Abstract »    Full Text »    PDF »
The Isomap Algorithm and Topological Stability.
M. Balasubramanian, E. L. Schwartz, J. B. Tenenbaum, V. de Silva, and J. C. Langford (2002)
Science 295, 7a
   Full Text »    PDF »
Improved recognition of native-like protein structures using a family of designed sequences.
P. Koehl and M. Levitt (2002)
PNAS 99, 691-696
   Abstract »    Full Text »    PDF »


To Advertise     Find Products

Science. ISSN 0036-8075 (print), 1095-9203 (online)