new JMLR paper: Think Globally, Fit Locally: Unsupervised Learning of Low Dimensional Manifolds

[David 'Pablo' Cohn]

[posted to connectionists at the request of the authors]

The Journal of Machine Learning Research (www.jmlr.org) is pleased to
announce publication of the seventh paper in Volume 4:

--------------------------

Think Globally, Fit Locally: Unsupervised Learning of
Low Dimensional Manifolds

Lawrence K. Saul and Sam T. Roweis
JMLR 4(Jun):119-155, 2003

Abstract

The problem of dimensionality reduction arises in many fields of
information processing, including machine learning, data compression,
scientific visualization, pattern recognition, and neural computation.
Here we describe locally linear embedding (LLE), an unsupervised
learning algorithm that computes low dimensional, neighborhood
preserving embeddings of high dimensional data. The data, assumed to be
sampled from an underlying manifold, are mapped into a single global
coordinate system of lower dimensionality. The mapping is derived from
the symmetries of locally linear reconstructions, and the actual
computation of the embedding reduces to a sparse eigenvalue problem.
Notably, the optimizations in LLE---though capable of generating highly
nonlinear embeddings---are simple to implement, and they do not involve
local minima. In this paper, we describe the implementation of the
algorithm in detail and discuss several extensions that enhance its
performance. We present results of the algorithm applied to data sampled
from known manifolds, as well as to collections of images of faces,
lips, and handwritten digits. These examples are used to provide
extensive illustrations of the algorithm's performance---both successes
and failures---and to relate the algorithm to previous and ongoing work
in nonlinear dimensionality reduction. Optimally-Smooth Adaptive 

----------------------------------------------------------------------------
This paper is available electronically at http://www.jmlr.org in
PostScript and PDF formats. The papers of Volumes 1, 2 and 3 are also
available electronically from the JMLR website, and in hardcopy from the
MIT Press; please see http://mitpress.mit.edu/JMLR for details.

-David Cohn, <david.cohn at acm.org>