הצגת המקור של הדף "משפט דייוויס-קהאן"

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

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

== רקע מתמטי ==
=== זווית בין מרחבים וקטורים {{אנ|Angles between flats}} ===
יהי [[מרחב הילברט]] <math>\mathcal{H}</math> ותתי [[מרחב וקטורי|מרחבים וקטורים]] שלו <math>M,L</math> מאותו [[ממד (אלגברה ליניארית)|מימד]] <math>d</math>. יהיו <math>U_M,U_L</math> [[מטריצה אוניטרית|מטריצות אוניטריות]] שעמודותיהן [[מערכת אורתונורמלית שלמה|בסיס אורתונורמלי]] למרחבים <math>M,L</math> בהתאמה (ניתן לחשב את המטריצות באמצעות [[תהליך גרם-שמידט]]). יהיו <math>\sigma_1 \le...\le \sigma_d</math> [[פירוק לערכים סינגולריים|הערכים הסינגולריים]] של המטריצה <math>U_M^*U_L</math>. הזווית ה-<math>i</math> בין המרחבים תוגדר <math>\cos^{-1}(\sigma_i)</math> ובהתאם נגדיר מטריצה<ref>{{cite journal|author=P. Zhu and A. V. Knyazev|year=2013|title=Angles between subspaces and their tangents|journal=J. Numer. Math.|volume=21|number=4}}</ref>

<center>
<math>
\Theta(M,L) = \begin{pmatrix}
\cos^{-1} \sigma_1 & 0 & \cdots & 0 \\
0 & \cos^{-1} \sigma_2 & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & \cos^{-1} \sigma_d
\end{pmatrix}
</math>
</center>
נגדיר את המטריצה <math>\sin(\Theta(M,L))</math> בתור המטריצה האלכסונית שמתקבלת מהפעלת סינוס לכל איבר בנפרד במטריצה המוגדרת. [[מקרה פרטי]] חשוב הוא הזווית בין שני מרחבים ממימד 1 (שני [[ישר]]ים). במקרה הזה קיימים שני וקטורים באורך יחידה (ה[[נורמה]] שלהם שווה <math>1</math>) שפורשים כל אחד בנפרד את <math>M,L</math> בהתאמה. מכאן, המטריצה הנ"ל הופכת ל[[סקלר (מתמטיקה)|סקלר]] (מטריצה <math>1\times 1</math>) :
<center>
<math>
U_M^*U_L = u_M \cdot u_L = \cos(\angle(u_M,u_L))
</math>
</center>
כאשר משתמשים [[מכפלה סקלרית|במכפלה הסקלרית]] ובזווית בין וקטורים שנובעת ממנה. נשים לב לכך שיש חופש בחירה בכיוון הווקטורים <math>\pm u_M,\pm u_L</math>. תחת אותו חופש, קיים <math>\epsilon \in \{1,-1\}</math> עבורו <math>\epsilon u_M \cdot u_L \ge 0</math>. הערך הסינגולרי היחיד של מטריצה <math>1\times 1</math> הוא [[ערך מוחלט|הערך המוחלט]] שלה לכן במקרה הזה הגדרת הזווית בין המרחבים תהיה:
<center>
<math>
\cos^{-1}(\sigma_1) = \cos^{-1}(\epsilon u_M \cdot u_L) = \angle(\epsilon u_M,u_L)
</math>
</center>
למרות העובדה שהזוויות בין מרחבים יכולות להיות רק בטווח <math>[0,\pi / 2]</math> (לעומת שני וקטורים שהזווית בניהם יכולה להיות ב<math>[0,\pi]</math>, זהו הבדל אינהרנטי בין וקטורים בודדים לבין מרחבים וקטורים) הדיון הזה מראה שההגדרה של זווית בין מרחבים מתיישבת עם זו של זווית בין שני וקטורים.

=== נורמה נשמרת אוניטרית ===
{{הפניה לערך מורחב|ערך=[[נורמה של מטריצות]]}}
נורמה של מרחב מטריצות מסדר <math>n\times m</math> תיקרא נשמרת אוניטרית אם:
<center>
<math>
\Vert UAV \Vert = \Vert A \Vert
</math>
</center>
לכל <math>V</math> מטריצה אוניטרית מסדר <math>m\times m</math> ו-<math>U</math> אוניטרית מסדר <math>n\times n</math>. שתי דוגמאות נפוצות הן נורמת פרוביניוס ונורמת-2 (הנורמה האופרטורית של המטריצה מעל מרחב וקטורי עם ה[[נורמה (אנליזה)|נורמה]] האוקלידית).

נורמה היא נשמרת אוניטרית [[אם ורק אם]] קיימת <math>f</math> פונקציית כיול סימטרית (Symmetric Gauge Function) שמקיימת<ref>{{Cite journal|last=Mirsky|first=L.|year=1960|title=Symmetric Gauge Functions and Unitarily Invariant Norms|url=https://doi.org/10.1093/qmath/11.1.50|journal=The Quarterly Journal of Mathematics|publisher=Oxford University Press|volume=11|issue=1|pages=50–59|doi=10.1093/qmath/11.1.50|access-date=2024-10-14}}</ref>:
<center>
<math>
\Vert A \Vert = f(\sigma_1,...,\sigma_r)
</math>
</center>
כאשר <math>\sigma_1,...,\sigma_r</math> הערכים הסינגולריים של <math>A</math>.<ref>{{Cite web |last=Higham |first=Nicholas |date=2021-02-02 |title=What is a unitarily invariant norm |url=https://nhigham.com/2021/02/02/what-is-a-unitarily-invariant-norm/ |website=Nicholas Higham's Blog |access-date=2024-10-06}}</ref>

נורמה תיקרא תת-כפלית אם לכל שתי מטריצות <math>A,B</math> מתקיים:
<center>
<math>
\Vert AB \Vert \le \Vert A \Vert \Vert B \Vert
</math>
</center>
כל נורמה נשמרת אוניטרית היא תת-כפלית.<ref>{{Cite book |author=Bhatia, Rajendra |title=Matrix Analysis |publisher=Springer |year=1997 |url=https://link.springer.com/book/10.1007/978-1-4612-0653-8|pages=94|access-date=2024-10-06}}</ref> בנוסף, יהיו <math>P_M,P_L</math> ה[[הטלה (מתמטיקה)|הטלות האורתוגונליות]] לתתי מרחבים <math>M,L</math> בהתאמה. ניתן להראות את השוויון:<ref>{{cite journal |author=Chandler Davis and W. M. Kahan |title=The Rotation of Eigenvectors by a Perturbation |journal=SIAM Journal on Numerical Analysis |volume=7 |number=1 |year=1970 |pages=10}}</ref><center>
<math> \Vert \sin(\Theta(L,M)) \Vert = \Vert (I - P_M)P_L \Vert </math>
</center>
לכל נורמה נשמרת אוניטרית.

== ניסוח פורמלי של המשפט ==
למשפט יש מספר ניסוחים פורמליים שונים, נציג ניסוח של משפט הסינוס (<math>\sin(\Theta)</math>) של דייוויס וקהאן הנובע מהמאמר שלהם.<ref name="DavisKahan1970">{{cite journal|author=Chandler Davis and W. M. Kahan|year=1970|title=The Rotation of Eigenvectors by a Perturbation |journal=SIAM Journal on Numerical Analysis|volume=7|number=1}}</ref>

יהיו <math>A,A+H</math> מטריצות הרמיטיות בגודל <math>n\times n</math> עם <math>\lambda_1<\lambda_2<...<\lambda_n </math> ערכים עצמיים של <math>A</math> ו - <math>\mu_1<\mu_2<...<\mu_n </math> ערכים עצמיים של <math>A+H</math>. מ[[משפט הפירוק הספקטרלי]], קיימות מטריצות <math>E</math> שוקטורי העמודה שלה הם בסיס אורתונורמלי <math>u_1,...,u_n</math> ו-<math>F</math> עם וקטורי עמודה <math>v_1,...,v_n</math> עבורן:
<center><math> A = E \Lambda E^{*}, A+H=F\Mu F^*</math></center>
כאשר <math>\Lambda,\Mu</math> הן [[מטריצה אלכסונית|מטריצות אלכסוניות]] עם הערכים <math>\Lambda_{ii}=\lambda_i,\Mu_{ii}=\mu_i</math> בהתאמה. יהי אינדקס <math>1<d<n</math>, נגדיר <math>E=(E_0, E_1)</math> כאשר <math>E_0</math> מטריצה עם <math>d</math> וקטורי השורה השמאליים של <math>E</math> (היא מייצגת את הווקטורים שפורשים את כל המרחבים העצמיים עד זה שמתאים לערך העצמי במקום ה-<math>d</math>) ו - <math>E_1</math> עם <math>n-d</math> האחרים (מייצגת את הווקטורים העצמיים שפורשים יחד את כל שאר המרחב הווקטורי). באופן דומה נגדיר <math>F=(F_0,F_1)</math>. נגדיר <math>\Lambda_0,\Lambda_1,\Mu_0,\Mu_1</math>:
<center>
<math>
\Lambda = \begin{pmatrix}
\Lambda_0 & 0 \\
0 & \Lambda_1
\end{pmatrix}
,
\Mu = \begin{pmatrix}
\Mu_0 & 0 \\
0 & \Mu_1
\end{pmatrix}
</math>
</center>
כאשר <math>\Lambda_0,\Mu_0</math> [[מטריצת בלוקים|בלוקים]] בגודל <math>d\times d</math> ו-<math>\Lambda_1,\Mu_1</math> בלוקים בגודל <math>(n-d)\times (n-d)</math>. נגדיר מטריצה:
<center>
<math>
R=H E_0
</math>
</center>

נניח שקיים [[קטע (מתמטיקה)|קטע]] <math>[\beta, \alpha]</math> ו-<math>\delta >0</math> כך ש-<math>\lambda_i \in [\beta, \alpha]</math> לכל <math> i\in \{1,...,d\}</math> וגם <math>\mu_i\notin [\beta-\delta, \alpha-\delta]</math> לכל <math>i\in \{d+1,...,n\}</math>. אזי, עבור <math>\Theta</math>, אופרטור הזווית בין המרחב שנפרש על ידי העמודות של <math>E_0</math> למרחב שנפרש על ידי עמודות <math>F_0</math>, לכל נורמה נשמרת אוניטרית מתקיים:
<center><math> \delta \| \sin(\Theta) \| \leq \| R \| </math></center>

== תוצאות נלוות והכללות ==
במאמר המקורי של דייוויס וקהאן, הוצגו משפטים נוספים מעבר למשפט ה-<math>\sin(\Theta)</math> הם הוכיחו משפטי <math>\sin(2\Theta),\tan(\Theta), \tan(2\Theta)</math>. בפועל, משפט <math>\sin(\Theta)</math> מהמאמר הוא הכי משומש מבין כולם.<ref name="DavisKahan1970"/>

=== משפט וודין ===
משפט [[פר אקאי וודין|וודין]] (Wedin) מהווה הכללה למשפט דייוויס-קהאן עבור מטריצות שאינן בהכרח הרמיטיות [[מטריצה ריבועית|ריבועיות]].<ref name="Wedin1972">{{cite journal|author=Per-Ake Wedin|year=1972|title=Perturbation Bounds in Connection with Singular Value Decomposition|journal=BIT|volume=12}}</ref> יהיו <math>A,A+H</math> מטריצות [[מספר מרוכב|מרוכבות]] מסדר כללי <math>m\times n</math>. קיים פירוק לערכים סינגולריים:
<center><math> A=U\Sigma V^* = U_0\Sigma_0 V_0^* + U_1\Sigma_1 V_1^*    </math></center>
כאשר המטריצה <math>\Sigma</math> מסדר <math>p\times p</math>, המטריצה <math>U</math> מסדר <math>m\times p</math> ו-<math>V</math>
מסדר <math> n\times p</math>. בנוסף, בדומה להגדרה במשפט דייוויס-קהאן נגדיר:
<center><math>V = (V_0, V_1), \, U = (U_0, U_1), \, \Sigma = \begin{pmatrix} \Sigma_0 & 0 \\ 0 & \Sigma_1 \end{pmatrix}</math></center>
באמצעות פיצול בין <math>d</math> העמודות הראשונות לשאר העמודות. פירוק דומה ניתן לעשות למטריצה <math>B=A+H</math>. נגדיר:
<center><math>A_j = U_j(A) \Sigma_j(A) V_j^*(A), B_j = U_j(B) \Sigma_j(B) V_j^*(B)</math></center>
נגדיר:
<center><math>R_{11} = -H V_1(B), R_{21} = -H^* U_1(B) </math></center>
משפט וודין גורס כי אם הערכים הסינגולריים מקיימים <math>\sigma_{\min}(B_1)\ge \alpha+\delta</math> וגם <math>\sigma_{\max}(A_0)\le \alpha</math> אז עבור:
<center><math>\epsilon = \max(\Vert R_{11} \Vert, \Vert R_{21} \Vert)</math></center>
בסימון <math>Im(M)</math> המרחב הווקטורי שהוא תמונה של ההעתקה <math>M</math> נקבל את אי השוויונות הבאים:
<center><math>\Vert \sin(\Theta(Im(B_1),Im(A_1))\Vert \le \frac{\epsilon}{\delta} </math></center>

<center><math>\Vert \sin(\Theta(Im(B_1^*),Im(A_1^*))\Vert \le \frac{\epsilon}{\delta} </math></center>

=== הרחבה של המשפט לסטטיסטיקאים ===
במשפט דייוויס קהאן, נדרשת אמירה על הספקטרום של שתי המטריצות - המקורית וזו אחרי ההפרעה. במאמר של [[יו טנגיאו וואנג]] ו-[[ריצ'רד סאמוורת']]{{אנ|Richard Samworth}} הרחבה המאפשרת להשתמש בדרישות רק על הספקטרום של <math>A</math>.<ref name="Yu2015">{{Cite journal |last1=Yu |first1=Y. |last2=Wang |first2=T. |last3=Samworth |first3=R. J. |title=A useful variant of the Davis–Kahan theorem for statisticians |journal=Biometrika |volume=102 |issue=2 |year=2015 |doi=10.1093/biomet/asv008 |publisher=Oxford University Press}}</ref>

יהיו <math>A,A+H</math> מטריצות סימטריות מסדר <math>n\times n</math> עם <math>\lambda_1<\lambda_2<...<\lambda_n </math> ערכים עצמיים של <math>A</math> ו - <math>\mu_1<\mu_2<...<\mu_n </math> ערכים עצמיים של <math>A+H</math>. נגדיר <math>\lambda_0 = \infty,\lambda_{n+1}=-\infty</math> ונקבע <math>1\le r \le s \le n</math>. נניח ש-<math>\delta = \min(\lambda_{r-1}-\lambda_r,\lambda_{s}-\lambda_{s+1})>0</math> נגדיר <math>d=s-r+1</math>. יהיו <math>M</math> המרחב שנפרש על ידי <math>u_r,...,u_s</math> הערכים העצמיים של <math>A</math> ו-<math>L</math> המרחב שנפרש על ידי <math>v_r,...,v_s</math> הערכים העצמיים של <math>A+H</math>. מתקיים:
<center><math> \Vert \sin(\Theta(M,L)) \Vert_F \leq \frac{2 \min (d^{1/2} \Vert H \Vert_{op},\Vert H \Vert_F)}{\delta} </math></center>

כאשר <math>\Vert \cdot \Vert_F</math> נורמת פרובניוס ו-<math>\Vert \cdot \Vert_{op}</math> נורמת 2 - הנורמה האופרטורית האוקלידית.

מקרה פרטי של ההרחבה הזו כאשר <math>r=s=j</math> בא לידי ביטוי במספר שימושים של משפט דייוויס-קהאן. נניח שמתקיים:
<center><math> \min_{i \ne j} |\lambda_j - \lambda_i| = \delta > 0 </math></center>

אזי, אם <math>u_j</math> וקטור עצמי של <math>A</math> המתאים לערך העצמי <math>\lambda_j</math> וגם <math>v_j</math> וקטור עצמי של <math>A+H</math> המתאים לערך העצמי <math>\mu_j</math>, קיים <math>\epsilon\in\{-1,1\}</math> כך שהזווית בין הווקטורים:

<center><math> 0 \le \sin(\angle (\epsilon v_j, u_j)) \leq \frac{2 \min(\Vert H \Vert_F,\Vert H \Vert_{op})}{\delta} </math></center>

בנוסף לכך, הראו במאמר תוצאה בעלת אופי דומה:
<center><math> \Vert u_j - \epsilon v_j \Vert \le \frac{2^{3/2}\min(\Vert H \Vert_F,\Vert H \Vert_{op})}{\delta} </math></center>

=== אי-שוויון וייל ===
{{הפניה לערך מורחב|ערך=[[אי-שוויון וייל]]}}
בעוד משפט דייוויס-קהאן עוסק בקשר בין וקטורים עצמיים של מטריצה הרמיטית תחת הפרעה, אי שוויון וויל (Weyl) מספק חסם על שינוי הערכים העצמיים. בדומה לניסוח תנאי משפט דייוויס-קהאן, יהיו <math>A,A+H</math> מטריצות הרמיטיות ממימד n. נסמן <math>\lambda_i(A)</math> בתור הערך העצמי ה-i של <math>A</math> (כאשר הערכים העצמיים בסדר יורד, ניתן לעשות זאת כי המטריצה הרמיטית). אי שוויון וויל אומר כי:
<center><math>\lambda_{i+j-1}(A+H) \le \lambda_i(A) + \lambda_j(H) \le \lambda_{i+j-n}(A+H)</math></center>
== רעיונות מרכזיים בהוכחה ==
נתבסס על ההוכחה של המשפט במאמר של דייוויס וקהאן.<ref name="DavisKahan1970" /> תחילה, נשתמש בטענת עזר - תהי נורמה נשמרת אוניטרית ויהיו <math>\alpha\ge 0, \delta>0</math> ויהיו שני אופרטורים שמקיימים <math>\Vert A^{-1} \Vert\le (\alpha+\delta)^{-1}</math> וגם <math>\Vert B \Vert\le \alpha</math> ויהי אופרטור <math>X</math> אזי האופרטור:
<center><math>C=AX-XB</math></center>
מקיים <math>\Vert C \Vert\le \delta \Vert X \Vert</math>.

הוכחת טענת העזר: מתת-כפליות של נורמה נשמרת אוניטרית, <math>\Vert XB \Vert \le \alpha \Vert X \Vert</math> וגם <math>\Vert AX \Vert \ge (\alpha+\delta) \Vert X \Vert</math> ומ[[אי-שוויון המשולש]]:
<center><math>\Vert C \Vert \ge \Vert AX \Vert - \Vert XB \Vert \ge \delta \Vert X \Vert </math></center>

כנדרש.

כעת נכתוב בצורה יותר מפורשת את המטריצות:
<center>
<math>
A+H = \begin{pmatrix}\ E_0 & E_1 \end{pmatrix}
\begin{pmatrix}
\Lambda_0 + H_0 & B^* \\
B & \Lambda_1 + H_1
\end{pmatrix}
\begin{pmatrix}
\ E_0^* \\
 \ E_1^*
\end{pmatrix} =
\begin{pmatrix}\ F_0 & F_1 \end{pmatrix}
\begin{pmatrix}
\Mu_0 & 0 \\
0 & \Mu_1
\end{pmatrix}
\begin{pmatrix}
\ F_0^* \\
 \ F_1^*
\end{pmatrix}
</math>
</center>

מהכתיבה המפורשת של המטריצות ניתן להסיק <math>AE_0 = E_0\Lambda_0</math>. לכן:
<center><math> R=HE_0=(A+H)E_0-E_0\Lambda_0 </math></center>
כעת, מפני שנורמת האופרטור <math>F_1</math> חסומה על ידי <math>1</math>, מתת-כפליות <math>\Vert R \Vert = \Vert R^* \Vert
 \ge \Vert R^* F_1 \Vert </math>. נקבל:
<center><math> R^*F_1 = E_0^*F_1\Mu_1 - \Lambda_0E_0^*F_1 </math></center>
נוסיף לאופרטור <math>A</math> כפולה של [[מטריצת היחידה]] (ניתן לעשות זאת מכיוון שזה לא משנה את המרחבים העצמיים) כך שנקבל <math>0\le \alpha = - \beta</math>. בצורה הזו מהנתון בתנאי המשפט על ההפרש בספקטרום, נוכל להשתמש בטענת העזר:
<center><math> \Vert R^*F_1 \Vert \ge \delta \Vert E_0^*F_1 \Vert </math></center>
לבסוף, ניתן להראות שלאופרטור <math>E_0^*F_1</math> יש אותם ערכים סינגולריים כמו ל-<math>\sin(\Theta)</math>, ומפני שנורמה נשמרת אוניטרית היא פונקציה של הערכים הסינגולריים של האופרטור, מתקיים:
<center><math> \Vert R \Vert \ge \delta \Vert E_0^*F_1 \Vert = \delta \Vert \sin(\Theta) \Vert </math></center>

== היסטוריה ==
המשפט של דייוויס-קהאן נולד מתוך התפתחות תורת ההפרעות של מטריצות, תחום שקיבל תשומת לב רבה במאה ה-20. בעבודות מוקדמות, כמו הספר של [[טוסיו קאטו]]{{אנ|Tosio Kato}} - "תורת ההפרעות לאופרטורים ליניאריים" משנת 1966, נדרשה רמת דיוק גבוהה יותר בניתוח מטריצות, דבר שהשפיע על התחום המתמטי והרחיב את הידע בהקשר של ניתוח [[ספקטרום (מתמטיקה)|ספקטרלי]].<ref>{{Cite book|last=Kato|first=Tosio|title=Perturbation Theory for Linear Operators|year=1966|publisher=Springer-Verlag|location=Berlin}}</ref> במקביל, [[אנליזה נומרית|אנליסטים נומריים]] תרמו להבנת יציבות ערכים עצמיים ותתי מרחבים עצמיים של מטריצות מופרעות, ובמיוחד דרך עבודותיהם של [[ג'יימס הארדי וילקינסון]]{{אנ|James H. Wilkinson}} ואחרים.

בשנת 1970 יצא משפט דייוויס-קהאן שהפך לכלי מרכזי בהבנת רגישותם של תתי מרחבים ספקטרליים להפרעות, בכך שהציע גבול ברור על הזווית בין מרחבים עצמיים של מטריצה ומטריצה מופרעת. תוצאה זו הייתה חשובה במיוחד לאנליסטים נומריים, והיא הובילה לפיתוחים נוספים בתחום. בשנת 1972, תוצאות אלו הורחבו על ידי וודין למטריצות לא הרמיטיות, מה שאִפשר את יישום התיאוריה גם במקרים של מטריצות מלבניות כלליות.<ref name="Wedin1972" /> במאמר מ-2015 של יו טנגיאו וואנג וריצ'רד סאמוורת' הותאמה תוצאת דייוויס-קאהן להקשרים סטטיסטיים, עם תנאי הפרדה מקלים בין ערכים עצמיים של אוכלוסייה ומדגם, מה שהרחיב את השימוש בה ואפשר גישה ליישומים מעשיים.<ref name="Yu2015" /> בשנת 2018, שיפרו [[ג'סטין אלדרידג'|אלדרידג']], [[מישה בלקין|בלקין]] ו-[[יוסו וואנג|וואנג]] את חסמי ההפרעה הקלאסיים על ידי התחשבות ברעש אקראי. הם הציעו חסמים מדויקים יותר להפרעות בערכים עצמיים ובווקטורים עצמיים, והתוצאות עלו בביצועיהן על אלו של משפטים מסורתיים כמו משפט וייל ברבים מהמקרים המעשיים.<ref>{{Cite conference |last1=Eldridge |first1=Justin |last2=Belkin |first2=Mikhail |last3=Wang |first3=Yusu |title=Unperturbed: spectral analysis beyond Davis-Kahan |conference=Proceedings of the 29th Conference on Learning Theory |editor1-last=Mohri |editor1-first=Mehryar |editor2-last=Sridharan |editor2-first=Karthik |year=2016 |location=New York, NY, USA |pages=1497–1561 |publisher=PMLR |url=https://proceedings.mlr.press/v49/eldridge16.pdf |access-date=2024-10-06}}</ref> חשוב לציין שרשימת הפיתוחים הנ"ל אינה ממצה את מה שקיים בספרות המתמטית.

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

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

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

== דוגמאות לשימושים ==
=== מודל Spiked Covariance ===
{{הפניה לערך מורחב|ערך=[[מודל Spiked Covariance]]}}
מודל זה עוסק באומדן וקטור עצמי מוביל של מטריצת שונות משותפת מדגמית. במצבים בהם הווקטור העצמי המוביל בולט בצורה משמעותית על פני וקטורים אחרים, באמצעות משפט דייוויס-קהאן ניתן להעריך את מידת הקרבה בין הווקטור העצמי האמיתי לבין זה שנאמד על בסיס דגימות אקראיות. באופן פורמלי, יהיו <math>X_1,...,X_n \overset{i.i.d}{\sim}(0,\Sigma)</math> וקטורים אקראיים ב - <math>\mathbb{R}^d</math>. נניח שמטריצת השונות המשותפת, <math>\Sigma</math> היא <math>\Sigma = \theta vv^T + I_d</math> עבור <math>\theta>0</math> ו - <math>v\in\mathbb{R}^d</math> וקטור בגודל יחידה (<math>\Vert v \Vert=1</math>). מההגדרה הנ"ל, הערך העצמי הגדול ביותר של מטריצה <math>\Sigma</math> הוא <math>1+\theta</math> עם וקטור עצמי מתאים <math>v</math>. אנחנו מעוניינים להסיק מהו <math>v</math> על סמך דגימות. תהי <math>\Sigma_n = \frac{1}{n}\sum_{i=1}^n X_i X_i^T</math> ויהי <math>v_n</math> הווקטור העצמי (בגודל יחידה) המוביל של <math>\Sigma_n</math> נשתמש בחישוב הבא:

<center><math>\Vert v_n - v\Vert^2 = \langle v_n - v, v_n - v\rangle = \Vert v_n \Vert^2+\Vert v \Vert^2 - \langle v_n, v\rangle - \langle v, v_n\rangle = 2-2|v^Tv_n|</math></center>

כעת, מ[[אי-שוויון קושי-שוורץ|אי שוויון קושי שוורץ]], <math>|v^Tv_n|\le \Vert v_n\Vert\cdot\Vert v\Vert = 1</math> לכן:

<center>
<math>
2 - 2|v^Tv_n| \le 2 - 2|v^Tv_n|^2 = 2 - 2\cdot \frac{|v^Tv_n|^2}{(\Vert v_n\Vert\Vert v\Vert)^2} = 2 - 2\cos^2(\angle(v,v_n)) = 2\sin^2(\angle(v,v_n))
</math>
</center>

מפני שההפרש בין הערך העצמי המוביל לכל הבאים הוא <math>\theta</math>, נשתמש ב (הרחבה לסטטיסטיקאים של) משפט דייוויס-קהאן ונקבל:
<center><math>\Vert v_n - v\Vert^2 \le 8 \frac{\Vert \Sigma_n - \Sigma\Vert_F^2}{\theta^2}</math></center>

תחת הנחות נוספות ניתן לקבל חסם על <math>\Vert \Sigma_n - \Sigma\Vert_F</math> והערכה על קצב הדעיכה של <math>\Vert v_n - v\Vert</math>.<ref name="RinaldoTomaselli">{{Cite book |last1=Rinaldo |first1=Alessandro |url=https://www.stat.cmu.edu/~arinaldo/Teaching/36709/LectureNotes/lecture23.pdf |title=36-709: Advanced Statistical Theory I, Lecture 23 |last2=Tomaselli |first2=Lorenzo |date=2019-04-16 |publisher=Carnegie Mellon University |location=Pittsburgh, PA |access-date=2024-10-06}}</ref>

=== מודל בלוקים סטוכסטי ===
{{הפניה לערך מורחב|ערך=[[מודל בלוקים סטוכסטי]]}}
נראה שימוש למקרה פרטי של מודל בלוקים סטוכסטי. יהי [[גרף (תורת הגרפים)|גרף]] שקבוצת הקודקודים בו מחולקת לשתי קהילות שבה כל זוג נקודות בתוך הקהילה מחוברות זו לזו בהסתברות <math>p</math> וכל זוג נקודות בקהילות שונות מחוברות זו לזה בהסתברות <math>q</math>. [[מטריצת שכנות|מטריצת השכנויות]] של הגרף מוגדרת באופן הסתברותי כך ש-<math>A_{i,j}</math> [[התפלגות ברנולי|מתפלג ברנולי]] בהסתברות <math>p</math> אם <math>i,j</math> באותה קהילה ומתפלג ברנולי בהסתברות <math>q</math> אם הם בקהילות שונות. נשים לב לכך שה[[תוחלת]] של המטריצה <math>A</math> היא:
<center>
<math>
\ P = \mathbb{E}(A) =
\begin{bmatrix}
p & p & \cdots & q & q & \cdots \\
p & p & \cdots & q & q & \cdots \\
\vdots & \vdots & \ddots & \vdots & \vdots & \cdots \\
q & q & \cdots & p & p & \cdots \\
q & q & \cdots & p & p & \cdots \\
\vdots & \vdots & \cdots & \vdots & \vdots & \ddots
\end{bmatrix}
</math>
</center>

משמע <math>\mathbb{E}(A)_{i,j}</math> [[מטריצת בלוקים]] שכל אחד מארבעת הבלוקים מטריצה שמקבלת רק הערך <math>p</math> או <math>q</math> בהתאמה. אפשר להראות שה[[דרגה (אלגברה ליניארית)|דרגה]] של <math>P</math> היא <math>2</math>, שהערך העצמי המוביל הוא <math> \lambda_1 = (\frac{p+q}{2})n</math> והווקטור העצמי המתאים לו הוא:
<center>
<math>
u_1(P) = \frac{1}{\sqrt{n}}
\begin{bmatrix}
1 \\
1 \\
\vdots \\
1 \\
1
\end{bmatrix}
</math>
</center>

הערך העצמי השני הוא <math> \lambda_1 = (\frac{p-q}{2})n</math> והווקטור העצמי המתאים לו:
<center>
<math>
u_2(P) = \frac{1}{\sqrt{n}}
\begin{bmatrix}
1 \\
\vdots \\
1 \\
-1 \\
\vdots \\
-1
\end{bmatrix}
</math>
</center>

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

תהי <math>E</math> מטריצה ממשית מסדר <math>n\times n</math> עם איברים <math>e_{ij}</math> שכל אחד [[משתנה מקרי]] בעל תוחלת <math>0</math> ו[[התפלגות תת-גאוסית|מתפלג תת-גאוסית]] עם נורמת תת-גאוסית <math>k</math>. לכל <math>t>0</math> קיים <math>C</math> קבוע כך שאי השוויון הבא מתקיים:<ref>{{Cite book|last=Vershynin|first=Roman|url=https://www.math.uci.edu/~rvershyn/|title=High-Dimensional Probability: An Introduction with Applications in Data Science|date=2024-05-20|publisher=University of California, Irvine|location=Theorem 4.4.5 (Norm of matrices with sub-gaussian entries)|access-date=2024-10-06}}</ref>
<center><math>\mathbb{P}(\Vert E \Vert \le Ck(\sqrt{n}+ t))\ge 1-e^{-t^2} </math></center>
מכאן, מפני שהמטריצה נגדיר מטריצה חדשה <math>E=A-P</math> מקיימת את תנאי המשפט, בהסתברות גבוהה מתקיים:
<center><math>\Vert E\Vert _{op} \le C\cdot \sqrt{n}</math></center>

בנוסף, ההפרש בין הערך העצמי השני לערכים העצמיים הקרובים אליו (הראשון והשלישי) של <math>P</math> הוא:
<center><math>\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})</math></center>

מכאן, בשימוש בהרחבה של משפט דייוויס-קהאן לסטטיסטיקאים, נקבל בהסתברות גבוהה שקיים <math>\epsilon\in\{-1,1\}</math> עבורו הווקטור העצמי השני מקיים:
<center>
<math>
 \ \Vert u_2(A) - \epsilon u_2(P)\ \Vert
\leq \frac{2^{3/2}\Vert E\Vert _{op}}{\delta} \le \frac{2C}{\min(q,\frac{p-q}{2})\sqrt{n}}
</math>
</center>

ניתן להראות שמספר האינדקסים בהם הסימן של <math>\epsilon u_2(P)_i</math> שונה מזה של <math>u_2(A)_i</math> שואף ל-<math>0</math> כאשר <math>n</math> שואף לאינסוף. לכן, עבור <math>n</math> מספיק גדול, בהסתברות גבוהה מספר טעויות הסיווג יהיה קטן.<ref name="RinaldoTomaselli" />

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

==הערות שוליים==
{{הערות שוליים|יישור=שמאל}}

[[קטגוריה:אלגברה ליניארית]]