רוחב גאוסי

**רוחב [[גאוס| גאוסי]]** הוא גודל סקלרי המוגדר לכל קבוצה במרחב מכפלה פנימית סוף-ממדי, אשר מאפשר למדוד, במובן מסוים, את גודלה ומלמד על תכונותיה הגאומטריות. בעזרתו ניתן להגדיר עוד מושגים גאומטריים קשורים, כגון גרסה של מושג המימד, אשר תופסים היבטים גאומטריים משמעותיים של הקבוצה.

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

## הגדרה
### רוחב בכיוון נתון
ממוזער|400x400 פיקסלים|רוחב הקבוצה <math>K</math> בכיוון <math>\theta</math> . בכחול: העל-מישורים התומכים בכיוונים הנגדיים <math>\theta, -\theta</math>.
תהא K תת-קבוצה של \mathbb{R}^n המצויד במכפלה הפנימית האוקלידית. בהינתן כיוון כלשהו S^{n-1}\ni\theta, נוכל להגדיר את **רוחבה של <math>K</math> בכיוון <math>\theta</math>** על-ידי \sup_{x, y \in K} \langle \theta, x-y \rangle(ראו איור).

ניתן לראות שביטוי זה שווה ל- h_{K-K}(\theta) = h_{K}(\theta) + h_{K}(-\theta) , כאשר h_{K}( \theta) = \sup_{x \in K} \langle x,\theta \rangle היא פונקציית התומך  של K.

קל לראות שקוטר הקבוצה הוא רוחבה המרבי, ואך טבעי להתעניין ברוחבה הממוצע, אשר בוודאי מכיל אף הוא מידע גאומטרי על הקבוצה.

### רוחב ספרי ורוחב גאוסי
ה**רוחב הספרי** (לעיתים נקרא גם ה**רוחב הממוצע**) של קבוצה \mathbb{R}^{n}\supseteq K  מוגדר על-ידי:

w_s(K) = 
\mathbb{E}
 \sup_{x \in K} \langle x, \theta \rangle
=
\int_{S^{n-1}} h_{K}(\theta) d\sigma_{n-1}(\theta)

כאשר בתוחלת  לעיל, \theta מתפלגת אחיד על הספירה.
מובן כי מתקיים w_s(K) = \frac{1}{2}\int_{S^{n-1}} h_{K-K}(\theta)d\sigma_{n-1}(\theta) = \frac{1}{2}w_{s}(K-K), כלומר, הרוחב הספרי הוא מחצית הממוצע של הרוחב בכל כיוון.

באופן דומה, ניתן להחליף את המשתנה האחיד על הספירה במשתנה גאוסי סטנדרטי ונקבל את **הרוחב הגאוסי** של הקבוצה:
,w(K) = 
\mathbb{E}
 \sup_{x \in K} \langle x, g \rangle

כאשר g \sim N(0,I_{n}).

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

על-ידי חלוקה לחלק הספירי והרדיאלי באינטגרציה, מקבלים כי w(K) = c_n w_s(K)  עבור c_n = \frac{\sqrt2 \Gamma\left(\frac{n+1}{2}\right)}{\Gamma\left( \frac{n}{2}+1\right)}, כאשר \Gamma היא פונקציית גמא. לאור זאת, מושג הרוחב הספרי והרוחב הגאוסי שקולים, והעדפת השימוש באחד על פני משנהו תלויה בנוחיות והתאמה לסיטואציה.

#### הערות
* הנחת סופיות המימד: בעוד שהרוחב בכיוון מסוים עודנו מוגדר היטב גם במרחב הילברט כללי, וכך גם המושג של משתנה גאוסי במקרה הספרבילי, לא נוכל למצע כראוי שכן המידה הגאוסית על הספירה אינה מידת הסתברות. על-כן, נדון ברוחב גאוסי במרחבים סוף ממדיים בלבד.
* הנחת האוקלידיות: ניתן להגדיר באותו אופן את הרוחב ביחס למכפלה פנימית כלשהי, אך מקודת מבט אסימפטוטית, אין בכך צורך, שכן הגדלים הללו שקולים מבחינה אסימפטוטית, לאור ההתאמה בין מכפלות פנימיות למטריצות חיוביות לחלוטין.
* יש מקומות בספרות שמגדירים את הרוחב הספרי/גאוסי  של K כתוחלת של הפונקציה h_{K-K} (לפי מידת ההסתברות המתאימה) ולא של h_K כפי שהגדרנו לעיל, שכן ערך זה הוט ממוצע הרוחב. כפי שראינו, ההגדרות נבדלות בקבוע כפלי של חצי, כך שאין זה משנה מהותית.

#### סימון
משום שהרוחב הגאוסי לרוב משמש בניתוח התנהגות אסימפטוטית (בממד), נשתמש בסימון   f \lesssim g לציין שקיים קבוע אוניברסלי C עבורו f \leq C g. כמו-כן, נסמן f \asymp g אם"ם f \lesssim g \lesssim f, דהיינו, קיים קבוע (אוניברסלי) C כך שמתקיים \frac{1}{C} f \leq g \leq C f.

לדוגמה, לעיל ראינו כי w(K) = c_n w_s(K), כאשר c_n \asymp \sqrt n, כלומר, w \asymp \sqrt{n} w_s.

## תכונות מפתח

* הקבוצה K חסומה אם"ם רוחבה w(K) סופי.
* הרוחב של קבוצה לא ריקה הוא אי-שלילי ושווה לאפס אם"ם הקבוצה היא יחידון.
* מונוטוניות: אם K_1 \subseteq K_2 אז w(K_1) \leq w(K_2).
* נשמר תחת העתקות אוניטריות אפיניות: לכל x_0 \in\mathbb{R^n} ולכל העתקה ליניארית אורתוגונלית U מתקיים w(UK+x_0) = w(K).
* באופן כללי, עבור העתקה ליניארית  A:\mathbb{R}^{n} \to \mathbb{R}^{m} מתקיים w(AK)\leq \|A\|w(K) כאשר \|A\| היא הנורמה של A.
* נשמר תחת קמור: w(\text{cnvx}(K)) = w(K).

* מכבד סכומי מינקובסקי : לכל \mathbb{R}^{n} \supseteq K, H ולכל \mathbb{R} \ni \alpha מתקיים w(K + \alpha H) = w(K)+|\alpha|w(L).
* עבור קבוצות קמורות, הרוחב הגאוסי הוא פונקציה מודולרית: עבור C_1, C_2 קמורות לא-ריקות שאיחודן קמור אף-הוא, מתקיים w(C_1 \cup C_2) = w(C_1) + w(C_2) - 
w(C_1 \cap C_2).  במילים אחרות, ההעתקה w \colon \mathcal{K}_n\to\mathbb{R} היא הערכה על ,\mathcal{K}_{n}  מרחב הקבוצות הקמורות הקומפקטיות והלא-ריקות ב-\mathbb{R}^{n}.
* ההעתקה w \colon \mathcal{C}_n\to\mathbb{R}, השולחת קבוצה קומפקטית לא-ריקה לרוחב שלה, היא העתקה ליפשיצית (כאשר \mathcal{C}_n, מרחב הקבוצות הקומפקטיות הלא-ריקות ב-\mathbb{R}^{n}, מצויד במטריקת האוסדורף).
* הרוחב גדל כמו הקוטר בפקטור שהוא לכל היותר שורש המימד: \frac{1}{\sqrt{2\pi}}\text{diam}(K) \leq w(K)\leq \frac{\sqrt{n}}{2} \text{diam}(K), כאשר \text{diam}(K) הוא קוטרה של הקבוצה.

### קשר למספרי כיסוי
אי-שוויון דאדלי (Dudley) לתהליכים גאוסיאנים ואי-שוויון סודקוב (Sudakov) מקשרים בין רוחב הקבוצה למספרי הכיסוי שלה:

**משפט (אי-שוויון דאדלי לקבוצות ב-<math>\mathbb{R}^{n}</math>).** לכל \mathbb{R}^{n}\supseteq K מתקיים w(K) \lesssim \int_{0}^{\infty}  \sqrt{\log\mathcal{N}(K,\varepsilon)} d\varepsilon.

למעשה, נוכל לחזק את האי-שוויון עבור קבוצות חסומות ולקחת באגף ימין את האינטגרל בקטע סגור [a,b] במקום בקרן [0,\infty), עבור a= \frac{cw(K)}{\sqrt n}, b = \text{diam}(K).

**משפט (אי שוויון סודקוב עבור הרוחב הגאוסי).** תהא \mathbb{R}^{n} \supseteq K ונגדיר .s(K) = \sup_{\varepsilon\geq0} \varepsilon
\sqrt{\log \mathcal{N}(K,\varepsilon)}מתקיים s(K) \lesssim w(K) \lesssim \log(n) s(K).

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

משפט האדוויגר (Hadwiger) בגאומטריה קמורה קושר בין הרוחב הספרי (ולפיכך גם הרוחב הגאוסי) ובין פונקציונאל גאומטרי אחר -- הנפח האינטרינזי הראשון -- המוגדר על ,\mathcal{K}_{n}  מרחב הקבוצות הקמורות הקומפקטיות והלא-ריקות ב-\mathbb{R}^{n}. במדויק,  ניתן להגדיר משפחת פונקציונלים V_{k} \colon \mathcal{K}_{n} \to\mathbb{R} (עבור 0 \leq k \leq n-1) אשר נקראים הפונקציונלים הבסיסיים או הנפחים האינטרינזיים (לא נגדירם כאן). 

**משפט. לכל <math>\mathcal{K}_n \ni K</math> מתקיים <math>w_s(K) = \frac{\text{vol}(B_{2}^{n-1})  }{n \text{vol}(S^{n-1}) } V_1 (K)</math>.

במימד 3,  <math>V_1</math> איננו אלא [[עקמומיות ממוצעת|העקמומיות הממוצעת]], ובמקרה זה המשפט מראה שהרוחב (הספרי/ הגאוסי) והעקמומיות הממוצעת חד הם (ע"כ קבוע).

===חישוב מקורב יעיל===
בעוד שהאמור לעיל מאפשר להעריך במידת-מה את הרוחב הגאוסי של קבוצה נתונה (בעזרת מספרי כיסוי, או בעזרת ידע על העקמומיות וכיוצא בזה), האומדנים הללו משמשים בעיקר ביישומים תאורטיים של הרוחב הגאוסי.

חישוב מקורב יעיל של הרוחב הגאוסי של קבוצה נתונה הוא פשוט, הודות לריכוז המידה הגאוסיאנית וכן בשל העובדה כי הוא נשמר תחת לקיחת קמור. דהיינו, בשל ריכוז המידה הגאוסיאנית, בהסתברות גבוהה, ה[[משתנה מקרי|משתנה המקרי]] <math>W_K = \sup_{x\in K} \langle x, g \ \rangle</math>  (כאשר <math>g \sim N(0,I_{n})</math>) קרוב מאוד ל[[תוחלת|תוחלתו]], שאיננה אלא <math>w(K)</math>, ולפיכך אומדן טוב של הרוחב הגאוסי מתקבל על-ידי דגימה (אף בודדת) של <math>W_K</math>. יתרה מזאת, בהינתן <math>g</math>, מציאת <math>W_K</math> היא בעיית [[אופטימיזציה קמורה]], שכן בפתרונה נוכל להניח בה"כ ש-<math>K</math> קמורה (על-ידי מעבר לקמור, שאינו משנה את הרוחב הגאוסי), ולכן ניתן לפתור אותה באופן יעיל.

==דוגמאות==
====קבוצה סופית====
ראשית, מובן שהרוחב של הקבוצה הריקה הוא <math>-\infty</math> ורוחבה של נקודה בודדת הוא <math>0</math> (התוחלת של משתנה נורמלי סטנדרטי).

עבור [[קבוצה סופית]] לא ריקה <math>K</math> כלשהי, מתקיים <math>w(K) \lesssim \sqrt{\log |K| } \text{diam}(K)</math>.
====כדור וספירה אוקלידיים====
מובן שלספירה ולכדור אותו רוחב, וקל לראות ש- <math>w(B_{2}^{n})=w(S^{n-1}) = \sqrt n \pm C</math>  (וכמובן ש- <math>w_s(B_{2}^{n})=2</math>).

בפרט, משום שאליפסואיד הוא תמונה של הכדור תחת העתקה ליניארית, נקבל שלכל [[אליפסואיד]]  <math>E^n</math> מתקיים  <math>w(E^n) \asymp \sqrt n </math>.

====כדור ביחס לנורמת-p====
עבור  <math>p=1</math>  מתקיים <math>w(B_{1}^{n}) \asymp \sqrt{\log n}</math>.

עבור <math>1< p < \infty</math>, מתקיים <math> n^{1/q} \lesssim w(B_{p}^{n}) \lesssim \sqrt{q}  n^{1/q}</math>, כאשר <math>q</math> הוא המעריך הצמוד ל-<math>p</math>, כלומר, המספר המקיים <math>\frac{1}{p} + \frac{1}{q} = 1</math>.

====קובייה====
רוחבה של קוביית היחידה, שאיננה אלא הכדור ביחס לנורמת <math>\ell_\infty</math>, הוא <math>w(B_{\infty}^{n})=\sqrt{\frac{2}{\pi}}n</math>.

====קבוצה המוכלת בתת-מרחב ליניארי====
אם <math>K</math> קבוצה המוכלת בתת-מרחב ממימד <math>d</math>, אזי <math>w(K)\leq \sqrt{d} \cdot \text{diam}(K) </math>.

בפרט, אנו רואים שהרוחב טומן בחובו מידע על אודות המימד האלגברי של הקבוצה (כלומר, המימד המזערי של תת-מרחב המכיל את הקבוצה).

====קבוצה חסומה כללית====

כמסקנה ממשפט הנשלטות (ר' מטה), ניתן להראות שמתקיים <math>w(K) \asymp \inf 
\left\{  
\left.\sup_{k\geq 2} \|x_k - s\|\sqrt{\log k}\; \right| 
K \subseteq \overline{\text{cnvx}\left( \left\{ x_k \left| k\geq2 \right.\right\} \right)}
\right\}</math>.

==מושגים והגדרות קשורים==
ישנם מספר מושגים וגדלים נוספים הקשורים קשר הדוק לרוחב הגאוסי -- חלקם אף ממש שקולים לו מבחינה אסימפטוטית, וחלקם מוגדרים באמצעותו, ולהם חשיבות ומשמעות גאומטרית. נציג כאן גדלים משמעותיים אלה, ובשל הקשר ההדוק שלהם לרוחב הגאוסי, נתייחס גם אליהם בסקירה של יישומים ושימושים מרכזיים, להדגמת חשיבות והיקף ההשפעה שלו.

===סיבוכיות גאוסית===
**הסיבוכיות הגאוסית** <math>\gamma(K)</math> של קבוצה <math>\mathbb{R}^{n}\supseteq K</math> מוגדרת על-ידי <math>\gamma(K)= \mathbb{E} \sup_{x\in K} \left|\langle x, g \rangle\right|</math> כאשר <math>g \sim N(0,I_n)</math>. כלומר, ההבדל היחיד מהגדרת הרוחב הגאוסי הוא לקיחת הערך המוחלט בסופרימום, וממילא מתקיים <math>w(K)\leq\gamma(K)</math> (ושוויון אם <math>K</math> סימטרית ביחס לראשית).

אמנם, הגדרה זו טבעית, אך בניגוד לרוחב הגאוסי, הסיבוכיות הגאוסית אינה נשמרת תחת הזזות, ולכן, מבחינה גאומטרית, הנה פחות טבעית במובן מסוים (בראייה של [[פליקס קליין]], המתייחסת לגאומטריה כחקר [[שמורה (מתמטיקה)| שמורותיהן]] של ה[[איזומטריה|איזומטריות]]).

מאידך, לכל <math>x_0\in K</math> מתקיים <math>\gamma(K)\leq 2\left(w(K)+||x_0||_2 \right)</math>, ולכן אינה שונה מהותית מהרוחב הגאוסי.

===מימד סטטיסטי (נורמת <math>L^2</math> של <math>h_K</math>)===
בדומה, נוכל להגדיר לכל  <math>\mathbb{R}^{n}\supseteq K</math> את הגודל  <math>h(K)= 
\left(\mathbb{E} \sup_{x\in K} \langle x, g \rangle ^2 \right)^{\frac{1}{2}} =
\|h_K\|_{L^2(\gamma_n)}</math>, כאשר <math>g \sim N(0,I_n)</math> ו- <math>\gamma_n</math> היא המידה הגאוסית על <math>.\mathbb{R}^n</math>

מתקיים  <math>w(K-K)\leq h(K-K) \leq w(K-K)+C^\prime \text{diam}(K)\leq Cw(K-K)</math>, ובפרט  <math>w(T) \asymp h(T-T)</math>.

בתחום שחזור האותות <math>h(K)</math> נקרא **המימד הסטטיסטי** של  <math>K</math>.

===רוחב גאוסי ממוקם===
עבור קבוצה <math>K</math> ב-<math>\mathbb{R}^{n}</math>, נוכל להביט לכל <math>s>0</math> על הרוחב הגאוסי של חיתוכה עם הכדור ברדיוס <math>s</math>:  <math>w_{\text{loc}}(K;s) = w \left(  K \cap sB_2^n \right)</math>. גודל זה נקרא ה**רוחב הגאוסי הממוקם (localized)** עם פרמטר <math>s</math>.

ניתן לחשוב על גודל זה כעל גרסה מקומית של הרוחב הגאוסי של הקבוצה (שהוא סופי לכל קבוצה, גם אם אינה חסומה אפריורי), אשר מחד ניתן לשחזר ממנה את הרוחב הגאוסי על-ידי לקיחת הגבול <math>s\to\infty</math>, ומאידך מאפשר בחינת התנהגות מקומית עבור ערכי <math>s</math> קטנים. גרסאות "ממוקמות" של מידות סיבוכיות הן כלי חשוב ונפוץ המאפשר קבלת חסמים אופטימליים בבעיות [[אמידה]] לא-פרמטריות, ולפיכך מושג  ה"מיקום" של מידות כאלה הוא בעל תפקיד חשוב בחקר תהליכים אמפיריים.

===מימד יציב/אפקטיבי===
בעזרת הרוחב הגאוסי, או, לחלופין, גרסת-<math>L^2</math> שלו, ניתן להגדיר מושג של מימד גאומטרי לקבוצה, אשר מחד מתכתב עם מימדה האלגברי, אך מאידך בעל תכונות רצויות ויציבות.
לדוגמה, בעוד שהמימד האלגברי של קבוצה רגיש להפרעה קלה (רעש קטן במיקומי נקודות הנמצאות על מישור עשוי לגרום להן שלא להיות מוכלות באף מישור), המימד האמור יציב ולא משתנה באופן זה.

**המימד היציב (אפקטיבי)''' של קבוצה \mathbb{R}^{n} \supseteq K מוגדר על-ידי d(K) = \frac{h(K-K)^2}{\text{diam}(K)^2} \asymp \frac{w(K-K)^2}{\text{diam}(K)^2}.

קל לראות שמתקיים d(K)\leq\dim(K), וכן, למשל, שמתקיים שוויון אם K  מכילה כדור (נובע ממונוטוניות ומכך שבבירור המימד האפקטיבי של כדור הוא מלא). מאידך, עבור קבוצה סופית, אנו יודעים שמתקיים d(K)\lesssim \log|K| (מה שגם מראה יציבות מסוימת כאמור לעיל). 

### סיבוכיות ראדמאכר

מושג קשור ודומה בהגדרתו לרוחב והסיבוכיות הגאוסית הוא המושג של סיבוכיות ראדמאכר של קבוצה, המוגדרת על-ידי ,R(K) = \mathbb{E}\sup_{x\in K} \langle x, \sigma\rangle כאשר \sigma  הוא וקטור שרכיביו הם משתני ראדמאכר בלתי-תלויים.

הגדרה זו הנה פחות גאומטרית באופיה, אך בעלת פירוש הסתברותי וסטטיסטי, ועולה באופן טבעי בבעיות סיווג ואנטרופיה. הרוחב הגאוסי וסיבוכיות ראדמאכר שקולים עד כדי גורם לוגריתמי בממד, דהיינו, R(K) \lesssim w(K) \lesssim \sqrt{\log(n)} R(K). עובדה זו בפני עצמה מרמזת על יישומים אפשריים של הרוחב הגאוסי בבעיות סיווג ולמידה.

למעשה, ישנה תוצאה עמוקה, אשר שוערה על-ידי מישל טלגרנד והוכחה (לאחר כ-25 שנים) על-ידי בדנורז ולטלה, המראה שסיבוכיות ראדמאכר עשויה להיות קטנה מאחת משתי סיבות: או שהרוחב הגאוסי קטן, או שהקוטר-\ell_1 של הקבוצה קטן: אם R(K)\leq r אזי K\subseteq K_g + K_1 כאשר w(K_g)\leq cr וכן \sup_{x\in K_1}\|x\|_{\ell_1} \leq cr.

## חשיבות ושימושים
### גשר בין גאומטריה בממדים גבוהים והסתברות
מושג הפונקציה התומכת של קבוצה קמורה הוא מושג מרכזי בגאומטריה קמורה, וכיוצא בזאת גם הרוחב הספרי מופיע באופן טבעי ומהווה גודל בסיסי. על-כן, אין זה מפתיע שבאנליזה גאומטרית אסימפטוטית (הנקראת לעיתים גם תורה גאומטרית מקומית של מרחבי בנך) הרוחב הספרי, אשר בהקשר זה נקרא לעיתים גם קבוע M^*  של הקבוצה, משחק תפקיד משמעותי בהבנת הגאומטריה שלה ומהווה נדבך מרכזי בתוצאות מרכזיות בתחום, כמו משפט דבורצקי-מילמן.

מן העבר השני, פותחה תורה ענפה של חקר תהליכים מקריים ואנליזה של התנהגותם, ובין היתר, התורה החזקה (שהתחיל עוד על-ידי קולמוגורוב ופותחה בעיקר על-ידי טלגרנד) של שיטת "שרשור גנרי" להשגת חסמים על גדלים שלתהליכים מקריים. בפרט, להבנת תהליכים מקריים, ובמיוחד תהליכים גאוסיים, קשר מיידי ועמוק עם גאומטריה אסימפטוטית, שכן כל תהליך מגדיר מרחק על קבוצת המצבים שלו, ועבור התהליך הגאוסי הקנוני, מרחק זה הוא המרחק האוקלידי.

באופן זה, הרוחב הגאוסי נמצא בגשר והחיתוך של שני תחומים ומספק נקודת מבט (וכלים) נוספת על הגאומטריה של מרחבים סוף-ממדיים והסברים חלופיים ונוספים על תופעות מפתח, כמו-גם מעניק יכולת לכמת אופי של התנהגויות מסוימות, כפי שנדגים מטה. להמחשת קשר עמוק זה, נציין כבר כעת כי השימוש הראשון ברוחב הגאוסי נעשה על-ידי גורדון במשפט "הבריחה מהרשת" המפורסם והמרכזי במאמרו מ-1988, בו עוד טרם ניתן לרוחב הגאוסי שמו.

#### כימות ופירוש תופעות מרכזיות בממדים גבוהים
בגאומטריה של מרחבים וקטוריים במימד (סופי) גבוה אנו נתקלים בתופעות מפתיעות רבות המתארות את התהגותו הלא-אינטואיבית של הנפח בממדים גבוהים, כדוגמת "הצטברותו" בפינות (אחת מפניה של "קללת המימד" המפורסמת). הרוחב של הקבוצה מתברר כגורם יסודי בתופעות אלו, אפשר מאפשר לכמת אותן ולהבינן טוב יותר.

כך, למשל, עבור קבוצה חסומה \mathbb{R}^{n}\supset K, אם נטילה על תת-מרחב אקראי ממימד m  (בהתפלגות אחידה על הגרסמניאן), אז בהסתברות גבוהה מאוד נקבל שהקוטר של ההטלה P_m(K) קטן מ-\max \left( w_s(K), \sqrt{\frac{m}{n}} \text{diam}(K)  \right). מחד, הלמה של ג'ונסון ולינדנשטראוס גורסת שאם K סופית, אז ההטלה היא רק כיול, בפקטור של \sqrt{\frac{m}{n}}, כאשר  m גדול דיו:  m \gtrsim \log |K|. כלומר, עבור קבוצות קטנות מספיק, הגודל השולט הוא הקוטר. מאידך, עבור קבוצה גדולה דיה, מובן ש- m כזה אינו קיים (דהיינו, כאשר  n \lesssim \log |K|). ניתן להראות ש"מעבר הפאזה" בהתנהגותו של הקוטר של  P_m(K) מתרחש בדיוק במימד היציב של  K. כלומר, אם  m \leq d(K) אז  \text{diam}(P_m(K)) \lesssim w_s(K) ואחרת \text{diam}(P_m(K)) \lesssim \sqrt{\frac{m}{n}}\text{diam}(K).

המימד האפקטיבי מופיע גם בתיאור שינוי ההתנהגות עם חיתוך עם תת-מרחב (אפיני) אקראי, שנזהה כגרעין (מוזז) של מטריצה אקראית: תהי A מטריצה מגודל m \times n, ששורותיה הן וקטורים מקריים בלתי-תלויים, איזוטרופיים ותת-גאוסיים עם נורמת-<math>\psi_2</math> חסומה מלעיל על ידי B. בהינתן ,\varepsilon>0 מתקיים ש-\mathbb{E}\text{diam} \left(K\cap \ker A \right) \leq \varepsilon \text{diam}(K)  כל עוד ש-m \gtrsim \frac{B^4}{\varepsilon^2}d(K). כלומר, הקוטר מתכווץ כל עוד הממד המשלים של \ker A  גדול דיו מהמימד היציב של K. תוצאה זו מתחברת למשפט דבורצקי וחסם ה-M^*, אשר מסביר מדוע הקוטר חדל להתכווץ במימד קטן מהמימד הקריטי -- שכן במקרה זה ההטלה היא בקירוב כדור בקוטר w_s(K). שוב, אנו רואים את יסודיותו של הרוחב בהסבר תופעות מרכזיות בתחום.

#### גאומטריה של תהליכים מקריים
בהינתן תהליך מקרי (X_t)_{t\in T}   מעל הקבוצה \mathbb{R}^{n} \supseteq T, ישנו קשר בין הגאומטריה של הקבוצה T לבין גודלו של התהליך, \mathbb{E} \sup_{t\in T} X_t (גודל זה איננו אלא הרוחב הגאוסי, כאשר X_t הוא התהליך הגאוסי הקנוני): מישל טלגרנד הראה שאם הצעדים של תהליך עם תוחלת אפס הם תת-גאוסיים, אז \mathbb{E} \sup_{t\in T} X_t נשלט על-ידי מאפיין גאומטרי של T, אשר מסומן \gamma_2(T), והוא אחד מסדרת פונקציונליים שהגדיר טלגרנד: \mathbb{E} \sup_{t\in T} X_t \asymp \gamma_2(T,d_X), כאשר d_X המטריקה המוגדרת על-ידי התהליך. כמסקנה חשובה מכך ניתן להסיק את משפט ההשוואה של טלגרנד, אשר בגרסתו הגאומטרית מלמד ש \mathbb{E} \sup_{t\in T} X_t \lesssim B_X w(T), כאשר B_X הוא חסם אחיד על  נורמת-<math>\psi_2</math> של צעדי התהליך. למעשה, ניתן לחסום את כל המומנטים על ידי \left( \mathbb{E} \sup_{t\in T} |X_t|^p \right)^{\frac{1}{p}} \lesssim \sqrt{p} B_X  \gamma(T).

בתורו, משפט ההשוואה הוא בעל השלכות רבות בקשרים בין אקראיות וגאומטריה. לדוגמה, שבט (Chevet) הראה כי עבור מטריצה גאוסית, התבנית הביליניארית המוגדרת על-ידה, מעל תתי-קבוצות T,S, חסומה בתוחלת על-ידי  .\text{radius}(T)w(S) + \text{radius}(S)w(T)

### יישומים בלמידה וסטטיסטיקה
לרוחב הגאוסי ישנם שימושים רבים באמידה, למידה, וסטטיסטיקה, זאת, בשל העובדה שזהו גודל טבעי בעזרתו ניתן לחסום את שגיאת האמידה כאשר הפרמטר הנאמד שייך לקבוצה נתונה, ומכאן, למשל, אף ניתן להסיק כמה דגימות נדרשות על מנת להבטיח תוצאות טובות ואף ללא כל שגיאה במקרים מסוימים. 

תוצאות כאלה התקבלו עבור אותות דלילים (כלומר, שמספר רכיביהם השונים מאפס חסום), המראות כי אף ניתן לשחזר במדויק וללא כל שגיאה את האות כל עוד מספר הדגימות גדול דיו -- ובמובן מאוד מדויק, אשר ניתן לתאר בעזרת רוחב הקבוצה אליה משתייך האות (ומתרגם נומינלית לביטוי מדויק וברור).

בנוסף, עבור משפחה רחבה של בעיות, הכוללת את המודל הליניארי המוכלל, ישנה דרך יעילה לאמוד, בעזרת הרוחב הגאוסי, את האות בשני שלבים -- אמידה ליניארית ולאחריה הטלה על הקבוצה K אליה משתייך האות, ואף נמצאו תנאים להבטחה של אופטימליות האומד, ע"כ קבוע כפלי. בפרט, תוצאה זו שימושית בתחום של חישה דחוסה (compressed sensing) (), כולל בגרפים של רשתות נוירונים.

השימושים של הרוחב הגאוסי בלמידה, סטטיסטיקה, הסתברות ותורת המטריצות האקראיות רחבים ורבים, וזהו רק קצה הקרחון. מאמר הסקירה של רומן ורשינין וספרו הם מקורות טובים להפניות ולחשיפה לנושא. 

### אופטימיזציה ואלגוריתמי קירוב
דוגמה נוספת לשימוש ברוחב הגאוסי מגיעה מהתחום של אופטימיזציה, שכן הרוחב הגאוסי מעניק כלי כמותי נוסף לתיאור הגאומטריה של הבעיה. נתאר בקצרה וללא פרטים דוגמה כזו, רק כדי להדגים את רוחב היריעה של השימושים ברוחב הגאוסי, ושאלו אינם מוגבלים לסטטיסטיקה והסתברות וכיוצא בזה. 

אופטימיזציה פולינומית היא בעיה רחבה אשר בה מחפשים את המקסימום (או המינימום) של פולינום ממעלה נתונה (בכמה משתנים) מעל תחום אלגברי-למחצה המתואר על-ידי מספר סופי של שוויונות ואי-שוויונות פולינומיים (למשל, ספירה או כדור (בנורמת-p כלשהי), העל-קוביה, הסימפלקס, פוליגון וכדומה). בעיות רבות ומשמעותיות באופטימיזציה קומבינטורית, כגון בעיית החתך המרבי (MaxCut), ניתנות לתיאור במסגרת זו.

בעוד שהבעיה של מירוב פולינום הומוגני (שנקבע לפיכך על-ידי ערכו על הספירה) ניתנת לפתרון יעיל כאשר הוא ריבועי (ואז הבעיה שקולה למציאת הערך העצמי המרבי של המטריצה המסומכת לה), אם מעלתו של הפולינום גדולה מ-3, זו בעיה NP-קשה, השקולה לבעיות ספקטרליות של טנזורים (לדוגמה, בעיית ניתוח רכיבים עיקריים (PCA)).

ברניקוב הגדיר משפחת פולינומים, להם קרא "ממוקדים", שבאופן לא-פורמלי הם פולינומים שמרוכזים סביב נקודה בודדת על הספירה, והראה שניתן למצוא להם (1+\varepsilon)^\deg-קירוב על ידי בחירה אקראית של תת-מרחב ליניארי ממימד נמוך, ופתרון בעיית האופטימיזציה שם (כלומר, על חיתוכו עם הספירה).

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

באותה רוח, סונדרסון, תלמיד נוסף של פרילו, תיאר וכימת בעזרת הרוחב הגאוסי את הפער של אופטימליות קירוב לבעיות אופטימיזציה מעל מטריצות מכווצות על-ידי מטריצות חיוביות-לחלוטין, ובכך הראה שהרוחב הגאוסי הוא המכשלה בפני סכימת קירוב מתאימה, מה שמדגים עוד את מרכזיותו של הרוחב הגאוסי.

## ראו גם
* תהליך גאוסי 
* סיבוכיות ראדמאכר
* משפט דבורצקי
* הלמה של ג'ונסון ולינדנשטראוס
* קללת הממד 

## לקריאה נוספת
#### אנליזה גאומטרית ורקע

* 
* 

* 
* 


#### שימושים ויישומים


* 

* 
* 

* 

*


## הערות שוליים

קטגוריה:מרחבים נורמיים