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.
Freiburg University

Site Tools

  • AAAS
  • Subscribe
  • Feedback

Site Search

Search Advanced

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:
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 »
A One-Dimensional Reaction Coordinate for Identification of Transition States from Explicit Solvent Pfold-Like Calculations.
D. A. C. Beck and V. Daggett (2007)
Biophys. J. 93, 3382-3391
   Abstract »    Full Text »    PDF »
Parametric embedding for class visualization..
T. Iwata, K. Saito, N. Ueda, S. Stromsten, T. L. Griffiths, and J. B. Tenenbaum (2007)
Neural Comput. 19, 2536-2556
   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 »
Nonlocal Estimation of Manifold Structure..
Y. Bengio, M. Monperrus, and H. Larochelle (2006)
Neural Comput. 18, 2509-2528
   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 »
Visual Characterization of Paper Using Isomap and Local Binary Patterns.
M. TURTINEN, M. PIETIKAINEN, and O. SILVEN (2006)
IEICE Trans D: Information E89-D, 2076-2083
   Abstract »    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 »
Incremental Online Learning in High Dimensions.
S. Vijayakumar, A. D'Souza, and S. Schaal (2005)
Neural Comput. 17, 2602-2634
   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 »
Facial Attractiveness: Beauty and the Machine.
Y. Eisenthal, G. Dror, and E. Ruppin (2005)
Neural Comput. 18, 119-142
   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 »
Learning Eigenfunctions Links Spectral Embedding and Kernel PCA.
Y. Bengio, O. Delalleau, N. Le Roux, J.-F. Paiement, P. Vincent, and M. Ouimet (2004)
Neural Comput. 16, 2197-2219
   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 »
Is There Something Out There? Inferring Space from Sensorimotor Dependencies.
D. Philipona, J.K. O'Regan, and J.-P. Nadal (2003)
Neural Comput. 15, 2029-2049
   Abstract »    Full Text »
Exploring the nonlinear geometry of protein homology.
M. A. Farnum, H. Xu, and D. K. Agrafiotis (2003)
Protein Sci. 12, 1604-1612
   Abstract »    Full Text »    PDF »
Laplacian Eigenmaps for Dimensionality Reduction and Data Representation.
M. Belkin and P. Niyogi (2003)
Neural Comput. 15, 1373-1396
   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 »


ADVERTISEMENT
Click Me!

ADVERTISEMENT

To Advertise     Find Products