کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4605165 | 1337551 | 2012 | 21 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: An efficient tree-based computation of a metric comparable to a natural diffusion distance An efficient tree-based computation of a metric comparable to a natural diffusion distance](/preview/png/4605165.png)
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.
Journal: Applied and Computational Harmonic Analysis - Volume 33, Issue 2, September 2012, Pages 261-281