An efficient tree-based computation of a metric comparable to a natural diffusion distance

Using diffusion to define distances between points on a manifold (or a sampled data set) has been successfully employed in various applications such as data organization and approximately isometric embedding of high dimensional data in low dimensional Euclidean space. Recently, P. Jones has proposed a diffusion distance which is both intuitively appealing and scales appropriately with increasing time. In the first part of our paper, we present an efficient tree-based approach to computing an approximation to Jonesʼs diffusion distance. We also show our approximation is comparable to Jonesʼs distance. Neither Jonesʼs distance, nor our approximation, satisfies the triangle inequality; in particular, in the case of heat flow on Rn, Jonesʼs separation distance gives a scaled square of the Euclidean distance. In the second part of our paper, we present a general construction to obtain an “almost” metric from a general distance. We also discuss a numerical procedure to implement our construction. Additionally, we show that in the case of heat flow on Rn, we recover (scaled) Euclidean distance from Jonesʼs distance.