משפט דייוויס-קהאן

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

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

רקע מתמטי

זווית בין מרחבים וקטורים

יהי מרחב הילברט ${\mathscr{H}}$ ותתי מרחבים וקטורים שלו $M,L$ מאותו מימד $d$. יהיו $U_M,U_L$ מטריצות אוניטריות שעמודותיהן בסיס אורתונורמלי למרחבים $M,L$ בהתאמה (ניתן לחשב את המטריצות באמצעות תהליך גרם-שמידט). יהיו ${\sigma }_1\le ...\le {\sigma }_d$ הערכים הסינגולריים של המטריצה $U_M^{*}{U}_L$. הזווית ה-$i$ בין המרחבים תוגדר ${\cos }^{-1}({\sigma }_i)$ ובהתאם נגדיר מטריצה

$\mathrm{\Theta }(M,L)=\left(\begin{array}{cccc}{\cos }^{-1}{\sigma }_1& 0& \cdots & 0\\ 0& {\cos }^{-1}{\sigma }_2& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & {\cos }^{-1}{\sigma }_d\end{array}\right)$

נגדיר את המטריצה $\sin (\mathrm{\Theta }(M,L))$ בתור המטריצה האלכסונית שמתקבלת מהפעלת סינוס לכל איבר בנפרד במטריצה המוגדרת. מקרה פרטי חשוב הוא הזווית בין שני מרחבים ממימד 1 (שני ישרים). במקרה הזה קיימים שני וקטורים באורך יחידה (הנורמה שלהם שווה $1$) שפורשים כל אחד בנפרד את $M,L$ בהתאמה. מכאן, המטריצה הנ"ל הופכת לסקלר (מטריצה $1\times 1$) :

$U_M^{*}{U}_L=u_M\cdot u_L=\cos (\mathrm{\angle }(u_M,u_L))$

כאשר משתמשים במכפלה הסקלרית ובזווית בין וקטורים שנובעת ממנה. נשים לב לכך שיש חופש בחירה בכיוון הווקטורים $\pm u_M,\pm u_L$. תחת אותו חופש, קיים $ϵ\in \{1,-1\}$ עבורו $ϵu_M\cdot u_L\ge 0$. הערך הסינגולרי היחיד של מטריצה $1\times 1$ הוא הערך המוחלט שלה לכן במקרה הזה הגדרת הזווית בין המרחבים תהיה:

${\cos }^{-1}({\sigma }_1)={\cos }^{-1}(ϵu_M\cdot u_L)=\mathrm{\angle }(ϵu_M,u_L)$

למרות העובדה שהזוויות בין מרחבים יכולות להיות רק בטווח $[0,\pi /2]$ (לעומת שני וקטורים שהזווית בניהם יכולה להיות ב$[0,\pi ]$, זהו הבדל אינהרנטי בין וקטורים בודדים לבין מרחבים וקטורים) הדיון הזה מראה שההגדרה של זווית בין מרחבים מתיישבת עם זו של זווית בין שני וקטורים.

נורמה נשמרת אוניטרית

ערך מורחב – נורמה של מטריצות

נורמה של מרחב מטריצות מסדר $n\times m$ תיקרא נשמרת אוניטרית אם:

$\Vert UAV\Vert =\Vert A\Vert$

לכל $V$ מטריצה אוניטרית מסדר $m\times m$ ו-$U$ אוניטרית מסדר $n\times n$. שתי דוגמאות נפוצות הן נורמת פרוביניוס ונורמת-2 (הנורמה האופרטורית של המטריצה מעל מרחב וקטורי עם הנורמה האוקלידית).

נורמה היא נשמרת אוניטרית אם ורק אם קיימת $f$ פונקציית כיול סימטרית (Symmetric Gauge Function) שמקיימת:

$\Vert A\Vert =f({\sigma }_1,...,{\sigma }_r)$

כאשר ${\sigma }_1,...,{\sigma }_r$ הערכים הסינגולריים של $A$.

נורמה תיקרא תת-כפלית אם לכל שתי מטריצות $A,B$ מתקיים:

$\Vert AB\Vert \le \Vert A\Vert \Vert B\Vert$

כל נורמה נשמרת אוניטרית היא תת-כפלית. בנוסף, יהיו

$P_M,P_L$

ההטלות האורתוגונליות לתתי מרחבים

$M,L$

בהתאמה. ניתן להראות את השוויון:

$\Vert \sin (\mathrm{\Theta }(L,M))\Vert =\Vert (I-P_M)P_L\Vert$

לכל נורמה נשמרת אוניטרית.

ניסוח פורמלי של המשפט

למשפט יש מספר ניסוחים פורמליים שונים, נציג ניסוח של משפט הסינוס ($\sin (\mathrm{\Theta })$) של דייוויס וקהאן הנובע מהמאמר שלהם.

יהיו $A,A+H$ מטריצות הרמיטיות בגודל $n\times n$ עם ${\lambda }_1<{\lambda }_2<...<{\lambda }_n$ ערכים עצמיים של $A$ ו - ${\mu }_1<{\mu }_2<...<{\mu }_n$ ערכים עצמיים של $A+H$. ממשפט הפירוק הספקטרלי, קיימות מטריצות $E$ שוקטורי העמודה שלה הם בסיס אורתונורמלי $u_1,...,u_n$ ו-$F$ עם וקטורי עמודה $v_1,...,v_n$ עבורן:

$A=E\mathrm{\Lambda }{E}^{*},A+H=F\mathrm{M}{F}^{*}$

כאשר $\mathrm{\Lambda },\mathrm{M}$ הן מטריצות אלכסוניות עם הערכים ${\mathrm{\Lambda }}_{ii}={\lambda }_i,{\mathrm{M}}_{ii}={\mu }_i$ בהתאמה. יהי אינדקס $1<d<n$, נגדיר $E=(E_0,E_1)$ כאשר $E_0$ מטריצה עם $d$ וקטורי השורה השמאליים של $E$ (היא מייצגת את הווקטורים שפורשים את כל המרחבים העצמיים עד זה שמתאים לערך העצמי במקום ה-$d$) ו - $E_1$ עם $n-d$ האחרים (מייצגת את הווקטורים העצמיים שפורשים יחד את כל שאר המרחב הווקטורי). באופן דומה נגדיר $F=(F_0,F_1)$. נגדיר ${\mathrm{\Lambda }}_0,{\mathrm{\Lambda }}_1,{\mathrm{M}}_0,{\mathrm{M}}_1$:

$\mathrm{\Lambda }=\left(\begin{array}{cc}{\mathrm{\Lambda }}_0& 0\\ 0& {\mathrm{\Lambda }}_1\end{array}\right),\mathrm{M}=\left(\begin{array}{cc}{\mathrm{M}}_0& 0\\ 0& {\mathrm{M}}_1\end{array}\right)$

כאשר ${\mathrm{\Lambda }}_0,{\mathrm{M}}_0$ בלוקים בגודל $d\times d$ ו-${\mathrm{\Lambda }}_1,{\mathrm{M}}_1$ בלוקים בגודל $(n-d)\times (n-d)$. נגדיר מטריצה:

$R=H{E}_0$

נניח שקיים קטע $[\beta ,\alpha ]$ ו-$\delta >0$ כך ש-${\lambda }_i\in [\beta ,\alpha ]$ לכל $i\in \{1,...,d\}$ וגם ${\mu }_i\notin [\beta -\delta ,\alpha -\delta ]$ לכל $i\in \{d+1,...,n\}$. אזי, עבור $\mathrm{\Theta }$, אופרטור הזווית בין המרחב שנפרש על ידי העמודות של $E_0$ למרחב שנפרש על ידי עמודות $F_0$, לכל נורמה נשמרת אוניטרית מתקיים:

$\delta \Vert \sin (\mathrm{\Theta })\Vert \le \Vert R\Vert$

תוצאות נלוות והכללות

במאמר המקורי של דייוויס וקהאן, הוצגו משפטים נוספים מעבר למשפט ה-$\sin (\mathrm{\Theta })$ הם הוכיחו משפטי $\sin (2\mathrm{\Theta }),\tan (\mathrm{\Theta }),\tan (2\mathrm{\Theta })$. בפועל, משפט $\sin (\mathrm{\Theta })$ מהמאמר הוא הכי משומש מבין כולם.

משפט וודין

משפט וודין (Wedin) מהווה הכללה למשפט דייוויס-קהאן עבור מטריצות שאינן בהכרח הרמיטיות ריבועיות. יהיו $A,A+H$ מטריצות מרוכבות מסדר כללי $m\times n$. קיים פירוק לערכים סינגולריים:

$A=U\mathrm{\Sigma }{V}^{*}=U_0{\mathrm{\Sigma }}_0{V}_0^{*}+U_1{\mathrm{\Sigma }}_1{V}_1^{*}$

כאשר המטריצה $\mathrm{\Sigma }$ מסדר $p\times p$, המטריצה $U$ מסדר $m\times p$ ו-$V$ מסדר $n\times p$. בנוסף, בדומה להגדרה במשפט דייוויס-קהאן נגדיר:

$V=(V_0,V_1),U=(U_0,U_1),\mathrm{\Sigma }=\left(\begin{array}{cc}{\mathrm{\Sigma }}_0& 0\\ 0& {\mathrm{\Sigma }}_1\end{array}\right)$

באמצעות פיצול בין $d$ העמודות הראשונות לשאר העמודות. פירוק דומה ניתן לעשות למטריצה $B=A+H$. נגדיר:

$A_j=U_j(A){\mathrm{\Sigma }}_j(A)V_j^{*}(A),B_j=U_j(B){\mathrm{\Sigma }}_j(B)V_j^{*}(B)$

נגדיר:

$R_{11}=-H{V}_1(B),R_{21}=-H^{*}{U}_1(B)$

משפט וודין גורס כי אם הערכים הסינגולריים מקיימים ${\sigma }_{\min }(B_1)\ge \alpha +\delta$ וגם ${\sigma }_{\max }(A_0)\le \alpha$ אז עבור:

$ϵ=\max (\Vert R_{11}\Vert ,\Vert R_{21}\Vert )$

בסימון $Im(M)$ המרחב הווקטורי שהוא תמונה של ההעתקה $M$ נקבל את אי השוויונות הבאים:

$\Vert \sin (\mathrm{\Theta }(Im(B_1),Im(A_1))\Vert \le \frac{ϵ}{\delta }$ $\Vert \sin (\mathrm{\Theta }(Im(B_1^{*}),Im(A_1^{*}))\Vert \le \frac{ϵ}{\delta }$

הרחבה של המשפט לסטטיסטיקאים

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

יהיו $A,A+H$ מטריצות סימטריות מסדר $n\times n$ עם ${\lambda }_1<{\lambda }_2<...<{\lambda }_n$ ערכים עצמיים של $A$ ו - ${\mu }_1<{\mu }_2<...<{\mu }_n$ ערכים עצמיים של $A+H$. נגדיר ${\lambda }_0=\mathrm{\infty },{\lambda }_{n+1}=-\mathrm{\infty }$ ונקבע $1\le r\le s\le n$. נניח ש-$\delta =\min ({\lambda }_{r-1}-{\lambda }_r,{\lambda }_s-{\lambda }_{s+1})>0$ נגדיר $d=s-r+1$. יהיו $M$ המרחב שנפרש על ידי $u_r,...,u_s$ הערכים העצמיים של $A$ ו-$L$ המרחב שנפרש על ידי $v_r,...,v_s$ הערכים העצמיים של $A+H$. מתקיים:

$\Vert \sin (\mathrm{\Theta }(M,L)){\Vert }_F\le \frac{2\min (d^{1/2}\Vert H{\Vert }_{op},\Vert H{\Vert }_F)}{\delta }$

כאשר $\Vert \cdot {\Vert }_F$ נורמת פרובניוס ו-$\Vert \cdot {\Vert }_{op}$ נורמת 2 - הנורמה האופרטורית האוקלידית.

מקרה פרטי של ההרחבה הזו כאשר $r=s=j$ בא לידי ביטוי במספר שימושים של משפט דייוויס-קהאן. נניח שמתקיים:

$\underset{i\ne j}{\min }|{\lambda }_j-{\lambda }_i|=\delta >0$

אזי, אם $u_j$ וקטור עצמי של $A$ המתאים לערך העצמי ${\lambda }_j$ וגם $v_j$ וקטור עצמי של $A+H$ המתאים לערך העצמי ${\mu }_j$, קיים $ϵ\in \{-1,1\}$ כך שהזווית בין הווקטורים:

$0\le \sin (\mathrm{\angle }(ϵv_j,u_j))\le \frac{2\min (\Vert H{\Vert }_F,\Vert H{\Vert }_{op})}{\delta }$

בנוסף לכך, הראו במאמר תוצאה בעלת אופי דומה:

$\Vert u_j-ϵv_j\Vert \le \frac{2^{3/2}\min (\Vert H{\Vert }_F,\Vert H{\Vert }_{op})}{\delta }$

אי-שוויון וייל

ערך מורחב – אי-שוויון וייל

בעוד משפט דייוויס-קהאן עוסק בקשר בין וקטורים עצמיים של מטריצה הרמיטית תחת הפרעה, אי שוויון וויל (Weyl) מספק חסם על שינוי הערכים העצמיים. בדומה לניסוח תנאי משפט דייוויס-קהאן, יהיו $A,A+H$ מטריצות הרמיטיות ממימד n. נסמן ${\lambda }_i(A)$ בתור הערך העצמי ה-i של $A$ (כאשר הערכים העצמיים בסדר יורד, ניתן לעשות זאת כי המטריצה הרמיטית). אי שוויון וויל אומר כי:

${\lambda }_{i+j-1}(A+H)\le {\lambda }_i(A)+{\lambda }_j(H)\le {\lambda }_{i+j-n}(A+H)$

רעיונות מרכזיים בהוכחה

נתבסס על ההוכחה של המשפט במאמר של דייוויס וקהאן. תחילה, נשתמש בטענת עזר - תהי נורמה נשמרת אוניטרית ויהיו $\alpha \ge 0,\delta >0$ ויהיו שני אופרטורים שמקיימים $\Vert A^{-1}\Vert \le (\alpha +\delta {)}^{-1}$ וגם $\Vert B\Vert \le \alpha$ ויהי אופרטור $X$ אזי האופרטור:

$C=AX-XB$

מקיים $\Vert C\Vert \le \delta \Vert X\Vert$.

הוכחת טענת העזר: מתת-כפליות של נורמה נשמרת אוניטרית, $\Vert XB\Vert \le \alpha \Vert X\Vert$ וגם $\Vert AX\Vert \ge (\alpha +\delta )\Vert X\Vert$ ומאי-שוויון המשולש:

$\Vert C\Vert \ge \Vert AX\Vert -\Vert XB\Vert \ge \delta \Vert X\Vert$

כנדרש.

כעת נכתוב בצורה יותר מפורשת את המטריצות:

$$\begin{gathered} A+H=\left(\begin{array}{cc} \\ {E}_0& E_1\end{array}\right)\left(\begin{array}{cc}{\mathrm{\Lambda }}_0+H_0& B^{*}\\ B& {\mathrm{\Lambda }}_1+H_1\end{array}\right)\left(\begin{array}{c} \\ {E}_0^{*}\\ \\ {E}_1^{*}\end{array}\right)=\left(\begin{array}{cc} \\ {F}_0& F_1\end{array}\right)\left(\begin{array}{cc}{\mathrm{M}}_0& 0\\ 0& {\mathrm{M}}_1\end{array}\right)\left(\begin{array}{c} \\ {F}_0^{*}\\ \\ {F}_1^{*}\end{array}\right) \end{gathered}$$

מהכתיבה המפורשת של המטריצות ניתן להסיק $A{E}_0=E_0{\mathrm{\Lambda }}_0$. לכן:

$R=H{E}_0=(A+H)E_0-E_0{\mathrm{\Lambda }}_0$

כעת, מפני שנורמת האופרטור $F_1$ חסומה על ידי $1$, מתת-כפליות $\Vert R\Vert =\Vert R^{*}\Vert \ge \Vert R^{*}{F}_1\Vert$. נקבל:

$R^{*}{F}_1=E_0^{*}{F}_1{\mathrm{M}}_1-{\mathrm{\Lambda }}_0{E}_0^{*}{F}_1$

נוסיף לאופרטור $A$ כפולה של מטריצת היחידה (ניתן לעשות זאת מכיוון שזה לא משנה את המרחבים העצמיים) כך שנקבל $0\le \alpha =-\beta$. בצורה הזו מהנתון בתנאי המשפט על ההפרש בספקטרום, נוכל להשתמש בטענת העזר:

$\Vert R^{*}{F}_1\Vert \ge \delta \Vert E_0^{*}{F}_1\Vert$

לבסוף, ניתן להראות שלאופרטור $E_0^{*}{F}_1$ יש אותם ערכים סינגולריים כמו ל-$\sin (\mathrm{\Theta })$, ומפני שנורמה נשמרת אוניטרית היא פונקציה של הערכים הסינגולריים של האופרטור, מתקיים:

$\Vert R\Vert \ge \delta \Vert E_0^{*}{F}_1\Vert =\delta \Vert \sin (\mathrm{\Theta })\Vert$

היסטוריה

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

בשנת 1970 יצא משפט דייוויס-קהאן שהפך לכלי מרכזי בהבנת רגישותם של תתי מרחבים ספקטרליים להפרעות, בכך שהציע גבול ברור על הזווית בין מרחבים עצמיים של מטריצה ומטריצה מופרעת. תוצאה זו הייתה חשובה במיוחד לאנליסטים נומריים, והיא הובילה לפיתוחים נוספים בתחום. בשנת 1972, תוצאות אלו הורחבו על ידי וודין למטריצות לא הרמיטיות, מה שאִפשר את יישום התיאוריה גם במקרים של מטריצות מלבניות כלליות. במאמר מ-2015 של יו טנגיאו וואנג וריצ'רד סאמוורת' הותאמה תוצאת דייוויס-קאהן להקשרים סטטיסטיים, עם תנאי הפרדה מקלים בין ערכים עצמיים של אוכלוסייה ומדגם, מה שהרחיב את השימוש בה ואפשר גישה ליישומים מעשיים. בשנת 2018, שיפרו אלדרידג', בלקין ו-וואנג את חסמי ההפרעה הקלאסיים על ידי התחשבות ברעש אקראי. הם הציעו חסמים מדויקים יותר להפרעות בערכים עצמיים ובווקטורים עצמיים, והתוצאות עלו בביצועיהן על אלו של משפטים מסורתיים כמו משפט וייל ברבים מהמקרים המעשיים. חשוב לציין שרשימת הפיתוחים הנ"ל אינה ממצה את מה שקיים בספרות המתמטית.

הקשר לתורת ההפרעות

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

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

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

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

מודל Spiked Covariance

ערך מורחב – מודל Spiked Covariance

מודל זה עוסק באומדן וקטור עצמי מוביל של מטריצת שונות משותפת מדגמית. במצבים בהם הווקטור העצמי המוביל בולט בצורה משמעותית על פני וקטורים אחרים, באמצעות משפט דייוויס-קהאן ניתן להעריך את מידת הקרבה בין הווקטור העצמי האמיתי לבין זה שנאמד על בסיס דגימות אקראיות. באופן פורמלי, יהיו $X_1,...,X_n\stackrel{i.i.d}{\sim }(0,\mathrm{\Sigma })$ וקטורים אקראיים ב - ${\mathbb{ℝ}}^d$. נניח שמטריצת השונות המשותפת, $\mathrm{\Sigma }$ היא $\mathrm{\Sigma }=\theta v{v}^T+I_d$ עבור $\theta >0$ ו - $v\in {\mathbb{ℝ}}^d$ וקטור בגודל יחידה ($\Vert v\Vert =1$). מההגדרה הנ"ל, הערך העצמי הגדול ביותר של מטריצה $\mathrm{\Sigma }$ הוא $1+\theta$ עם וקטור עצמי מתאים $v$. אנחנו מעוניינים להסיק מהו $v$ על סמך דגימות. תהי ${\mathrm{\Sigma }}_n=\frac{1}{n}\sum _{i=1}^n{X}_i{X}_i^T$ ויהי $v_n$ הווקטור העצמי (בגודל יחידה) המוביל של ${\mathrm{\Sigma }}_n$ נשתמש בחישוב הבא:

$\Vert v_n-v{\Vert }^2=⟨v_n-v,v_n-v⟩=\Vert v_n{\Vert }^2+\Vert v{\Vert }^2-⟨v_n,v⟩-⟨v,v_n⟩=2-2|v^T{v}_n|$

כעת, מאי שוויון קושי שוורץ, $|v^T{v}_n|\le \Vert v_n\Vert \cdot \Vert v\Vert =1$ לכן:

$2-2|v^T{v}_n|\le 2-2|v^T{v}_n{|}^2=2-2\cdot \frac{|v^T{v}_n{|}^2}{(\Vert v_n\Vert \Vert v\Vert {)}^2}=2-2{\cos }^2(\mathrm{\angle }(v,v_n))=2{\sin }^2(\mathrm{\angle }(v,v_n))$

מפני שההפרש בין הערך העצמי המוביל לכל הבאים הוא $\theta$, נשתמש ב (הרחבה לסטטיסטיקאים של) משפט דייוויס-קהאן ונקבל:

$\Vert v_n-v{\Vert }^2\le 8\frac{\Vert {\mathrm{\Sigma }}_n-\mathrm{\Sigma }{\Vert }_F^2}{{\theta }^2}$

תחת הנחות נוספות ניתן לקבל חסם על $\Vert {\mathrm{\Sigma }}_n-\mathrm{\Sigma }{\Vert }_F$ והערכה על קצב הדעיכה של $\Vert v_n-v\Vert$.

מודל בלוקים סטוכסטי

ערך מורחב – מודל בלוקים סטוכסטי

נראה שימוש למקרה פרטי של מודל בלוקים סטוכסטי. יהי גרף שקבוצת הקודקודים בו מחולקת לשתי קהילות שבה כל זוג נקודות בתוך הקהילה מחוברות זו לזו בהסתברות $p$ וכל זוג נקודות בקהילות שונות מחוברות זו לזה בהסתברות $q$. מטריצת השכנויות של הגרף מוגדרת באופן הסתברותי כך ש-$A_{i,j}$ מתפלג ברנולי בהסתברות $p$ אם $i,j$ באותה קהילה ומתפלג ברנולי בהסתברות $q$ אם הם בקהילות שונות. נשים לב לכך שהתוחלת של המטריצה $A$ היא:

$P=\mathbb{𝔼}(A)=\left[\begin{array}{cccccc}p& p& \cdots & q& q& \cdots \\ p& p& \cdots & q& q& \cdots \\ ⋮& ⋮& \ddots & ⋮& ⋮& \cdots \\ q& q& \cdots & p& p& \cdots \\ q& q& \cdots & p& p& \cdots \\ ⋮& ⋮& \cdots & ⋮& ⋮& \ddots \end{array}\right]$

משמע $\mathbb{𝔼}(A{)}_{i,j}$ מטריצת בלוקים שכל אחד מארבעת הבלוקים מטריצה שמקבלת רק הערך $p$ או $q$ בהתאמה. אפשר להראות שהדרגה של $P$ היא $2$, שהערך העצמי המוביל הוא ${\lambda }_1=(\frac{p+q}{2})n$ והווקטור העצמי המתאים לו הוא:

$u_1(P)=\frac{1}{\sqrt{n}}\left[\begin{array}{c}1\\ 1\\ ⋮\\ 1\\ 1\end{array}\right]$

הערך העצמי השני הוא ${\lambda }_1=(\frac{p-q}{2})n$ והווקטור העצמי המתאים לו:

$u_2(P)=\frac{1}{\sqrt{n}}\left[\begin{array}{c}1\\ ⋮\\ 1\\ -1\\ ⋮\\ -1\end{array}\right]$

נרצה לנחש את הקהילות המקוריות באמצעות קירוב את הווקטור העצמי השני (אם $u_2(P{)}_i=1$ אז $i$ בקהילה אחת ואם $u_2(P{)}_i=-1$ אז $i$ בקהילה השנייה). נשתמש במשפט הבא:

תהי $E$ מטריצה ממשית מסדר $n\times n$ עם איברים $e_{ij}$ שכל אחד משתנה מקרי בעל תוחלת $0$ ומתפלג תת-גאוסית עם נורמת תת-גאוסית $k$. לכל $t>0$ קיים $C$ קבוע כך שאי השוויון הבא מתקיים:

$\mathbb{\mathbb{P}}(\Vert E\Vert \le Ck(\sqrt{n}+t))\ge 1-e^{-t^2}$

מכאן, מפני שהמטריצה נגדיר מטריצה חדשה $E=A-P$ מקיימת את תנאי המשפט, בהסתברות גבוהה מתקיים:

$\Vert E{\Vert }_{op}\le C\cdot \sqrt{n}$

בנוסף, ההפרש בין הערך העצמי השני לערכים העצמיים הקרובים אליו (הראשון והשלישי) של $P$ הוא:

$\delta =\min (\frac{p+q}{2}n-\frac{p-q}{2}n,\frac{p-q}{2}n-0)=n\cdot \min (q,\frac{p-q}{2})$

מכאן, בשימוש בהרחבה של משפט דייוויס-קהאן לסטטיסטיקאים, נקבל בהסתברות גבוהה שקיים $ϵ\in \{-1,1\}$ עבורו הווקטור העצמי השני מקיים:

$$\begin{gathered} \Vert u_2(A)-ϵu_2(P) \\ \Vert \le \frac{2^{3/2}\Vert E{\Vert }_{op}}{\delta }\le \frac{2C}{\min (q,\frac{p-q}{2})\sqrt{n}} \end{gathered}$$

ניתן להראות שמספר האינדקסים בהם הסימן של $ϵu_2(P{)}_i$ שונה מזה של $u_2(A{)}_i$ שואף ל-$0$ כאשר $n$ שואף לאינסוף. לכן, עבור $n$ מספיק גדול, בהסתברות גבוהה מספר טעויות הסיווג יהיה קטן.

ראו גם

תורת ההפרעות
משפט הפירוק הספקטרלי
ספקטרום (מתמטיקה)
פירוק לערכים סינגולריים
אי-שוויון וייל
מודל בלוקים סטוכסטי
מודל spiked covariance
תורת ההפרעות (מכניקת הקוונטים)