Computer Science Colloquium
Statistics, Geometry, Computation:
Searching for Low Dimensional Manifolds in High Dimensional Data
Lawrence Saul
UPenn
Monday, February 28, 2005 11:15 A.M.
Room 1302 Warren Weaver Hall
251 Mercer Street
New York, NY 100121185
Directions: http://cs.nyu.edu/csweb/Location/directions.html
Colloquium Information: http://cs.nyu.edu/csweb/Calendar/colloquium/index.html
Hosts:
Yann LeCun yann@cs.nyu.edu, (212) 9983283
Abstract
How can we detect low dimensional structure in high dimensional data? If
the data is mainly confined to a low dimensional subspace, then simple
linear methods can be used to discover the subspace and estimate its
dimensionality. More generally, though, if the data lies on (or near) a
low dimensional manifold, then its structure may be highly nonlinear,
and linear methods are bound to fail.
The last few years have witnessed several advances in the problem of
nonlinear dimensionality reduction. Given high dimensional data sampled
from a low dimensional manifold, we now have several frameworks for
estimating the data's intrinsic dimensionality and computing a faithful
low dimensional embedding. Surprisingly, the main computations for
"manifold learning" are based on highly tractable optimizations, such as
nearestneighbor searches, least squares fits, eigenvalue problems, and
semidefinite programming.
Building on elementary ideas from convex optimization, spectral graph
theory, and differential geometry, I will describe two recent approaches
that we have developed for the problem of nonlinear dimensionality
reduction: one for computing distancepreserving (isometric) embeddings,
the other for computing anglepreserving (conformal) embeddings. The
resulting algorithms can be understood in terms of simple physical
intuitions. In practice, the embeddings computed by these algorithms
are quite useful for the visualization and analysis of high dimensional
data sets. I will also discuss several applications to problems in
image, speech, and language processing.
top  contact webmaster@cs.nyu.edu
