אי-שוויון ברנשטיין למטריצות

בערך זה נעשה שימוש בסימנים מוסכמים מתחום המתמטיקה. להבהרת הסימנים ראו סימון מתמטי.

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

היסטוריה ופיתוח

אי-השוויון במתכונתו המודרנית הופיע לראשונה בעבודתם של רודולף אלסווד (Rudolf Ahlswede) ואנדריאס וינטר (Andreas Winter) משנת 2002. הם השתמשו בו בהקשר של תורת האינפורמציה הקוונטית, ספציפית לחקר שיעורי התכנסות חזקים (strong converse rates) בערוצים קוונטיים.

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

ניסוח פורמלי

יהיו $X_1,\dots ,X_n$ סדרה סופית של מטריצות אקראיות בלתי תלויות מממד $d\times d$, אשר כל אחת מהן היא הרמיטית. נניח כי כל המטריצות הן ממוקדות, כלומר $\mathbf{𝐄}[X_k]=0$ (מטריצת האפס) לכל $k=1,\dots ,n$.

נניח שקיים קבוע $R>0$ כך שהנורמה של כל מטריצה חסומה כמעט בוודאות: $\Vert X_k\Vert \le R$ לכל $k$ כאשר $\Vert \cdot \Vert$ היא הנורמה אופרטורית (הידועה גם כנורמה ספקטרלית), השווה לערך הסינגולרי הגדול ביותר של המטריצה (או הערך העצמי הגדול ביותר בערכו המוחלט, עבור מטריצות הרמיטיות).

נגדיר את "פרמטר השונות המטריציוני" (matrix variance parameter) של הסכום על ידי: ${\sigma }^2:=\Vert \sum _{k=1}^n\mathbf{𝐄}[X_k^2]\Vert$ כאן, $\mathbf{𝐄}[X_k^2]$ היא תוחלת המטריצה $X_k^2$. מכיוון שכל $X_k$ היא הרמיטית, $X_k^2$ היא מטריצה חיובית (positive semidefinite), וכך גם תוחלתה $\mathbf{𝐄}[X_k^2]$. לפיכך, הסכום $\sum _{k=1}^n\mathbf{𝐄}[X_k^2]$ הוא מטריצה חיובית, והנורמה האופרטורית שלו ${\sigma }^2$ היא פשוט הערך העצמי הגדול ביותר של מטריצת השונות המצטברת הזו.

אזי, לכל $t\ge 0$, מתקיים אי-שוויון ברנשטיין למטריצות: $\mathbf{𝐏}(\Vert \sum _{k=1}^n{X}_k\Vert \ge t)\le 2d\cdot \exp (-\frac{t^2}{2{\sigma }^2+(2/3)Rt})$

הערה: הקבוע $2/3$ במכנה האקספוננט עשוי להשתנות מעט בין גרסאות שונות של אי-השוויון בספרות, בהתאם לחסמים הספציפיים שבהם משתמשים בהוכחה.

הסבר ואינטואיציה

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

• הקבלה לאי-שוויון ברנשטיין הסקלרי: באי-השוויון הסקלרי, חסם הזנב תלוי בשונות הכוללת ובחסם העליון על גודל המשתנים הבודדים. באופן מקביל, אי-שוויון המטריצות תלוי בפרמטר השונות המטריציוני ${\sigma }^2$ (שמכמת את השונות המצטברת של המטריצות) ובחסם העליון $R$ על הנורמה של המטריצות הבודדות. אי-שוויון ברנשטיין למטריצות הוא הכללה של אי-שוויון ברנשטיין עבור משתנים מקריים סקלריים. כאשר ממד המטריצות הוא 1 (d=1), הנורמה האופרטורית מתכווצת לערך המוחלט, והאי-שוויון הופך לאי-שוויון ברנשטיין הסטנדרטי עבור סכום של משתנים מקריים חסומים .
• משמעות האיברים במכנה האקספוננט: המכנה $2{\sigma }^2+(2/3)Rt$ משלב שני משטרים:

1. מקרה תת-גאוסיאני (Sub-Gaussian regime): כאשר $t$ קטן יחסית (ובאופן גס, $t\lesssim {\sigma }^2/R$), האיבר הדומיננטי במכנה הוא $2{\sigma }^2$. החסם דומה להתנהגות זנב גאוסיאני, $\exp (-t^2/(2{\sigma }^2))$. התנהגות זו אופיינית לסטיות קטנות הנשלטות על ידי השונות המצטברת, ברוח משפט הגבול המרכזי.
2. מקרה תת-אקספוננציאלי (Sub-exponential regime): כאשר $t$ גדול ($t\gg {\sigma }^2/R$), האיבר הדומיננטי במכנה הוא $(2/3)Rt$. החסם דומה להתנהגות זנב פואסוני או תת-אקספוננציאלי, $\exp (-3t/(2R))$ (עד כדי פקטורים קבועים). התנהגות זו אופיינית לסטיות גדולות, הנשלטות על ידי הערכים הקיצוניים האפשריים של המטריצות (הנורמה המקסימלית $R$).

• תפקיד הממד $d$: הפקטור $2d$ המופיע לפני האקספוננט הוא ההבדל הבולט ביותר בהשוואה לאי-השוויון הסקלרי (שם המקדם הוא 2). הוא נובע מהמעבר למרחב מטריצות, ובאופן טכני, מהשימוש בעקבה (trace) של אקספוננט מטריציוני בהוכחה, והחסם $\mathrm{T}\mathrm{r}(A)\le d\Vert A\Vert$ עבור מטריצות חיוביות. ניתן לחשוב על פקטור זה כמחיר שמשלמים על חוסר הקומוטטיביות של כפל מטריצות ועל העובדה שהנורמה של המטריצה מושפעת מ-$d$ ערכים עצמיים פוטנציאליים. במקרים רבים, כאשר למטריצות יש מבנה נוסף (למשל, דרגה נמוכה), ניתן לשפר פקטור זה ולהחליפו ב"ממד אפקטיבי" הקטן מ-$d$.
• שימושיות: אי-השוויון יעיל במיוחד כאשר השונות המצטברת ${\sigma }^2$ קטנה משמעותית מהשונות שהייתה מתקבלת אם היינו משתמשים בחסם הגס $\Vert X_k\Vert \le R$ בלבד (למשל, כאשר ${\sigma }^2\ll n{R}^2$). במצבים אלו, הוא מספק חסמים הדוקים יותר מאשר אי-שוויון הופדינג למטריצות, שאינו מתחשב במבנה השונות.

הוכחה (סקיצה)

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

הוכחה

נסמן את הסכום $S=\sum _{k=1}^n{X}_k$. מטרתנו היא לחסום את $\mathbf{𝐏}(\Vert S\Vert \ge t)$. 1. פירוק הנורמה: מכיוון ש-$S$ היא מטריצה הרמיטית, הנורמה האופרטורית שלה היא הערך המוחלט של הערך העצמי הקיצוני ביותר: $\Vert S\Vert =\max (|{\lambda }_{\max }(S)|,|{\lambda }_{\min }(S)|)=\max ({\lambda }_{\max }(S),-{\lambda }_{\min }(S))$ כאשר ${\lambda }_{\max }(S)$ ו-${\lambda }_{\min }(S)$ הם הערכים העצמיים המקסימלי והמינימלי של $S$, בהתאמה. לכן, על ידי אי-שוויון האיחוד: $\mathbf{𝐏}(\Vert S\Vert \ge t)=\mathbf{𝐏}({\lambda }_{\max }(S)\ge t\text{ or }{\lambda }_{\min }(S)\le -t)\le \mathbf{𝐏}({\lambda }_{\max }(S)\ge t)+\mathbf{𝐏}({\lambda }_{\min }(S)\le -t)$ נשים לב ש-${\lambda }_{\min }(S)\le -t$ שקול ל-${\lambda }_{\max }(-S)\ge t$. מכיוון שהסכום $-S=\sum _{k=1}^n(-X_k)$ מורכב גם הוא ממטריצות הרמיטיות בלתי תלויות וממורכזות, עם אותו חסם נורמה $R$ ואותו פרמטר שונות ${\sigma }^2$, החסם על $\mathbf{𝐏}({\lambda }_{\min }(S)\le -t)$ זהה לחסם על $\mathbf{𝐏}({\lambda }_{\max }(S)\ge t)$. לכן, מספיק לחסום את $\mathbf{𝐏}({\lambda }_{\max }(S)\ge t)$ ולהכפיל את התוצאה ב-2. 2. שימוש בחסם צ'רנוף ובעקבה: עבור $\theta >0$ (פרמטר שייבחר בהמשך), נשתמש בחסם צ'רנוף: $\mathbf{𝐏}({\lambda }_{\max }(S)\ge t)=\mathbf{𝐏}(\exp (\theta {\lambda }_{\max }(S))\ge \exp (\theta t))$ לפי אי-שוויון מרקוב, ההסתברות חסומה על ידי: $\mathbf{𝐏}({\lambda }_{\max }(S)\ge t)\le \mathbf{𝐄}[\exp (\theta {\lambda }_{\max }(S))]\cdot \exp (-\theta t)$ כעת משתמשים בקשר היסודי בין הערך העצמי המקסימלי לעקבה של אקספוננט מטריציוני. לכל מטריצה הרמיטית $A$, מתקיים ${\lambda }_{\max }(A)$ הוא לוגריתם של הרדיוס הספקטרלי של המטריצה החיובית $\exp (A)$. כמו כן, הרדיוס הספקטרלי של מטריצה חיובית חסום על ידי העקבה שלה: $\exp ({\lambda }_{\max }(A))={\lambda }_{\max }(\exp (A))\le \mathrm{T}\mathrm{r}(\exp (A))$ לכן: $\exp (\theta {\lambda }_{\max }(S))\le \mathrm{T}\mathrm{r}(\exp (\theta S))$ מכאן מקבלים את החסם המבוסס על תוחלת העקבה: $\mathbf{𝐏}({\lambda }_{\max }(S)\ge t)\le \underset{\theta >0}{\inf }\{\mathbf{𝐄}[\mathrm{T}\mathrm{r}(\exp (\theta S))]\cdot \exp (-\theta t)\}$ 3. חסם על תוחלת עקבת האקספוננט: זהו השלב המרכזי והטכני ביותר. בשל אי-קומוטטיביות המטריצות, $\exp (\theta S)=\exp (\theta \sum X_k)$ אינו מתפרק למכפלת אקספוננטים. משתמשים בתוצאה עמוקה מתורת המטריצות, הנובעת ממשפט ליב (Lieb's theorem on trace convexity/concavity) או תוצאות קשורות כמו אי-שוויון גולדן-תומפסון. תוצאה מרכזית (למשל, Tropp, Theorem 3.6) מאפשרת לחסום את תוחלת העקבה באופן איטרטיבי או ישיר: $\mathbf{𝐄}[\mathrm{T}\mathrm{r}(\exp (\theta S))]\le \mathrm{T}\mathrm{r}(\exp (\sum _{k=1}^n\log (\mathbf{𝐄}[\exp (\theta X_k)])))$ כאשר $\log$ הוא לוגריתם מטריציוני. 4. חסם על הלוגריתם של תוחלת האקספוננט הבודד: השלב הבא הוא לחסום כל $\log (\mathbf{𝐄}[\exp (\theta X_k)])$. כאן משתמשים בתכונות של $X_k$ (הרמיטית, ממורכזת, חסומה בנורמה על ידי $R$). ניתן להראות, על ידי הכללה של טכניקות מאי-שוויון ברנשטיין הסקלרי, כי מתקיים האי-שוויון המטריציוני (בסדר ליוונר, $A\le B$ פירושו $B-A$ חיובית): $\log (\mathbf{𝐄}[\exp (\theta X_k)])⪯\frac{{\theta }^2}{2}(1-\theta R/3{)}^{-1}\cdot \mathbf{𝐄}[X_k^2]$ (הסימן $⪯$ מציין אי-שוויון בסדר ליוונר. חסם זה תקף בתנאי ש-$\theta R$ קטן מספיק, למשל $\theta R<3$). נסמן את הפקטור הסקלרי $g(\theta ,R)=\frac{{\theta }^2}{2}(1-\theta R/3{)}^{-1}$. 5. הרכבת החסמים: בהצבת החסם על $\log (\mathbf{𝐄}[\exp (\theta X_k)])$ בחזרה ושימוש בתכונות המונוטוניות של אקספוננט ועקבת מטריצות (ובפרט, העובדה ש-$A⪯B$ גורר $\mathrm{T}\mathrm{r}(\exp (A))\le \mathrm{T}\mathrm{r}(\exp (B))$ עבור $A,B$ הרמיטיות), מקבלים: $\mathbf{𝐄}[\mathrm{T}\mathrm{r}(\exp (\theta S))]\le \mathrm{T}\mathrm{r}(\exp (g(\theta ,R)\sum _{k=1}^n\mathbf{𝐄}[X_k^2]))$ נשתמש שוב בתכונת העקבה $\mathrm{T}\mathrm{r}(\exp (A))\le d\cdot {\lambda }_{\max }(\exp (A))=d\cdot \exp ({\lambda }_{\max }(A))$. מכיוון ש-$\sum \mathbf{𝐄}[X_k^2]$ היא מטריצה חיובית ו-$g(\theta ,R)>0$, נקבל: $\mathbf{𝐄}[\mathrm{T}\mathrm{r}(\exp (\theta S))]\le d\cdot \exp (g(\theta ,R)\cdot {\lambda }_{\max }(\sum _{k=1}^n\mathbf{𝐄}[X_k^2]))=d\cdot \exp (g(\theta ,R){\sigma }^2)$ 6. אופטימיזציה של $\theta$: מציבים את החסם על $\mathbf{𝐄}[\mathrm{T}\mathrm{r}(\exp (\theta S))]$ בחזרה לחסם צ'רנוף: $\mathbf{𝐏}({\lambda }_{\max }(S)\ge t)\le \underset{0<\theta <3/R}{\inf }\{d\cdot \exp (g(\theta ,R){\sigma }^2-\theta t)\}$ $\mathbf{𝐏}({\lambda }_{\max }(S)\ge t)\le \underset{0<\theta <3/R}{\inf }\{d\cdot \exp (\frac{{\sigma }^2({\theta }^2/2)}{1-\theta R/3}-\theta t)\}$ מבצעים אופטימיזציה על $\theta$ (בדומה לאי-שוויון ברנשטיין הסקלרי). הבחירה האופטימלית (או קרוב לאופטימלית) של $\theta$ היא $\theta =t/({\sigma }^2+Rt/3)$. הצבת ערך זה של $\theta$ במעריך (לאחר חישוב אלגברי) נותנת: $\exp (-\frac{t^2}{2{\sigma }^2+(2/3)Rt})$ 7. התוצאה הסופית: לאחר הכפלה בפקטור 2 (כפי שהוסבר בשלב 1), מתקבל אי-השוויון המוצהר: $\mathbf{𝐏}(\Vert \sum _{k=1}^n{X}_k\Vert \ge t)\le 2d\cdot \exp (-\frac{t^2}{2{\sigma }^2+(2/3)Rt})$

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

קיימות מספר גרסאות והרחבות לאי-שוויון ברנשטיין למטריצות:

• מטריצות מלבניות: ניתן להכליל את אי-השוויון למקרה שבו $X_k$ הן מטריצות אקראיות מממד $d_1\times d_2$, כאשר $X_k$ אינן בהכרח הרמיטיות. במקרה זה, הנורמה היא עדיין הנורמה האופרטורית, וההגדרות של ${\sigma }^2$ משתנות מעט (לרוב מערבות את $\mathbf{𝐄}[X_k{X}_k^{*}]$ ו-$\mathbf{𝐄}[X_k^{*}{X}_k]$). הפקטור $2d$ מוחלף ב-$d_1+d_2$.
• מטריצות סימטריות: אם המטריצות Xi הן סימטריות, ניתן לקבל חסם דומה עם פקטור 1 במקום 2 לפני d.
• תלות בממד אפקטיבי: הפקטור $d$ יכול להיות פסימי מדי אם למטריצות יש מבנה פנימי, כגון דרגה נמוכה. ניתן להראות שבתנאים מסוימים, $d$ יכול להיות מוחלף ב"ממד אפקטיבי" או "דרגה יציבה" (stable rank), שיכול להיות קטן משמעותית מ-$d$.
• הרפיית תנאי אי-התלות: קיימות גרסאות של אי-השוויון עבור סדרות תלויות של מטריצות, למשל, סדרות המהוות מרטינגל (תורת ההסתברות) מטריציוני (Matrix Martingale). גרסאות אלו דומות לאי-שוויון אזומה-הופדינג למטריצות.
• גרסאות עם קבועים שונים: כאמור, קיימות גרסאות עם קבועים מעט שונים במכנה האקספוננט, הנובעות משימוש בחסמים שונים בהוכחה.

שימושים

אי-שוויון ברנשטיין למטריצות הפך לכלי בסיסי וחשוב בתחומים רבים, ביניהם:

• תורת המטריצות האקראיות: ניתוח התנהגות ספקטרלית של סכומי מטריצות אקראיות, חסימת ריכוז של מטריצות קווריאנציה אמפיריות סביב תוחלתן.
• למידת מכונה וסטטיסטיקה:
  • ניתוח אלגוריתמים של אמידה סטטיסטית בממדים גבוהים.
  • ריכוז של מטריצות גרעין (Kernel matrices).
  • ניתוח ניתוח גורמים ראשיים (PCA) אקראי ואלגוריתמי הורדת ממדים.
  • בניית אמדי קווריאנציה רובוסטיים וקביעת גבולות על שגיאות.
  • ניתוח של שיטות למידה מקוונת (online learning).
• מדעי המחשב העיוניים:
  • ניתוח של אלגוריתמים אקראיים, במיוחד אלגוריתמים על גרפים (למשל, חסימת ההפרש בין לפלסיאן של גרף אקראי לתוחלתו), ניתוח ספקטרלי של מטריצות סמיכויות של גרפים.
  • בנייה וניתוח של אלגוריתמי קירוב, למשל בבעיות כיסוי.
  • שיטות של ספרסיפיקציה ספקטרלית (spectral sparsification) של גרפים.
• תורת האינפורמציה הקוונטית : כפי שצוין, האי-שוויון שימש במקור לחקר ערוצים קוונטיים ויכולת הבחנה בין מצבים קוונטיים.
• עיבוד אותות: ניתוח שיטות שחזור ודגימה, למשל בחישה דחוסה (Compressed Sensing).
• ניתוח רשתות מורכבות: חקר תכונות ספקטרליות של מטריצות שכנות (adjacency matrices) ומטריצות לפלסיאן של רשתות אקראיות.

דוגמה חישובית עבור מטריצה בגודל 2×2

כדי להמחיש את אי-שוויון ברנשטיין למטריצות, נבחן את המקרה הפשוט של שתי מטריצות מקריות סימטריות בגודל $2\times 2$:

$X_1=\left[\begin{array}{cc}a& b\\ b& -a\end{array}\right],X_2=\left[\begin{array}{cc}c& 0\\ 0& -c\end{array}\right]$

כאשר $a,b,c$ הם משתנים מקריים בלתי תלויים עם תוחלת אפס:

$\mathbb{𝔼}[a]=\mathbb{𝔼}[b]=\mathbb{𝔼}[c]=0$

ונניח כי קיימת קבועה $r>0$ כך ש-$|a|,|b|,|c|\le r$ כמעט תמיד.

מגבלת הנורמה

• עבור $X_1$, הערכים העצמיים הם $\pm \sqrt{a^2+b^2}$, ולכן:

$\Vert X_1\Vert =\sqrt{a^2+b^2}\le \sqrt{2}r$

• עבור $X_2$, הערכים העצמיים הם $\pm |c|$, ולכן:

$\Vert X_2\Vert =|c|\le r$

נגדיר את החסם האחיד: $R:=\max (\Vert X_1\Vert ,\Vert X_2\Vert )\le \sqrt{2}r$

חישוב פרמטר השונות

נחשב את המטריצות $X_1^2$ ו-$X_2^2$:

$X_1^2={\left[\begin{array}{cc}a& b\\ b& -a\end{array}\right]}^2=\left[\begin{array}{cc}{a}^2+b^2& 0\\ 0& a^2+b^2\end{array}\right]$

$X_2^2={\left[\begin{array}{cc}c& 0\\ 0& -c\end{array}\right]}^2=\left[\begin{array}{cc}{c}^2& 0\\ 0& c^2\end{array}\right]$

ולכן: $X_1^2+X_2^2=\left[\begin{array}{cc}{a}^2+b^2+c^2& 0\\ 0& a^2+b^2+c^2\end{array}\right]=(a^2+b^2+c^2)\cdot I$

נסמן ${\sigma }_0^2:=\mathbb{𝔼}[a^2]=\mathbb{𝔼}[b^2]=\mathbb{𝔼}[c^2]\le r^2$, ונקבל: ${\sigma }^2:=\Vert \mathbb{𝔼}[X_1^2+X_2^2]\Vert =\mathbb{𝔼}[a^2+b^2+c^2]=3{\sigma }_0^2\le 3r^2$

החלת האי-שוויון

לפי אי-שוויון ברנשטיין למטריצות, עבור $d=2$ ועבור כל $t>0$:

$\mathbb{\mathbb{P}}(\Vert X_1+X_2\Vert \ge t)\le 2d\cdot \exp \left(\frac{-t^2/2}{{\sigma }^2+Rt/3}\right)$

נציב את החסמים: $\mathbb{\mathbb{P}}(\Vert X_1+X_2\Vert \ge t)\le 4\cdot \exp \left(\frac{-t^2/2}{3r^2+(\sqrt{2}r)t/3}\right)$

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

המחשה אמפירית של אי-שוויון ברנשטיין למקרה של מטריצה בגודל 2x2 - סימולציה נומרית

הגרף מציג הדגמה אמפירית של אי-שוויון ברנשטיין למטריצות אקראיות, במקרה של סכום שתי מטריצות סימטריות בגודל 2×2. המחשה של אי-שוויון ברנשטיין עבור סכום של שתי מטריצות מקריות סימטריות בגודל (2*2). ההיסטוגרמה מציגה את ההתפלגות האמפירית של הנורמה הספקטרלית של הסכום X1 + X2, והעקומה האדומה מציגה את החסם התאורטי לפי אי-שוויון ברנשטיין. הקו הירוק מסמן את התוחלת האמפירית, והאזור המוצלל מציין את תחום הריכוז הגבוה לפי האי-שוויון. תיאור הסימולציה הופעל ניסוי חישובי הכולל 10,000 דגימות. בכל דגימה חושבו שתי מטריצות מקריות: מטריצה ראשונה: X1 = [[a, b], [b, -a]] כאשר a ו-b הם מספרים אקראיים אחידים בטווח [-r, r] מטריצה שנייה: X2 = [[c, 0], [0, -c]] כאשר c נבחר גם הוא באותו טווח באופן בלתי תלוי בכל הרצה חושבה הנורמה הספקטרלית (נורמת האופרטור) של סכום המטריצות: X1 + X2 מה מציג הגרף העמודות הכחולות: ההתפלגות האמפירית של ערכי הנורמה הספקטרלית $\Vert X_1+X_2\Vert$ מתוך סימולציה של 10,000 דגימות. הקו האדום: החסם התאורטי שניתן על ידי אי-שוויון ברנשטיין למטריצות. הקו הירוק המקווקו: התוחלת האמפירית (הממוצע) של ערכי הנורמה כפי שנמדדו בניסוי. ההצללה האדומה: תחום הריכוז הגבוה – אזור שבו הסיכוי לחריגה מערכי התוחלת קטן באופן אקספוננציאלי לפי הגבול התאורטי. החסם שמספק אי-שוויון ברנשטיין במקרה זה הוא: $\mathbb{\mathbb{P}}(\Vert X_1+X_2\Vert \ge t)\le 4\cdot \exp \left(\frac{-t^2}{2{\sigma }^2+\frac{2}{3}Rt}\right)$ כאשר: ${\sigma }^2=3r^2$ – גבול על הווריאנס הכולל. $R=\sqrt{2}r$ – חסם על נורמת האופרטור של כל מטריצה. הגרף מדגים כיצד ההתפלגות האמפירית מתכנסת סביב ערך ממוצע, ואת ההשפעה של הגבול התאורטי על סיכוי לסטיות קיצוניות. תובנות מהגרף הגרף ממחיש את האפקטיביות של אי-שוויון ברנשטיין: אף שהתפלגות הנורמה אינה ידועה מראש, החסם מצליח להקיף את הזנב של ההתפלגות בפועל. ניתן לראות שההסתברות לחריגה משמעותית מהתוחלת נמוכה ומתאימה בקירוב לחסם התאורטי. החסם מצליח "לכפות" גבול סביר מעל ערכי הקצה. כלומר, חריגות גדולות מתרחשות לעיתים נדירות, בהתאם למה שהאי-שוויון קובע.

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

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

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

תיאור הסימולציה

בסימולציה זו, נקבעו הפרמטרים הבאים:

• ממד המטריצות: $d=5$
• מספר המטריצות בסכום: $n=50$
• חסם עליון על הנורמה של כל מטריצה: $R=1.0$
• מספר הניסויים (חזרות) בסימולציה: 5000

בכל אחד מ-5000 הניסויים הבלתי תלויים:

1. נוצרה סדרה של $n=50$ מטריצות אקראיות $X_1,\dots ,X_{50}$ מממד $5\times 5$. כל מטריצה $X_k$ נבנתה כך שתקיים את תנאי אי-השוויון:
   • הרמיטיות: $X_k=X_k^{*}$
   • תוחלת אפס: $\mathrm{E}[X_k]=0$ (מטריצת האפס).
   • נורמה חסומה: $\Vert X_k\Vert \le R=1.0$ כמעט בוודאות. (דרך נפוצה להשיג זאת היא ליצור מטריצות עם רכיבים אקראיים ממשיים או מרוכבים בעלי תוחלת אפס ושונות קבועה, לבצע הרמטיזציה (למשל, $(G+G^{*})/2$ אם $G$ היא מטריצת רכיבים גאוסיאניים), ואז לנרמל את המטריצה אם הנורמה שלה חורגת מהחסם $R$).
2. חושב הסכום של המטריצות: $S=\sum _{k=1}^{50}{X}_k$.
3. חושבה הנורמה אופרטורית של הסכום: $\Vert S\Vert$.

לאחר 5000 חזרות, התקבלו 5000 ערכים של $\Vert S\Vert$, המהווים מדגם אמפירי להתפלגות הנורמה של הסכום.

ניתוח הגרפים

היסטוגרמה (גרף שמאל)

הגרף השמאלי מציג היסטוגרמה של 5000 ערכי $\Vert S\Vert$ שהתקבלו בסימולציה. ציר ה-x מייצג את ערך הנורמה האופרטורית $\Vert S\Vert$, וציר ה-y מייצג את צפיפות ההסתברות האמפירית. ניתן לראות שהתפלגות הנורמה מרוכזת סביב ערכים מסוימים (באזור 6-8 במקרה זה). למרות שתוחלת הסכום $S$ היא מטריצת האפס ($\mathrm{E}[S]=0$), הנורמה שלו $\Vert S\Vert$ היא תמיד ערך אי-שלילי המודד את "גודל" הסטייה של $S$ ממטריצת האפס. הריכוז שנצפה בהיסטוגרמה מדגים את העובדה שהסתברות לקבל ערכי נורמה גדולים מאוד היא נמוכה.

הסתברות זנב אמפירית מול חסם ברנשטיין (גרף ימין)

הגרף הימני משווה בין הסתברות הזנב האמפירית לבין החסם התאורטי של ברנשטיין:

• ציר ה-x: ערך הסף $t$.
• ציר ה-y: הסתברות (בסולם לוגריתמי). הסולם הלוגריתמי מדגיש התנהגות של דעיכה מעריכית.
• הקו הכחול (רציף): מייצג את ההסתברות האמפירית $\mathrm{P}(\Vert S\Vert \ge t)$, כפי שנמדדה בסימולציה. ערך זה עבור $t$ נתון הוא פשוט שיעור הניסויים (מתוך 5000) שבהם הנורמה $\Vert S\Vert$ הייתה גדולה או שווה ל-$t$.
• הקו האדום (מקווקו): מייצג את החסם העליון התאורטי שמספק אי-שוויון ברנשטיין למטריצות: $2d\exp (-\frac{t^2}{2{\sigma }^2+(2/3)Rt})$. כדי לצייר גרף זה, יש צורך לחשב או לאמוד את פרמטר השונות ${\sigma }^2=\Vert \sum _{k=1}^n\mathrm{E}[X_k^2]\Vert$ עבור המטריצות הספציפיות שנוצרו בסימולציה (או להשתמש בחסם עליון עבורו).

פרשנות והקשר לאי-השוויון

מהגרפים ניתן ללמוד מספר דברים המדגימים את תכונות אי-שוויון ברנשטיין למטריצות:

1. החסם אכן מתקיים: הקו הכחול (ההסתברות האמיתית, כפי שנצפתה בסימולציה) נמצא תמיד מתחת או על הקו האדום המקווקו (החסם התאורטי). זה מאשר את נכונות אי-השוויון עבור המקרה שנבדק – החסם אכן מהווה חסם עליון להסתברות הזנב.
2. החסם אינו בהכרח הדוק: קיים פער (gap) בין החסם האדום לבין ההסתברות האמיתית הכחולה. הפער יכול להיות משמעותי, במיוחד עבור ערכי $t$ נמוכים. הדבר נובע מאופיו הכללי של אי-השוויון, שנועד להיות נכון עבור כל התפלגות מטריצות המקיימת את התנאים (הרמיטיות, תוחלת אפס, נורמה חסומה, ושונות נתונה), ולכן הוא מהווה חסם "במקרה הגרוע" (worst-case bound) ואינו מותאם ספציפית להתפלגות הגאוסית (או אחרת) ששימשה בסימולציה.
3. לכידת הדעיכה המעריכית: למרות הפער, החסם של ברנשטיין (הקו האדום) מצליח ללכוד את קצב הדעיכה המהיר (המעריכי) של הסתברות הזנב, כפי שמשתקף בשיפוע הירידה הדומה של שני הקווים בציר הלוגריתמי. ככל ש-$t$ גדל, ההסתברות לסטייה גדולה כזו יורדת במהירות, והחסם משקף נכונה התנהגות זו.

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

אי-שוויונות קשורים

• אי-שוויונות ברנשטיין: הגרסה הסקלרית הקלאסית, שאי-שוויון המטריצות מכליל.
• אי-שוויון צ'רנוף למטריצות (Matrix Chernoff Inequality): חסם ריכוז דומה, אך מיועד ספציפית לסכום של מטריצות חיוביות (PSD) אקראיות ובלתי תלויות. לרוב נותן חסמים הדוקים יותר מברנשטיין במקרה זה, והתנאים מנוסחים במונחי הערכים העצמיים המקסימליים של המטריצות הבודדות.
• אי-שוויון הופדינג למטריצות (Matrix Hoeffding Inequality): גרסה פשוטה יותר של אי-שוויון ריכוז למטריצות. הוא מניח רק חסימות על הנורמה של המטריצות הבודדות ($\Vert X_k\Vert \le R_k$) ולא משתמש במידע על השונות ${\sigma }^2$. החסם המתקבל תלוי רק בסכום ריבועי החסמים $\sum R_k^2$. הוא פחות הדוק מברנשטיין כאשר ${\sigma }^2$ קטן משמעותית מסכום ריבועי הנורמות המקסימליות, אך פשוט יותר לשימוש כאשר מידע על השונות אינו זמין.
• אי-שוויון אזומה-הופדינג למטריצות (Matrix Azuma-Hoeffding Inequality): הרחבה של אי-שוויון הופדינג למטריצות לסדרות תלויות של מטריצות המהוות מרטינגל (תורת ההסתברות) מטריציוני. הוא מספק חסם על הסטייה של המרטינגל מערכו ההתחלתי.

ראו גם

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

לקריאה נוספת

• https://arxiv.org/pdf/1004.4389 - מאמר הסקירה המקיף של ג'ואל טרופ, כולל הוכחה מפורטת ודיון ביישומים.
• http://www.cs.cmu.edu/~avrim/Talks/MatrixConcentration.pdf - מצגת הרצאה על אי-שוויוני ריכוז למטריצות] מאת איברים בלום (Avrim Blum) (באנגלית).
• https://terrytao.wordpress.com/2010/01/03/254a-notes-1-concentration-of-measure/ - פוסט בבלוג של טרנס טאו] על ריכוז המידה, כולל דיון באי-שוויונות למטריצות (באנגלית).
• An Introduction to Matrix Concentration Inequalities Joel A. Tropp https://arxiv.org/pdf/1501.01571
• Proof of Matrix Bernstein Inequality: https://pages.cs.wisc.edu/~yudongchen/cs839_sp22/4_mtx_concentration2.pdf
• Proof of Matrix Bernstein Inequality: https://www.stat.cmu.edu/~arinaldo/Teaching/36710/F18/Scribed_Lectures/Oct8.pdf
• https://www.stat.cmu.edu/~larry/=stat705/Lecture3.pdf - Carnegie mellon university Larry Wasserman course on Intermediate Statistics 36-705 - Lecture Notes 3
• Bai & Silverstein, Spectral Analysis of Large Dimensional Random Matrices, 2010
• Terence Tao, Topics in random matrix theory
• Vershynin, R. High-Dimensional Probability. Cambridge University Press, 2018.
• Wainwright, M. J. (2019). High-dimensional statistics: A non-asymptotic viewpoint. Cambridge University Press.
• Joel A. Tropp, An Introduction to Matrix Concentration Inequalities, Foundations and Trends® in Machine Learning, 2015. (ספר מבוא מקיף לנושא).

הערות שוליים

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

אי-שוויון ברנשטיין למטריצות41567524