Local Quadrature Reconstruction on Smooth Manifolds

Bhuwan Dhingra and Dr. Amitabha Mukerjee (IIT Kanpur)
July, 2013

Overview

Non-Linear Dimensionality Reduction (NLDR) techniques such as ISOMAP, LLE, Laplacian Eigenmaps etc. attempt to estimate low-dimensional latent descriptors for data assumed to be drawn from an m-dimensional manifold in an ambient n-dimensional space. Out-of-Sample Extension - the problem of estimating the latent vectors for novel data - has attracted considerable attention in the literature. Here we consider the opposite problem, that of reconstructing new high-dimensional points, given a novel latent-vector in a previously discovered embedding. Such a procedure finds relevance in applications such as video frame interpolation or robot motion planning.

Some global methods can be applied to the problem, but these are polynomials on the total number of data points N resulting in a complexity of O(N3), where N is often in the thousands. In contrast, we propose a Local Quadrature Reconstruction (LQR) approach that looks at only the local k-neighbourhood for which the complexity reduces to O(k3) (k may be about 10). LQR achieves low error by estimating the second order error terms based on a differential geometric formulation for a small neighbourhood around the query point on the manifold. Main features of LQR include its fast reconstruction time and lack of a training phase, but since k increases as O(m2) it is currently limited to manifolds with low intrinsic dimension.

Local Quadrature Reconstruction

LQR proceeds in three steps:

  • Principal Components Analysis (PCA) on k-NN of the novel point. First m are along the tangent space and next d (<< n-m) along the normal space.
  • Linear Interpolation to find projection of novel point onto the tangent space.
  • Quadratic Regression along each normal space component to fine tune the projection.

External Links