Lemma von Johnson-Lindenstrauss

Unter dem Lemma von Johnson-Lindenstrauss versteht man in der Mathematik ein Resultat über die verzerrungsarme Einbettung von Punkten aus einem hochdimensionalen in einen niedrig-dimensionalen euklidischen Raum. Nach diesem Lemma ist es möglich, eine Menge von Punkten eines hochdimensionalen Raumes so in einem Raum mit deutlich niedriger Dimension einzubetten, dass die Distanzen zwischen den Punkten bis auf einen Faktor erhalten bleiben.

Benannt ist das Lemma nach den beiden Mathematikern William B. Johnson und Joram Lindenstrauss, die das Lemma erstmals im Jahr 1984 bewiesen.

Lemma

Sei $0<\varepsilon <1$ und $n\in \mathbb {N}$ beliebig. Sei $k\in \mathbb {N}$ so, dass

$k\geq 4(\varepsilon ^{2}/2-\varepsilon ^{3}/3)^{-1}\ln(n)$.

Dann gilt: Für jede aus $n$ Punkten bestehende Menge ${\mathcal {P}}\subset \mathbb {R} ^{d}$, existiert eine lineare Abbildung $f:\mathbb {R} ^{d}\to \mathbb {R} ^{k}$, so dass für alle $v,w\in {\mathcal {P}}$

$(1-\varepsilon )\|v-w\|_{2}^{2}\leq \|f(v)-f(w)\|_{2}^{2}\leq (1+\varepsilon )\|v-w\|_{2}^{2}$.

Kurz formuliert zeigt das Lemma, dass eine Menge von $n$ Punkten in einem hochdimensionalen Raum linear in einen ${\mathcal {O}}(\varepsilon ^{-2}\ln(n))$-dimensionalen Raum eingebettet werden kann, so dass sich die Distanz zwischen zwei Punkten höchstens um einen Faktor $(1\pm \varepsilon )$ ändert.

Anwendungen

Das Lemma spielt vor allem im Bereich der Data-Science-Mathematik eine fundamentale Rolle. Dies liegt darin begründet, dass viele auf Computern verwendete Daten wie Bilder und Texte als Punkte in einem hochdimensionalen Raum betrachtet werden können.