הלמה של ג'ונסון ולינדנשטראוס
במתמטיקה, הלמה של ג'ונסון ולינדנשטראוס (על שם המתמטיקאים ויליאם ג'ונסון ויורם לינדנשטראוס) נוגעת להיטל של נקודות ממרחב אוקלידי בממד גבוהה לממד נמוך.
הלמה אומרת שניתן לשכן $ m $ נקודות מ־$ \mathbb {R} ^{N} $ במרחב מממד נמוך יותר (התלוי רק ב־$ m $ ובדיוק הרצוי), בלי לשנות יותר מדי את המרחקים בין הנקודות. ללמה שימושים בקרובי מטריצות, הורדת ממדים ועוד.
ניסוח הלמה
יהי $ 0<\varepsilon <1 $ ו־$ X\subset \mathbb {R} ^{N} $ קבוצת נקודות בגודל $ m $ .
אזי לכל $ n>ln(m)/\varepsilon ^{2} $ קיימת העתקה לינארית $ f:\mathbb {R} ^{N}\to \mathbb {R} ^{n} $ עבורה
- $ (1-\varepsilon )\|u-v\|^{2}\leq \|f(u)-f(v)\|^{2}\leq (1+\varepsilon )\|u-v\|^{2} $
לכל $ u,v\in X $ .
גרסה הסתברותית של הלמה
קיימת גרסה נוספת של הלמה הטוענת טענה מקבילה עבור התפלגויות של העתקות:
יהי $ 0<\varepsilon ,\delta <{\frac {1}{2}} $ ויהי $ d $ שלם חיובי. אז עבור $ k={\mathcal {O}}(\varepsilon ^{-2}\log(1/\delta )) $ קיימת התפלגות על מרחב המטריצות בגודל $ k\times d $ כך שלכל וקטור $ x\in \mathbb {R} ^{d} $ מתקיים
- $ P(|\Vert Ax\Vert _{2}^{2}-1|>\varepsilon )<\delta $
לקריאה נוספת
- Johnson, William B.; Lindenstrauss, Joram (1984), "Extensions of Lipschitz mappings into a Hilbert space", Conference in Modern Analysis and Probability (New Haven, Conn., 1982), Contemporary Mathematics, vol. 26, Providence, RI: American Mathematical Society, pp. 189–206, doi:10.1090/conm/026/737400, MR 0737400.
