Ein elementarer Beweis eines Theorems von Johnson und Lindenstrauss

Zusammenfassung Ein Ergebnis von Johnson und Lindenstrauss 13 zeigt, dass eine Menge von n Punkten im hochdimensionalen euklidischen Raum in einen O( log n/ϵ 2 )‐dimensionalen euklidischen Raum abgebildet werden kann, sodass sich der Abstand zwischen zwei Punkten nur um einen Faktor von (1 ± ϵ) ändert. In dieser Arbeit beweisen wir dieses Theorem mit elementaren probabilistischen Techniken. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 22: 60–65, 2002