Distanzfunktion

Distanzfunktionen sind bestimmte reellwertige Abbildungen metrischer Räume, die die Eigenschaften der zugrunde liegenden Metrik auf einstellige Funktionen übertragen. Das Konzept von Distanzfunktionen wurde 2011 von Chazal, Cohen-Steiner und Mérigot eingeführt und besitzt unter anderem Anwendungsmöglichkeiten in der geometrischen und der stochastischen Maßtheorie sowie im Data-Mining.[1]

Definition

Sei ${\displaystyle (X;d_{X})}$ ein nicht-leerer metrischer Raum, dessen Metrik ohne Beschränkung der Allgemeinheit durch eine Norm ${\displaystyle \|.\|_{X}}$ induziert sei (vgl. Satz von Kunugui).

Eine Distanzfunktion auf ${\displaystyle X}$ ist nun eine Abbildung ${\displaystyle d\colon X\to \mathbb {R} _{0}^{+}}$ (die also keine negativen Werte annimmt), mit den folgenden drei Eigenschaften:

1. Die Funktion selbst ist 1-Lipschitz-stetig: Für je zwei Punkte ${\displaystyle x;y\in X}$ gilt also ${\displaystyle |d(x)-d(y)|\leq \|x-y\|_{X}}$
2. Das Quadrat der Funktion ist 1-semikonkav: Dies ist äquivalent dazu, dass ${\displaystyle x\mapsto d(x)^{2}-\|x\|_{X}^{2}}$ eine konkave Funktion ist.
3. Die Funktion divergiert, wann immer die Norm es tut: Für jedes Netz ${\displaystyle (x_{i})_{i\in I}}$ in ${\displaystyle X}$ mit ${\displaystyle \|x_{i}\|_{X}\to \infty }$ gilt auch ${\displaystyle d(x_{i})\to \infty }$.

Pseudo-Distanzfunktion

Streng genommen genügt es bereits, die zweite und dritte Eigenschaft der obigen Definition zu fordern, da aus der 1-Semikonkavität des Quadrates einer Funktion bereits die 1-Lipschitz-Stetigkeit der ursprünglichen Abbildung folgt.[2] Allerdings ist die erste Eigenschaft anschaulich genau das, was eine Funktion distanzartig macht: Es lässt sich leicht nachrechnen, dass ${\displaystyle d}$ genau dann 1-Lipschitz-stetig ist, wenn sie mit der Metrik ${\displaystyle d_{X}}$ verträglich ist, wenn also für je zwei Elemente ${\displaystyle x;y\in X}$ stets ${\displaystyle d(x)\leq d(y)+d_{X}(x;y)}$ gilt.

In abschwächender Sprechweise wird eine Funktion ${\displaystyle d\colon X\to \mathbb {R} _{0}^{+}}$ daher auch Pseudo-Distanzfunktion genannt, wenn sie 1-Lipschitz-stetig ist und mit der Norm divergiert.

Distanzfunktion zu einer Menge

Der Prototyp einer Distanzfunktion ist der Abstand zu einer kompakten Teilmenge ${\displaystyle K\subseteq X}$, der durch ${\displaystyle d_{K}(x)=\inf _{k\in K}\|x-k\|_{X}}$ erklärt wird.[3] Die Kompaktheit bewirkt hier, dass das Infimum stets für mindestens einem Punkt aus ${\displaystyle K}$ tatsächlich angenommen wird. Die 1-Lipschitz-Stetigkeit folgt dann aus der Dreiecksungleichung.

Distanzfunktion zu einem Maß

Sei nun ${\displaystyle X}$ zusätzlich mit einem Maß ${\displaystyle \mu }$ versehen und ${\displaystyle 0\leq m<\mu (X)}$ eine reelle Zahl, so lässt sich zeigen, dass durch

${\displaystyle \delta _{\mu ;m}(x)=\inf\{r>0|\mu ({\overline {B}}_{r}(x))>m\}}$

eine Pseudo-Distanzfunktion erklärt ist, wobei ${\displaystyle {\overline {B}}_{r}(x)=\{y\in X|d_{X}(x;y)\leq r\}}$ die abgeschlossene Kugel um ${\displaystyle x}$ mit Radius ${\displaystyle r}$ bezeichne.[3]

Für jede reelle Zahl ${\displaystyle 0<m_{0}<\mu (X)}$ heiße nun die Abbildung

${\displaystyle d_{\mu ;m_{0}}\colon X\to \mathbb {R} _{0}^{+};\ x\mapsto {\sqrt {{\frac {1}{m_{0}}}\int _{0}^{m_{0}}\delta _{\mu ;m}(x)^{2}\ \mathrm {d} m}}}$

die Distanzfunktion zum Maß ${\displaystyle \mu }$ mit Parameter ${\displaystyle m_{0}}$.

Differenzierbarkeit

Nach d​em Satz v​on Rademacher s​ind (Pseudo-)Distanzfunktionen fast überall metrisch differenzierbar, d​a sie Lipschitz-stetig sind.

Ist speziell ${\displaystyle X=\mathbb {R} ^{n}}$ euklidisch, dann folgt aus dem Satz von Alexandrow mit der Semikonkavität des Quadrates auch die zweifache (totale) Differenzierbarkeit von Distanzfunktionen fast überall.

Dies ermöglicht e​ine eingehende Untersuchung v​on Distanzfunktionen u​nd den zugrunde liegenden Räumen d​urch die Betrachtung d​es Gradienten vergleichbar m​it der Morsetheorie i​n der Differentialtopologie.[4]

Einzelnachweise

1. Frédéric Chazal, David Cohen-Steiner, Quentin Mérigot: Geometric Inference for Probability Measures. In: Foundations of Computational Mathematics. Bd. 11, Nr. 6, 2011, ISSN 1615-3375, S. 733–751, doi:10.1007/s10208-011-9098-0, (online PDF; 628 kB).
2. Frédéric Chazal, David Cohen-Steiner, Quentin Mérigot: Geometric Inference for Probability Measures. In: Foundations of Computational Mathematics. Bd. 11, Nr. 6, 2011, ISSN 1615-3375, S. 733–751, Proposition 3.1, doi:10.1007/s10208-011-9098-0, (online PDF; 628 kB).
3. Frédéric Chazal, David Cohen-Steiner, Quentin Mérigot: Geometric Inference for Probability Measures. In: Foundations of Computational Mathematics. Bd. 11, Nr. 6, 2011, ISSN 1615-3375, S. 733–751, Section 3, doi:10.1007/s10208-011-9098-0, (online PDF; 628 kB).
4. Karsten Grove: Critical Point Theory for Distance Functions. In: Proceedings of Symposia in Pure Mathematics. Bd. 54, Nr. 3, 1993, ISSN 0082-0717, S. 357–385, (Grove gebraucht hier den Begriff distance function im Sinne obiger Definition, ohne jedoch die umfassende Theorie von Chazal et al. vorwegzunehmen.).