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

במתמטיקה, הלמה של ג'ונסון ולינדנשטראוס, הוכחה בשנת 1984 על ידי ויליאם ג'ונסון ויורם לינדנשטראוס, נוגעת להיטל של נקודות ממרחב אוקלידי במימד גבוה למימד נמוך. הלמה אומרת שניתן לשכן 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.