10.1162/153244304322972667
Applied Physics LettersPublished 1 January 2000Open access
Citations353
SJR quartileQ1
SJR score0.90
SNIP1.00
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Locally linear embedding (LLE) is described, an unsupervised learning algorithm that computes low dimensional, neighborhood preserving embeddings of high dimensional data that relates to previous and ongoing work in nonlinear dimensionality reduction.
Abstract
This DOI is not currently attached to any metadata records. DOIs can’t actually ever be deleted (they’re persistent), but sometimes our members create DOIs in error. We do have a process to approximate deletion which we follow only in rare cases where the DOI has been genuinely created in error, and most crucially, if the DOI has never been published anywhere online or in print and never otherwise distributed to or communicated with anyone (authors, readers, reviewers, etc.
Keywords
Arts and HumanitiesHealth Professions
Journal of the Royal Statistical Society Series B (Statistical Methodology)Maximum Likelihood from Incomplete Data Via the <i>EM</i> Algorithm
49,657 Citations1977A. P. Dempster, N. M. Laird +1 more
IEEE Transactions on Pattern Analysis and Machine IntelligenceNormalized cuts and image segmentation
15,696 Citations2000Jianbo Shi, Jitendra Malik
ScienceNonlinear Dimensionality Reduction by Locally Linear Embedding
15,035 Citations2000Sam T. Roweis, Lawrence K. Saul
Locally linear embedding (LLE) is introduced, an unsupervised learning algorithm that computes low-dimensional, neighborhood-preserving embeddings of high-dimensional inputs that learns the global structure of nonlinear manifolds.
ScienceA Global Geometric Framework for Nonlinear Dimensionality Reduction
13,740 Citations2000Joshua B. Tenenbaum, Vin de Silva +1 more
An approach to solving dimensionality reduction problems that uses easily measured local metric information to learn the underlying global geometry of a data set and efficiently computes a globally optimal solution, and is guaranteed to converge asymptotically to the true structure.
Journal of the American Society for Information ScienceIndexing by latent semantic analysis
12,677 Citations1990Scott Deerwester, Susan Dumais +3 more
The MIT Press eBooksLearning with Kernels
9,548 Citations2001Bernhard Schölkopf, Alexander J. Smola
Learning with Kernels provides an introduction to SVMs and related kernel methods that provide all of the concepts necessary to enable a reader equipped with some basic mathematical knowledge to enter the world of machine learning using theoretically well-founded yet easy-to-use kernel algorithms.
Neural ComputationNonlinear Component Analysis as a Kernel Eigenvalue Problem
8,078 Citations1998Bernhard Schölkopf, Alexander J. Smola +1 more
A new method for performing a nonlinear form of principal component analysis by the use of integral operator kernel functions is proposed and experimental results on polynomial feature extraction for pattern recognition are presented.
SIAM Journal on ComputingDepth-First Search and Linear Graph Algorithms
6,021 Citations1972Robert E. Tarjan
The value of depth-first search or “backtracking” as a technique for solving problems is illustrated by two examples of an improved version of an algorithm for finding the strongly connected components of a directed graph.
The MIT Press eBooksLaplacian Eigenmaps and Spectral Techniques for Embedding and Clustering
4,535 Citations2002Mikhail Belkin, Partha Niyogi
The algorithm provides a computationally efficient approach to nonlinear dimensionality reduction that has locality preserving properties and a natural connection to clustering.
Springer series in information sciencesSelf-Organization and Associative Memory
3,820 Citations1988Teuvo Kohonen
AIChE JournalNonlinear principal component analysis using autoassociative neural networks
3,042 Citations1991Mark Kramer
The NLPCA method is demonstrated using time-dependent, simulated batch reaction data and shows that it successfully reduces dimensionality and produces a feature space map resembling the actual distribution of the underlying system parameters.
ACM Transactions on Mathematical SoftwareAn Algorithm for Finding Best Matches in Logarithmic Expected Time
2,765 Citations1977Jerome H. Friedman, Jon Bentley +1 more
IEEE Transactions on Pattern Analysis and Machine IntelligenceA database for handwritten text recognition research
2,237 Citations1994J.J. Hull
An image database for handwritten text recognition research is described that contains digital images of approximately 5000 city names, 5000 state names, 10000 ZIP Codes, and 50000 alphanumeric characters to overcome the limitations of earlier databases.
Queensland's institutional digital repository (The University of Queensland)Mixture models : inference and applications to clustering
2,074 Citations1988Geoffrey J. McLachlan, K. E. Basford
Society for Industrial and Applied Mathematics eBooksData Structures and Network Algorithms
2,067 Citations1983Robert E. Tarjan
This paper presents a meta-trees tree model that automates the very labor-intensive and therefore time-heavy and therefore expensive process of manually selecting trees to grow in a graph.
Neural ComputationMixtures of Probabilistic Principal Component Analyzers
1,903 Citations1999Michael E. Tipping, Chris Bishop
PCA is formulated within a maximum likelihood framework, based on a specific form of gaussian latent variable model, which leads to a well-defined mixture model for probabilistic principal component analyzers, whose parameters can be determined using an expectation-maximization algorithm.
Proceedings of the National Academy of SciencesHessian eigenmaps: Locally linear embedding techniques for high-dimensional data
1,696 Citations2003David L. Donoho, Carrie Grimes
The Hessian-based locally linear embedding method for recovering the underlying parametrization of scattered data (mi) lying on a manifold M embedded in high-dimensional Euclidean space is described, where the isometric coordinates can be recovered up to a linear isometry.
Information science and statisticsNonlinear Dimensionality Reduction
1,530 Citations2007John A. Lee, Michel Verleysen
The purpose of the book is to summarize clear facts and ideas about well-known methods as well as recent developments in the topic of nonlinear dimensionality reduction, which encompasses many of the recently developed methods.
Neural ComputationGTM: The Generative Topographic Mapping
1,389 Citations1998Chris Bishop, Markus Svensén +1 more
A form of nonlinear latent variable model called the generative topographic mapping, for which the parameters of the model can be determined using the expectation-maximization algorithm, is introduced.
Neural ComputationThe Helmholtz Machine
1,219 Citations1995Peter Dayan, Geoffrey E. Hinton +2 more
A way of finessing this combinatorial explosion by maximizing an easily computed lower bound on the probability of the observations is described, viewed as a form of hierarchical self-supervised learning that may relate to the function of bottom-up and top-down cortical processing pathways.
PsychometrikaNonmetric Individual Differences Multidimensional Scaling: An Alternating Least Squares Method with Optimal Scaling Features
960 Citations1977Yoshio Takane, Forrest W. Young +1 more
Neural NetworksTopology representing networks
887 Citations1994Thomas Martinetz, Klaus Schulten
This competitive Hebbian rule provides a novel approach to the problem of constructing topology preserving feature maps and representing intricately structured manifolds and makes this novel approach particularly useful in all applications where neighborhood relations have to be exploited or the shape and topology of submanifolds have to been take into account.
Lecture notes in computer scienceEfficient BackProp
867 Citations1998Yann LeCun, Léon Bottou +2 more
Many undesirable behaviors of backprop can be avoided with tricks that are rarely exposed in serious technical publications, and this paper gives some of those tricks, and offers explanations of why they work.
ScienceThe Manifold Ways of Perception
818 Citations2000H. Sebastian Seung, Daniel D. Lee
In an informative Perspective, Seung and Lee explain the mathematical intricacies of two new algorithms for modeling the variability of perceptual stimuli and other types of high-dimensional data.
NatureAn analogue approach to the travelling salesman problem using an elastic net method
810 Citations1987Richard Durbin, David Willshaw
This work describes how a parallel analogue algorithm, derived from a formal model for the establishment of topographically ordered projections in the brain, can be applied to the travelling salesman problem, and produces shorter tour lengths than another recent parallel analogue algorithms.
Neural ComputationDimension Reduction by Local Principal Component Analysis
723 Citations1997Nandakishore Kambhatla, Todd K. Leen
A local linear approach to dimension reduction that provides accurate representations and is fast to compute is developed and it is shown that the local linear techniques outperform neural network implementations.
Segmentation using eigenvectors: a unifying view
722 Citations1999Yaakov Weiss
A unified treatment of eigenvectors of block matrices based on eigendecompositions in the context of segmentation is given, and close connections between them are shown while highlighting their distinguishing features.
PsychometrikaEM Algorithms for ML Factor Analysis
602 Citations1982Donald B. Rubin, Dorothy T. Thayer
Scientific Repository (Petra Christian University)The EM algorithm for mixtures of factor analyzers
585 Citations1996Zoubin Ghahramani, GE Hinton
This work presents an exact Expectation{Maximization algorithm for determining the parameters of this mixture of factor analyzers which concurrently performs clustering and dimensionality reduction, and can be thought of as a reduced dimension mixture of Gaussians.
Neural ComputationIndependent Factor Analysis
508 Citations1999Hagai Attias
An expectation-maximization (EM) algorithm is presented, which performs unsupervised learning of an associated probabilistic model of the mixing situation and is shown to be superior to ICA since it can learn arbitrary source densities from the data.
Five Balltree Construction Algorithms
415 Citations2009Stephen M. Omohundro
This report compares 5 different algorithms for constructing ball trees from data and finds that the bottom up approach usually produces the best trees but has the longest construction time.
Learning Segmentation by Random Walks
370 Citations2000Marina Meilă, Jianbo Shi
This interpretation shows that spectral methods for clustering and segmentation have a probabilistic foundation and proves that the Normalized Cut method arises naturally from the framework.
Journal of the American Statistical AssociationPrincipal Curves
348 Citations1989Trevor Hastie, Werner Stuetzle
This article defines principal curves, an algorithm for their construction is given, some theoretical results are presented, and the procedure is compared to other generalizations ofprincipal components.
IEEE Transactions on ComputersAn Algorithm for Finding Intrinsic Dimensionality of Data
346 Citations1971Keinosuke Fukunaga, D.R. Olsen
An algorithm for the analysis of multivariant data is presented along with some experimental results, and an analysis that demonstrates the feasability of this approach.
Finding nearest neighbors in growth-restricted metrics
342 Citations2002David R. Karger, Matthias Rühl
This paper develops an efficient dynamic data structure for nearest neighbor queries in growth-constrained metrics that satisfy the property that for any point q and number r the ratio between numbers of points in balls of radius 2r and r is bounded by a constant.
IEEE Transactions on Neural NetworksModeling the manifolds of images of handwritten digits
329 Citations1997Geoffrey E. Hinton, Peter Dayan +1 more
Two new methods for modeling the manifolds of digitized images of handwritten digits of principal components analysis and factor analysis are described, based on locally linear low-dimensional approximations to the underlying data manifold.
SIAM Journal on Scientific ComputingJacobi--Davidson Style QR and QZ Algorithms for the Reduction of Matrix Pencils
319 Citations1998Diederik R. Fokkema, Gérard L. G. Sleijpen +1 more
Two algorithms, JDQZ for the generalized eigen problem and JDQR for the standard eigenproblem, that are based on the iterative construction of a (generalized) partial Schur form are presented, suitable for the efficient computation of several eigenvalues and the corresponding eigenvectors near a user-specified target value in the complex plane.
ScienceImage Representations for Visual Learning
270 Citations1996David Beymer, Tomaso Poggio
Computer vision researchers are developing new approaches to object recognition and detection that are based almost directly on images and avoid the use of intermediate three-dimensional models.
Mapping a Manifold of Perceptual Observations
251 Citations1997Joshua B. Tenenbaum
The isometric feature mapping procedure, or isomap, is able to reliably recover low-dimensional nonlinear structure in realistic perceptual data sets, such as a manifold of face images, where conventional global mapping methods find only local minima.
`N-Body' Problems in Statistical Learning
249 Citations2000Alexander Gray, Andrew Moore
A suite of new geometric techniques which are applicable in principle to any 'N-body' computation including large-scale mixtures of Gaussians, RBF neural networks, and HMM's are presented.
Intrinsic Dimension Estimation Using Packing Numbers
224 Citations2002Balázs Kégl
A new algorithm is proposed to estimate the intrinsic dimension of data sets based on geometric properties of the data and requires neither parametric assumptions on the data generating model nor input parameters to set.
IEEE Transactions on Pattern Analysis and Machine IntelligenceAn Intrinsic Dimensionality Estimator from Near-Neighbor Information
220 Citations1979Karl Pettis, Thomas A. Bailey +2 more
An intuitively appealing, noniterative estimator for intrinsic dimensionality which is based on nearneighbor information is proposed which works well in identifying the true dimensionality for a variety of artificial data sets and is fairly insensitive to the number of samples and to the algorithmic parameters.
NeurocomputingIndependent component analysis in the presence of Gaussian noise by maximizing joint likelihood
166 Citations1998Aapo Hyvärinen
It is shown that the presence of noise implies that the relation between the observed data and the estimates of the independent components is non-linear, and how to approximate thisNon-linearity is shown, and an efficient algorithm is proposed for approximate maximization of the likelihood.
CaltechAUTHORS (California Institute of Technology)Grouping and dimensionality reduction by locally linear embedding
147 Citations2001Marzia Polito, Pietro Perona
A variant of LLE that can simultaneously group the data and calculate local embedding of each group is studied, and an estimate for the upper bound on the intrinsic dimension of the data set is obtained automatically.
A unifying theorem for spectral embedding and clustering
141 Citations2003Matthew Brand, Kun Huang
A nonlinear dimensionality reduction (NLDR) algorithm for data sampled from manifolds whose intrinsic coordinate system has linear and cyclic axes, and a novel clustering-by-projections algorithm that requires no postprocessing and gives superior performance on challenge problems from the recent literature are constructed.
Pattern Recognition LettersA k-segments algorithm for finding principal curves
111 Citations2002Jakob Verbeek, Nikos Vlassis +1 more
An incremental method to find principal curves using line segments fitted and connected to form polygonal lines to meet a performance criterion is proposed.
Sample-based synthesis of photo-realistic talking heads
93 Citations2002Eric Cosatto, Hans Peter Graf
A system that generates photo-realistic video animations of talking heads from existing video footage using image recognition techniques, and uses precise multi channel facial recognition techniques to track facial parts, and derives the exact 3D position of the head, enabling the automatic extraction of normalized face parts.
Nonlinear Image Interpolation using Manifold Learning
90 Citations1994Christoph Bregler, Stephen M. Omohundro
This work describes an approach based on the abstract task of "manifold learning" and presents results on both synthetic and real image sequences to solve the problem of interpolating between specified images in an image sequence.
ScholarlyCommons (University of Pennsylvania)Learning High Dimensional Correspondences from Low Dimensional Manifolds
83 Citations2003Ji Hun Ham, Daniel D. Lee +1 more
This paper generalizes three methods in unsupervised learning—principal components analysis, factor analysis, and locally linear embedding— to discover subspaces and manifolds that provide common low dimensional representations of different high dimensional data sets and uses the shared representations discovered by these algorithms to put high dimensional examples from different data sets into correspondence.
ESO astrophysics symposiaFast Algorithms and Efficient Statistics: N-Point Correlation Functions
73 Citations2006Andrew Moore, Andrew J. Connolly +9 more
A new algorithm for the fast computation of N-point correlation functions in large astronomical data sets is presented, based on kdtrees which are decorated with cached sufficient statistics thus allowing for orders of magnitude speed-ups over the naive non-tree-based implementation of correlation functions.
IEEE Transactions on Speech and Audio ProcessingMaximum likelihood and minimum classification error factor analysis for automatic speech recognition
71 Citations2000L.K. Saul, Mazin G. Rahim
It is found that modeling feature correlations by factor analysis leads to significantly increased likelihoods and word accuracies, and the rate of improvement with model size often exceeds that observed in conventional HMM's.
Bumptrees for Efficient Function, Constraint and Classification Learning
71 Citations1990Stephen M. Omohundro
A new class of data structures called "bumptrees" is described, useful for efficiently implementing a number of neural network related operations and applications to density estimation, classification, and constraint representation and learning are outlined.
Pattern RecognitionData visualization by multidimensional scaling: a deterministic annealing approach
56 Citations2000Hansjörg Klock, Joachim M. Buhmann
A novel deterministic annealing algorithm is presented for SSTRESS and Sammon mapping, derived in the framework of maximum entropy estimation, and the superiority of this optimization technique compared to conventional gradient descent methods is demonstrated.
Neural ComputationSupervised Dimension Reduction of Intrinsically Low-Dimensional Data
53 Citations2002Nikos Vlassis, Yoichi Motomura +1 more
This article is proposing a supervised projection pursuit method that can be regarded as an extension of the single-index model for nonparametric regression and shows results from a toy and two robotic applications.
Lecture notes in statisticsUnsupervised Learning of Curved Manifolds
42 Citations2003Vin de Silva, Joshua B. Tenenbaum
A variant of the Isomap manifold learning algorithm, called C-Isomap, designed to recover mappings in the larger class of conformal embeddings, provided that the original sampling density is reasonably uniform.
Lecture notes in computer scienceCoordinating Principal Component Analyzers
39 Citations2002Jakob Verbeek, Nikos Vlassis +1 more
It is shown that a restricted form of the Mixtures of Probabilistic PCA model allows for a more efficient algorithm and results are provided to illustrate the viability method.
Periodic Component Analysis: An Eigenvalue Method for Representing Periodic Structure in Speech
37 Citations2000Lawrence K. Saul, Jont B. Allen
An eigenvalue method is developed for analyzing periodic structure in speech that avoids the inefficiencies of autocorrelation at the pitch period and correlates signals at a clock rate on the order of the actual pitch, as opposed to the original sampling rate.
Journal of the American Statistical AssociationInequality Restrictions in Regression Analysis
36 Citations1966George G. Judge, T. Takayama
Lecture notes in computer scienceGrouping with Directed Relationships
28 Citations2001Stella X. Yu, Jianbo Shi
The eigenvectors characterize the optimal partitioning in the complex phase plane, with phase angle separation determining the partitioning of vertices and the relative phase advance indicating the ordering of partitions.