הלמה של ג'ונסון ולינדנשטראוס

במתמטיקה, הלמה של ג'ונסון ולינדנשטראוס (על שם המתמטיקאים ויליאם ג'ונסון ויורם לינדנשטראוס) נוגעת להיטל של נקודות ממרחב אוקלידי בממד גבוהה לממד נמוך.

הלמה אומרת שניתן לשכן $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.

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0