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 ℝ n, is locally isometric to an open, connected subset Θ of Euclidean space ℝ d. Because Θ 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 ℋ (f) = ∫ M ∥ H f (m) ∥ 12ptminimal amsmath wasysym amsfonts amssymb amsbsy mathrsfs -69pt document equation*{₅^{2}}equation*document dm defined on functions f: M ↦ ℝ. Here Hf denotes the Hessian of f, and ℋ (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 ℝ d, then ℋ (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 eigenmaps framework, where we substitute a quadratic form based on the Hessian in place of one based on the Laplacian.