|
Applied Math Seminar Can these things really work? Theoretical Results for ISOMAP and Locally Linear Embedding (LLE) |
|
In two recent articles in Science, new algorithms were proposed 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 of a data manifold. The second algorithm, LLE (Roweis and Saul, 2000) learns a global representation by computing local patches at each data point. Both algorithms have demonstrated promising empirical results for image databases with applications in face and character recognition. We develop a theoretical `continuum' framework for understanding each algorithm under perfect sampling of the data manifold. This framework gives predictive power to consider cases where the algorithms will perfectly recover the underlying parametrization of the data space, indpendent of sampling and pixelization effects. For ISOMAP, the resulting theoretical criterion for success is straightforward and surprisingly 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 require more complicated local machinery and may preclude an exact solution. In the case of LLE, we show that the algorithm is associated with a variational problem involving differential operators. The resulting solution will not in general perfectly recover the underlying parametrization, although in some special cases the result is qualitatively similarl. We instead propose a modified variational problem with an accompanying empirical algorithm (Hessian LLE), which will always recover the underlying parametrization (up to a linear transformation). |