Publikace na Matematicko-fyzikální fakulta |
2008
Abstrakt
Lemma Johnsona a Lindenstrausse lemma říká, že každá n-bodová množina v euklidovském prostoru se dá vnořit do euklidovského prostoru dimenze k=O(epsilon^{-2} log n) tak, že všechny vzdálenosti mezi body jsou zachovány až na multiplikativní faktor mezi 1-epsilon a 1+epsilon. Ve známých důkazech se takové vnoření dostane z lineárního zobrazení R^n do R^k s vhodnou náhodnou maticí.
V článku je podán jednoduchý a elementární důkaz, který zahrnuje jak původní verzi, tak pozdější algoritmicky výhodnější verze od Achlioptase.