Efficient, sparse representation of manifold distance matrices for classical scaling
Abstract
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