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

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

ניסוח הלמהעריכה

יהי   ו   קבוצת נקודות בגודל  .

אז, לכל  , קיימת העתקה ליניארית   כך ש:

 

לכל  

גרסה הסתברותית של הלמהעריכה

קיימת גרסה נוספת של הלמה הטוענת טענה מקבילה עבור התפלגויות של העתקות:

יהי   ויהי d שלם חיובי. אז עבור  

קיימת התפלגות על מרחב המטריצות בגודל   כך שלכל וקטור יחידה   מתקיים:

 

לקריאה נוספתעריכה