Hessian eigenmaps: Locally linear embedding techniques for high-dimensional data

We describe a method for recovering the underlying parametrization of scattered data (m(i)) lying on a manifold M embedded in high-dimensional Euclidean space. The method, Hessian-based locally linear embedding, derives from a conceptual framework of local isometry in which the manifold M, viewed as a Riemannian submanifold of the ambient Euclidean space R-n, is locally isometric to an open, connected subset Theta of Euclidean space R-d. Because Theta does not have to be convex, this framework is able to handle a significantly wider class of situations than the original ISOMAP algorithm. The theoretical framework revolves around a quadratic form H(f) = integral(M)parallel toH(f)(m)parallel to(F)(2)dm defined on functions f : M --> R. Here Hf denotes the Hessian of f, and H(f) averages the Frobenius norm of the Hessian over M. To define the Hessian, we use orthogonal coordinates on the tangent planes of M. The key observation is that, if M truly is locally isometric to an open, connected subset of R-d, then H(f) has a (d + 1)-dimensional null space consisting of the constant functions and a d-dimensional space of functions spanned by the original isometric coordinates. Hence, the isometric coordinates can be recovered up to a linear isometry. Our method may be viewed as a modification of locally linear embedding and our theoretical framework as a modification of the Laplacian eigen-maps framework, where we substitute a quadratic form based on the Hessian in place of one based on the Laplacian.