A Global Geometric Framework for Nonlinear Dimensionality Reduction

• DOI: 10.1126/science.290.5500.2319
• Publication Date: 2002-07-27T09:47:44Z
• Authors: Joshua B. Tenenbaum; Vin de Silva; John C. Langford
• Keywords: Isomap; Multidimensional scaling; Diffusion map; Handwriting

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