Diffusion EMD can be computed in $\tilde(n)$ time and is more accurate than similarly fast algorithms such as tree-based EMDs. In such cases where the graph is a discretization of an underlying Riemannian closed manifold, we prove that Diffusion EMD is topologically equivalent to the standard EMD with a geodesic ground distance. We model the datasets as distributions supported on common data graph that is derived from the affinity matrix computed on the combined data. Links to: GitHub, Preprint, Paper, Poster, Video, Tweetorial, and SlidesĪbstract: We propose a new fast method of measuring distances between large numbers of related high dimensional datasets called the Diffusion Earth Mover's Distance (EMD). Diffusion Earth Mover’s Distance and Distribution EmbeddingsĪlexander Tong*, Guillaume Huguet*, Amine Natik*, Kincaid MacDonald, Manik Kuchroo, Ronald Coifman, Guy Wolf, Smita Krishnaswamy In followup work we show that using a smaller number of scales, can be interpreted as an approximation of the unbalanced transport, and has numerical advantages. This can be computed in log-linear time with Diffusion EMD instead of quadratic time using other EMD approximations. This approximation is particularly useful when we would like to compute the nearest-EMD-neighbor distributions, which is the first step in low-dimensional non-linear embeddings such as PHATE and is the goal of PhEMD. Summary: The Diffusion Earth Mover’s Distance embeds distributions on a graph into a vector space where the L1 distance between embeddings approximates an earth mover’s distance between distributions with a ground distance represented by the geodesics along the underlying continuous data manifold.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |