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

Abstract

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 )∥ \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \setlength{\oddsidemargin}{-69pt} \begin{document} \begin{equation*}{\mathrm{_{{\mathit{F}}}^{2}}}\end{equation*}\end{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.