Quasi-Metrics to Compare Finite Sets of Points

62 Views Asked by At

Given two sets $S_1$ and $S_2$ of points in $\mathbb{R}^3$, where $|S_1|$ is not necessarily the same as $|S_2|$, what are some of the metrics that could be used to compare these two sets? I am aware of Wasserstein distance and Hausdorff distance, and am looking for related metrics that are not necessarily symmetric (i.e. quasi-metrics).

Any pointers would be very appreciated.

1

There are 1 best solutions below

0
On

Allow yourself to consider any finite set $A$ as an average of Dirac deltas $\mu_A = \frac{1}{|A|} \sum_{a\in A} \delta_a$ or as a plain sum $\nu_A=\sum_{a\in A} \delta_a$. If you are considering $A$ as the empirical measure $\mu_A$ then the wide assortment of probability metrics opens up to you. In addition to the Wasserstein metrics you have metrics such as the Lévy–Prokhorov metric, Total Variation metric, the square-root of the Jensen-Shannon divergence, and Integral Probability Metrics (IPMs) (not all IPMs are true metrics, but that class does include the 1-Wasserstein metric as a special case).

You can also take advantage of Hilbert spaces. You can realize both $\mu_A$ and $\nu_A$ inside the negative order Sobolev spaces $H^s(\mathbb{R}^n)$ for $s<-\tfrac{n}{2}$ and inside of reproducing kernel Hilbert spaces. Thus using the norms for those Hilbert spaces will induce a metric on your finite sets.

For metrics which don't assume a "measure-like" structure, you may be interested in "Distances Between Sets - A Survey" wherein Conci & Kubrusly lists many variants on the Hausdorff distance. Additionally they also mention additional variants of some probability metrics.