Estimating and Computing Density Based Distance Metrics

Abstract

Density-based distance metrics have applications in semi-supervised learning, nonlinear interpolation and clustering. We consider density-based metrics induced by Riemannian manifold structures and estimate them using kernel density estimators for the underlying data distribution. We lower bound the rate of convergence of these plug-in path-length estimates and hence of the metric, as the sample size increases. We present an upper bound on the rate of convergence of all estimators of the metric. We also show that the metric can be consistently computed using the shortest path algorithm on a suitably constructed graph on the data samples and lower bound the convergence rate of the computation error. We present experiments illustrating the use of the metrics for semi-supervised classification and non-linear interpolation.