אי-שוויון הנסון-רייט

אי-שוויון הנסון–רייט (באנגלית: Hanson–Wright inequality) הוא אי שוויון הסתברותי בתחום ריכוז המידה. אי השוויון נותן חסם לסיכוי שתצפית ריבועית מהצורה <math>X^\mathsf{T} A X</math> תחרוג מהתוחלת שלה עבור וקטור אקראי <math>X</math> אשר מורכב ממשתנים תת גאוסיים בלתי תלויים בעלי תוחלת אפס. גרסה ראשונה של המשפט הוכחה על ידי הנסון ורייט בשנת 1971.

המשפט נחשב לאבן דרך בהבנה של התנהגות של ביטויים מהצורה <math>X^T A X</math>, כאשר <math>X</math> הוא וקטור מקרי ו־<math>A</math> היא מטריצה קבועה.

ניסוח המשפט

עבור <math>n </math> מספר חיובי ו-<math>X_1, ..., X_n</math> משתנים בלתי תלויים שמקיימים <math>E[X_i] = 0</math>. נגדיר את הווקטור האקראי <math>X = (X_1, \dots, X_n)</math>. עבור כל מטריצה A מגודל <math>n\times n</math> נקבל: <math display="block">P(|X^T AX - E[X^TAX]| > t ) \leq \max\left( 2 e^{-\frac{ct^2}{K^4\|A\|_F^2}}, 2 e^{-\frac{ct}{K^2\|A\|}} \right) = 2 \exp \left[-c \min \left(\frac{t^2}{K^4\|A\|_F^2}, \frac{t}{K^2\|A\|}\right)\right] </math> כש<math>K = \max_i \|X_i\|_{\psi_2}</math> הוא המקסימום של הנורמה התת-גאוסית של המשתנים המקריים ו- <math>\|A\|_F = \sqrt{\sum_{ij} A_{ij}^2}</math> היא נורמת פורביניוס ו<math>\|A\| = \max_{\|x\|_2=1} \|Ax\|_2</math> היא הנורמה של אופרטור של המטריצה, עבור קבוע c.

עיקרי ההוכחה

ההוכחה לגרסה המלאה של המשפט שהוצגה על ידי מארק רודלסון ורומן ורשינין

תחילה נניח כי K=1. מספיק להראות עבור החלק החיובי בערך המוחלט ובאופן דומה לכיוון השני: <math>p:=\mathbb{P}\left( X^T A X - \mathbb{E}[X^T A X] \geq t \right)</math> בעזרת חישוב ההגדרות נוכל להגיע לשוויון הבא: <math> X^T A X - \mathbb{E}[X^T A X] = \sum_i a_{ii} (X_i^2 - \mathbb{E}[X_i^2]) + \sum_{i \ne j} a_{ij} X_i X_j </math> וכך נוכל לחסום את ההסתברות p כך: <math> p \leq \mathbb{P} \left( \sum_i a_{ii} (X_i^2 - \mathbb{E}[X_i^2]) \geq \frac{t}{2} \right) + \mathbb{P} \left( \sum_{i \ne j} a_{ij} X_i X_j \geq \frac{t}{2} \right) </math>

מכאן נוכל לחסום כל מחובר בנפרד ולהגיע לחסם מחובר ראשון: המשתנים <math>X_i^2 - \mathbb{E}[X_i^2]</math> הם בלתי תלויים, בעלי תוחלת אפס ותת-אקספוננציאליים. בנוסף, מתקיים:

<math> \|X_i^2 - \mathbb{E}[X_i^2]\|_{\psi_1} \lesssim \|X_i^2\|_{\psi_1} \lesssim \|X_i\|_{\psi_2}^2 \lesssim 1 </math> מכאן אפשר להשתמש באי שוויון ברנשטיין ולקבל את החסם: <math> \exp\left( - c \cdot \min\left( \frac{t^2}{\sum_i a_{ii}^2}, \frac{t}{\max_i |a_{ii}|} \right) \right) \leq \exp\left( - c \cdot \min\left( \frac{t^2}{\|A\|_F^2}, \frac{t}{\|A\|} \right) \right) </math>

בחלק השני נוכל להשתמש באי-שוויון מרקוב עבור <math>\lambda > 0</math> <math> \mathbb{P}(\sum_{i \ne j} a_{ij} X_i X_j \geq \frac{t}{2} \geq t/2) = \mathbb{P}(\lambda \sum_{i \ne j} a_{ij} X_i X_j \geq \frac{t}{2} \geq \lambda t/2) \leq \exp(-\lambda t/2) \cdot \mathbb{E}[\exp(\lambda \sum_{i \ne j} a_{ij} X_i X_j \geq \frac{t}{2})] </math> מכאן נשתמש ב3 למות נוספות:

למה 1-(טכניקת הפרדה (decoupling))

עבור כל מטריצה ריבועית <math>A = (a_{ij})</math>, מתקיים: <math> \mathbb{E} \left[ \left( \sum_{i \ne j} a_{ij} X_i X_j \right)^2 \right] \leq \mathbb{E} \left[ \left( 4 \sum_{i,j} a_{ij} X_i X_j' \right)^2 \right] </math>

כאשר <math>X = (X_1, \dots, X_n)</math> ו-<math>X' = (X_1', \dots, X_n')</math> הם וקטורים של משתנים מקריים בלתי תלויים, ו־<math>X'</math> הוא עותק בלתי תלוי של <math>X</math>.

למה 2- נניח כי <math>X, X'</math> הם וקטורים מקריים בלתי תלויים בעלי תוחלת אפס ב <math>\mathbb{R}^n</math>, כך שלכל אחד מהם יש תכונת תת-גאוסיות עם חסם <math>K</math>:

<math>\|X\|_{\psi_2} \leq K, \quad \|X'\|_{\psi_2} \leq K</math>

נניח גם כי <math>g, g'</math> הם וקטורים מקריים בלתי תלויים שמתפלגים נורמלית:

<math>g, g' \sim \mathcal{N}(0, I_n)</math>

לכל מטריצה <math>A \in \mathbb{R}^{n \times n}</math> ולכל <math>\lambda \in \mathbb{R}</math> מתקיים:

<math> \mathbb{E} \left[ \exp\left( \lambda X^T A X' \right) \right] \leq \mathbb{E} \left[ \exp\left( C K^2 \lambda\, g^T A g' \right) \right] </math>

למה 3 - פונקציה יוצרת מומנטים של כאוס גאוסי

יהיו <math>X, X'</math> וקטורים מקריים בלתי תלויים המתפלגים נורמלית: <math>X, X' \sim \mathcal{N}(0, I_n)</math>. יהי <math>A = (a_{ij})</math> מטריצה ממשית בגודל <math>n \times n</math>.

אז, עבור כל <math>\lambda</math> המקיים <math>|\lambda| \leq \frac{c}{\|A\|}</math>, מתקיים:

<math> \mathbb{E} \left[ \exp\left( \lambda X^T A X' \right) \right] \leq \exp\left( C \lambda^2 \|A\|_F^2 \right) </math>

בעזרת שימוש בלמות לפי הסדר המוצג כאן נוכל ליצור את החסם הבא: <math> \mathbb{E} \left[ \exp\left( \lambda \sum_{i \ne j} a_{ij} X_i X_j \right) \right] \leq \mathbb{E} \left[ \exp(4 \lambda X^T A X') \right] \leq \mathbb{E} \left[ \exp(C_1 \lambda\, g^T A g') \right] \leq \exp\left( C \lambda^2 \|A\|_F^2 \right) </math>

נבחר את <math>\lambda</math> שתקיים את התנאי ללמה 3. <math>|\lambda| \leq \frac{c}{\|A\|}</math> ונוכל לקבל

<math> \mathbb{P} \left( \sum_{i \ne j} a_{ij} X_i X_j \geq \frac{t}{2} \right) \leq \exp\left( - c \cdot \min\left( \frac{t^2}{\|A\|_F^2}, \frac{t}{\|A\|} \right) \right) </math>

היסטוריה

האי-שוויון נקרא על שם ד.הנסון (D. L. Hanson) ופארול רייט (Farroll T. Wright), שפרסמו בשנת 1971 את המאמר:

A bound on tail probabilities for quadratic forms in independent random variables Annals of Mathematical Statistics, Vol. 42, No. 3 (1971), pp. 1079–1083.

במאמר זה, הם פיתחו לראשונה חסם אקספוננציאלי לזנב של צירוף ריבועי של משתנים בלתי תלויים עם תכונות ריכוז (כמו תוחלת אפס ושונוּת סופית).

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

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

גרסאות נוספות והרחבות

אי שוויון הנסן-רייט בממדים גבוהים

אי-שוויון הנסון–רייט ניתן להרחבה גם למקרה של וקטורים אקראיים תת-גאוסיים במרחב ממימד גבוה. יהי <math>X_1, \dots, X_n</math> סדרה של וקטורים מקריים בלתי תלויים ב־<math>\mathbb{R}^d</math>, עם תוחלת אפס, כך שמתקיים:

<math> \|X_i\|_{\psi_2} \leq K </math>

נסמן <math>A = (a_{ij})</math> מטריצה ממשית בגודל <math>n \times n</math>. אזי, לכל <math>t \geq 0</math> מתקיים:

<math> \Pr\left( \sum_{i \ne j} a_{ij} \langle X_i, X_j \rangle \geq t \right) \leq 2 \exp\left( - c \cdot \min\left( \frac{t^2}{K^4 d \|A\|_F^2}, \frac{t}{K^2 \|A\|} \right) \right) </math>

כאשר <math>\|A\|_F</math> היא נורמת פרוביניוס ו <math>\|A\|</math> היא הנורמה של האופרטור

מקרה פרטי של אי-שוויון הנסון–רייט עבור נורמה ריבועית

יהי <math>A \in \mathbb{R}^{m \times n}</math> מטריצה קבועה, ויהי <math>X = (X_1, \dots, X_n)</math> וקטור מקרי שמרכיביו הם משתנים מקריים בלתי תלויים, כך שלכל <math>i</math> מתקיים: <math>\mathbb{E}[X_i] = 0</math> , <math>\mathbb{E}[X_i^2] = 1</math>, <math>\|X_i\|_{\psi_2} \leq K</math>

אזי לכל <math>t \geq 0</math> מתקיים:

<math> \mathbb{P} \left( \left| \|AX\|_2^2 - \|A\|_{HS}^2 \right| > t \right) \leq 2 \exp\left( - \frac{c t^2}{K^4 \|A\|^2} \right) </math>

כאשר:

• <math>\|AX\|_2</math> היא נורמת <math>\ell_2</math>
• <math>\|A\|_{HS} = \left( \sum_{i,j} a_{ij}^2 \right)^{1/2}</math> היא נורמת הילברט–שמידט

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

דוגמאות לשימושים

ריכוז מידה עבור וקטורים מקריים אנאיזוטרופיים

<math>B</math> היא מטריצה בגודל <math>m \times n</math>, ויהי <math>X = (X_1, \dots, X_n) \in \mathbb{R}^n</math> וקטור אקראי שערכיו בלתי תלויים, בעלי תוחלת אפס, שונות אחידה, ותת-גאוסיות עם קבוע <math>K</math>, כלומר <math>\|X_i\|_{\psi_2} \leq K</math> לכל <math>i</math>. מתקיים:

<math> \left\| \|BX\|_2 - \|B\|_F \right\|_{\psi_2} \leq C K^2 \|B\| </math>

מקרה פרטי חשוב של משפט זה מתקבל עבור מטריצת היחידה <math>B = I_n</math> במקרה זה, מתקבל:

<math> \left\| \|X\|_2 - \sqrt{n} \right\|_{\psi_2} \leq C K^2 </math>.

חישוב נורמה של מטריצות אקראיות

<math>B</math> היא מטריצה קבועה בגודל <math>m \times N</math>, ו־<math>G</math> היא מטריצה מקרית בגודל <math>N \times n</math> שאיבריה בלתי תלויים ומקיימים:

<math> \mathbb{E}[G_{ij}] = 0,\quad \mathbb{E}[G_{ij}^2] = 1,\quad \|G_{ij}\|_{\psi_2} \leq K </math>

אזי, עבור כל <math>s, t \geq 1</math>, מתקיים:

<math> \mathbb{P}\left( \|BG\| > C K^2 \left( s \|B\|_{HS} + t \sqrt{n} \|B\| \right) \right) \leq 2 \exp\left( -s^2 r - \frac{t^2}{n} \right) </math>

כאשר <math>r = \|B\|_{HS}^2 / \|B\|^2</math>.

חישוב מרחב בין וקטורים אקראיים לתת מרחב

יהי <math>E</math> תת-מרחב של <math>\mathbb{R}^n</math> ממימד <math>d</math>. נניח כי <math>X = (X_1, \dots, X_n)</math> הוא וקטור אקראי, שבו <math>X_i</math> הם משתנים מקריים בלתי תלויים, המקיימים את התנאים הבאים:

<math>\mathbb{E}[X_i] = 0</math>, <math>\mathbb{E}[X_i^2] = 1</math> ו- <math>\|X_i\|_{\psi_2} \leq K</math>

אז לכל <math>t \geq 0</math>, מתקיים:

<math> \Pr\left( \left| d(X, E) - \sqrt{n - d} \right| > t \right) \leq 2 \exp\left( -c \cdot \frac{t^2}{K^4} \right) </math>

כאשר <math>d(X, E)</math> הוא המרחק האוקלידי של <math>X</math> מהמרחב <math>E</math> ו <math>c</math> הוא קבוע.

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

רעיון: בעזרת מקרה פרטי של אי-שוויון הנסון–רייט עבור נורמה ריבועית עבור <math>A = P_{E^\perp}</math> ההטלה האורתוגונלית על <math>E</math> ולקבל <math> d(X, E) = \|P_{E^\perp} X\|_2 </math>, <math>\|P_{E^\perp}\|_{HS} = \sqrt{\dim(E^\perp)} = \sqrt{n - d}</math> , <math>\|P_{E^\perp}\| = 1</math>

ניתוח טרנספורמציות ליניאריות של רעש

במקרים רבים אנו עוסקים במקרים שמשתנה תת גאוסי (או גאוסי) עבור העתקה ליניארית. כמו במקרה של רעש <math>Z = AX</math>.

כאשר <math>X</math> הוא וקטור אקראי תת-גאוסי ומייצג את הרעש ו־<math>A</math> מטריצה ליניארית קבועה ו<math>Z</math> הוא האות הנצפה.

במקרים בהם <math>A</math> ו-<math>X</math> מתאימים לתנאי האי-שוויון, אפשר בעזרתו לחסום את ההסתברות שגודל הווקטור המתקבל מטרנספורמציה ליניארית של רעש יסטה באופן משמעותי מהתוחלת שלו. ניתן להראות כי:

<math> \mathbb{P}\left( \left| \|AX\|_2^2 - \mathbb{E}[\|AX\|_2^2] \right| > t \right) \leq 2 \exp\left( -c \cdot \min\left( \frac{t^2}{K^4 \|A\|_F^2}, \frac{t}{K^2 \|A\|^2} \right) \right) </math>

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

ראו גם

• אי-שוויונות ברנשטיין
• אי-שוויונות ריכוז
• התפלגות תת-גאוסית