Efficient, sparse representation of manifold distance matrices for
  classical scaling
  Geodesic distance matrices can reveal shape properties that are largely
invariant to non-rigid deformations, and thus are often used to analyze and
represent 3-D shapes. However, these matrices grow quadratically with the
number of points. Thus for large point sets it is common to use a low-rank
approximation to the distance matrix, which fits in memory and can be
efficiently analyzed using methods such as multidimensional scaling (MDS). In
this paper we present a novel sparse method for efficiently representing
geodesic distance matrices using biharmonic interpolation. This method exploits
knowledge of the data manifold to learn a sparse interpolation operator that
approximates distances using a subset of points. We show that our method is 2x
faster and uses 20x less memory than current leading methods for solving MDS on
large point sets, with similar quality. This enables analyses of large point
sets that were previously infeasible.
