Title: ISOMAP and LLE: analysis
of recent developments in dimensionality reduction
Abstract:
Two new algorithms were recently proposed in Science
to represent nonlinear data manifolds in lower dimensional spaces. The first
algorithm, ISOMAP (Tenenbaum et al., 2000), uses an
assumed isometry to produce a global low-dimensional
representation. The second algorithm, LLE (Roweis and
Saul, 2000), learns a global manifold representation from local patches. Both
algorithms have demonstrated promising empirical results in a number of
applications, including image libraries.
This talk develops a theoretical `continuum' framework
for these algorithms under perfect sampling of the data manifold. The
theoretical framework gives predictive power to consider cases where the
algorithms will perfectly recover the underlying parametrization
of the data space, independent of sampling and pixelization
effects.
For ISOMAP, the resulting strict theoretical criterion
for success predicts perfect recovery (up to a coordinate transformation) for a
variety of simple image libraries. However, several natural imaging effects
such as occlusion, non-convex sampling, and perspective transformations
demonstrably alter the structure of the data manifold in such a way as to require
more complicated machinery to construct a solution.
In the case of LLE, we show that the algorithm is
associated with a variational problem involving
differential operators on the data manifold. The resulting solution will not in
general recover the underlying parametrization,
although in some special cases the result is qualitatively similar. We instead
propose a modified variational problem with an
accompanying empirical algorithm (Hessian LLE) that will predictably recover an
isometric parametrization under a relaxation of the
convexity conditions associated with ISOMAP.
(Joint work with David Donoho)