פירוק SVD והפירוק הפולארי של מטריצות

מבוא

בפוסט הזה אני רוצה לדבר על פירוק SVD, שהוא תוצאה מרהיבה באלגברה לינארית שבמובן מאוד מסויים מכלילה תוצאה מרהיבה אחרת של האלגברה הלינארית שעליה כתבתי ממש לא מזמן: לכסון אוניטרי. אמרנו שמטריצה \( A \) ניתנת ללכסון אוניטרי אם אפשר לכתוב \( A=UDU^{*} \) כאשר \( U \) היא מטריצה אוניטרית ואילו \( D \) היא מטריצה אלכסונית. המשפט שהוכחנו אמר ש:

• מעל \( \mathbb{R} \), \( A \) היא לכסינה אוניטרית אם ורק אם \( A=A^{*} \) ("A צמודה לעצמה").
• מעל \( \mathbb{C} \), \( A \) היא לכסינה אוניטרית אם ורק אם \( A^{*}A=AA^{*} \) ("A נורמלית").

אפשר לחשוב על לכסון אוניטרי גם בצורה שונה: מטריצה אוניטרית \( U \) מסדר \( n\times n \) מעל \( \mathbb{F} \) היא בעצם אוסף \( \left\{ u_{1},\ldots,u_{n}\right\} \) של וקטורים ב-\( \mathbb{F}^{n} \): כל עמודה שלה היא וקטור שכזה. דרישת האוניטריות שקולה לכך שהוקטורים הללו יהיו בסיס אורתונורמלי, כלומר וקטורים בלתי תלויים המקיימים \( \left\langle u_{i},u_{j}\right\rangle =\delta_{ij} \) כאשר המכפלה הפנימית היא המכפלה הסטנדרטית מעל \( \mathbb{F} \). כדי לראות שזה עובד פשוט נסתכל על השוויון \( U^{*}U=I \) שמגדיר אוניטריות: באופן כללי, כאשר כופלים שתי מטריצות \( A,B \) אז הכניסה ה-\( ij \) במכפלה שווה לשורה ה-\( i \) של \( A \) שמוכפלת סקלרית בעמודה ה-\( j \) של \( B \); במכפלה \( U^{*}U \), השורה ה-\( i \) של \( U^{*} \) היא בעצם העמודה ה-\( i \) של \( U \), אחרי שביצענו לאבריה הצמדה. המכפלה הפנימית הסטנדרטית מעל \( \mathbb{F} \) היא בדיוק “בצעו הצמדה לאחד הוקטורים ואז כפלו אותם סקלרית”, מה שנותן לנו את המעבר החלק מלשון מטריצות ללשון וקטורים. בנוסף, העמודות של \( U \) הן בלתי תלויות לינארית כי \( U \) היא מטריצה הפיכה - כל זה חומר סטנדרטי של אלגברה לינארית שאני לא אוכיח שוב.

את השוויון \( A=UDU^{*} \) אפשר להבין גם כן בלשון וקטורית. בואו נסמן

\( D=\left(\begin{array}{cccc} \lambda_{1}\\ & \lambda_{2}\\ & & \ddots\\ & & & \lambda_{n} \end{array}\right) \)

כלומר \( D \) היא מטריצה אלכסונית עם הערכים \( \lambda_{1},\ldots,\lambda_{n} \). עכשיו, ניקח את \( A=UDU^{*} \), נכפול מימין ב-\( U \) ונקבל

\( AU=UD \)

מה קורה פה? אמרתי שהכניסה ה-\( ij \) של \( AU \) היא מכפלת השורה ה-\( i \) של \( A \) בעמודה ה-\( j \) של \( U \); אם נסתכל על כל העמודה ה-\( j \) של \( AU \) (כלומר, על הכניסות \( 1j,2j,\ldots,nj \)) אז יוצא שהעמודה הזו שווה למכפלה של \( A \) בוקטור העמודה ה-\( j \)-י של \( U \). סימנו את הוקטור הזה כזכור ב-\( u_{j} \) אז אפשר לסכם שהעמודה ה-\( j \) של \( AU \) היא פשוט \( Au_{j} \).

עכשיו, מה זו \( UD \)? הכניסה ה-\( ij \) של \( UD \) שווה למכפלת השורה ה-\( i \) של \( U \) בעמודה ה-\( j \) של \( D \). בעמודה ה-\( j \) של \( D \) יש רק איבר אחד שאולי שונה מאפס: \( \lambda_{j} \), שנמצא בשורה ה-\( j \) של העמודה. אז מכל השורה ה-\( i \)-ית של \( U \), הולך להישאר רק האיבר במקום \( ij \), והוא יוכפל ב-\( \lambda_{j} \). במילים אחרות: העמודות של \( UD \) הן בדיוק העמודות של \( U \), רק שבנוסף העמודה ה-\( j \) של \( U \) מוכפלת ב-\( \lambda_{j} \), כלומר היא שווה ל-\( \lambda_{j}u_{j} \).

השוויון \( AU=UD \) אומר לנו, אם כן, ש-\( Au_{j}=\lambda_{j}u_{j} \), כלומר ש-\( u_{j} \) הוא וקטור עצמי של \( A \) עם ערך עצמי \( \lambda_{j} \). זה מוביל לניסוח שקול של מה זה לכסון אוניטרי: שיהיה לנו בסיס אורתונורמלי למרחב שמורכב כולו מוקטורים עצמיים של \( A \). לבסוף, אם לוקחים טרנספורמציה לינארית כללית \( T:V\to V \) עבור מרחב סוף-ממדי \( V \) מעל \( \mathbb{R} \) או \( \mathbb{C} \) אז אפשר לקחת בסיס אורתונורמלי למרחב הזה (תהליך גרם-שמידט מבטיח שקיים כזה), ולהשתמש בבסיס הזה כדי לעבור לדבר על \( \mathbb{F}^{n} \) ולקבל את כל המושגים שדיברנו עליהם כאן גם בהקשר של טרנספורמציות כלליות. מכיוון שאני מניח שהטריק הזה מוכר, בפוסט הזה אני לא ממש אדבר עליו - לכאורה נדבר רק על המקרה הקונקרטי של \( \mathbb{F}^{n} \) ושל מטריצות, אבל ברקע הדברים צריך לזכור שזה פשוט התכל’ס הטכני של תוצאה שתקפה לכל מרחב מכפלה פנימית סוף-ממדי.

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

מה זה פירוק SVD?

לכסון אוניטרי זה משהו שקיים לחלק מהמטריצות הריבועיות. לעומתו, פירוק SVD (ראשי תיבות של Singular Value Decomposition, “פירוק ערכים סינגולריים” ואוטוטו נראה מהם הערכים הללו) זה משהו שקיים לכל מטריצה \( A\in M_{n,m}\left(\mathbb{F}\right) \) מעל \( \mathbb{F} \) שהוא הממשיים או המרוכבים (בדרך כלל לא אטרח לכתוב אותו), גם אם \( A \) היא בכלל לא ריבועית. זה הפירוק הבא:

\( A=U\Sigma V^{*} \)

כאשר \( U\in M_{n,n} \) ו-\( V\in M_{m,m} \) הן מטריצות אוניטריות ואילו \( \Sigma\in M_{n,m} \) (כלומר, מטריצה לא בהכרח ריבועית, מאותו סדר כמו \( A \)) היא “אלכסונית” במובן זה שהערכים היחידים שלה שעשויים להיות שונים מאפס הם הערכים מהצורה \( \Sigma_{ii} \) (עבור \( 1\le i\le\min\left\{ n,m\right\} \)). יותר מזה: אם נסמן את הערכים על האלכסון הזה ב-\( \sigma_{1},\sigma_{2},\ldots,\sigma_{k} \) אז כולם מספרים ממשיים, ומתקיים \( \sigma_{1}\ge\sigma_{2}\ge\ldots\ge\sigma_{k}\ge0 \). כלומר, בניגוד ללכסון אוניטרי שבו היה “חופש בחירה” עבור \( D \) איך הערכים העצמיים יהיו מסודרים בה, כאן יש הצגה קנונית יחידה של המטריצה \( \Sigma \) (אבל לא של \( U,V \)). ויותר מכך: ערכי ה-\( \alpha \) ששונים מאפס הם בדיוק הערכים \( \sigma_{1},\ldots,\sigma_{r} \), כאשר \( r \) היא הדרגה של המטריצה \( A \).

הערכים \( \sigma_{1},\sigma_{2},\ldots,\sigma_{k} \) הללו נקראים הערכים הסינגולריים של \( A \). קל להגיד מה הם: אם נסתכל על \( AA^{*} \) נקבל את מה שקראתי לו בפוסט הקודם מטריצה חיובית (Positive Definite) והערכים העצמיים של המטריצות הללו הם ממשיים אי-שליליים ולכן אפשר להוציא להם שורש ריבועי ולקבל ממשיים אי-שליליים; הערכים הסינגולריים הם בדיוק השורשים הללו.

בואו ננסה להבין את SVD ברמת הוקטורים. אני אסמן את העמודות של \( U \) ב-\( \left\{ u_{1},\ldots,u_{n}\right\} \)ושל \( V \) ב-\( \left\{ v_{1},\ldots,v_{m}\right\} \), אז מכיוון שאלו מטריצות אוניטריות, שני אלו הם בסיסים אורתונורמליים (למרחבים שהם אולי שונים; הראשון ל-\( \mathbb{F}^{n} \) והשני ל-\( \mathbb{F}^{m} \)). עכשיו, נכפול את \( A=U\Sigma V^{*} \) ב-\( V \) מימין ונקבל

\( AV=U\Sigma \)

וכמו שהסברתי במבוא, זה אומר שמתקיים

\( Av_{j}=\sigma_{j}u_{j} \)

זה מאוד מזכיר וקטורים עצמיים, חוץ מהקטע של ה”עצמי”. מכפלה ב-\( A \) מעבירה את \( v_{j} \) אל מכפלה של \( u_{j} \) ב-\( \sigma_{j} \), כלומר אנחנו עוברים מהקבוצה \( \left\{ v_{1},\ldots,v_{m}\right\} \) אל \( \left\{ u_{1},\ldots,u_{n}\right\} \). זה ה”מחיר” שאנחנו משלמים: מצד אחד הפירוק קיים לכל מטריצה, מצד שני אין לנו בסיס אחד לאותו מרחב ש-\( A \) מעבירה אותו לעצמו; יש לנו שני בסיסים למרחבים שונים ש-\( A \) מעבירה אותנו מאחד מהם לשני, אבל עדיין בצורה פשוטה יחסית: היא לא מעבירה איבר בסיס לצירוף לינארי של שני וקטורים או יותר, אלא רק למכפלה בסקלר של וקטור אחד.

מקבלים פירוק שהוא כמעט, אבל לא בדיוק, שונה לגמרי מ-SVD

ההוכחה שפירוק SVD תמיד קיים היא לא מסובכת במיוחד, אבל אני הולך בכוונה לסבך אותה טיפה כי אם מתחילים ממשפט יותר כללי, אפשר לקבל ממנו גם את פירוק SVD אבל גם את הפירוק הפולארי של מטריצות שהזכרתי בפוסט הקודם: שכל מטריצה \( A \) ניתן לכתוב בתור \( A=PU \) כך ש-\( P \) היא מטריצה חיובית ו-\( U \) היא מטריצה אוניטרית. למעשה, גם כאן זה עובד אפילו למטריצות לא ריבועיות: אם \( A\in M_{n,m} \) כך ש-\( n\le m \) (מספר השורות לא גדול ממספר העמודות) אז קיימת \( P\in M_{n,n} \) חיובית מאותה דרגה כמו \( A \), ו-\( U\in M_{n,m} \) כך ש-\( A=PU \), ו-\( U \) היא “אוניטרית” במובן הבא: \( UU^{*}=I_{n\times n} \). כלומר, השורות של \( U \) הן אורתונורמליות.

נראה קשור אל SVD? לא? לי זה בכלל לא נראה קשור ממבט ראשון אבל תוך שניה הכל יתבהר, ולמעשה כבר הזכרתי את טיעון המפתח המרכזי: זה לא משנה איזו מטריצה היא \( A \) - הפיכה, לא הפיכה, ריבועית, לא ריבועית - אני תמיד מקבל ש-\( AA^{*} \) היא מטריצה חיובית, ולכן אפשר לקחת את הערכים העצמיים שלה ולהוציא להם שורש ולקבל את הערכים הסינגולריים. זה האופן שבו מטריצות חיוביות נדחפות לתוך ההוכחה, ואם יש לנו מטריצות חיוביות ומטריצות כמו-אוניטריות, כבר יש לנו את הפירוק הפולארי.

אוקיי, אז מה עושים? עכשיו נעבוד מסודר ומדוקדק. התחלנו עם \( A\in M_{n,m} \) שמקיימת \( n\le m \). ביצענו את הכפל \( AA^{*} \) וקיבלנו מטריצה \( n\times n \) שהיא חיובית, ולכן עם ערכים עצמיים \( \lambda_{1}\ge\lambda_{2}\ge\ldots\ge\lambda_{n}\ge0 \). הערכים העצמיים לאו דווקא שונים זה מזה, אבל שימו לב שכל \( n \) הערכים העצמיים קיימים, וזה כי \( AA^{*} \) היא בפרט מטריצה צמודה לעצמה ולכן לכסינה. מכיוון שכל ערך עצמי הוא ממשי אי שלילי אני יכול להגדיר \( \sigma_{i}=\sqrt{\lambda_{i}} \) ולקבל סדרה חדשה של מספרים ממשיים אי שליליים \( \sigma_{1}\ge\sigma_{2}\ge\ldots\ge\sigma_{n}\ge0 \). המספרים הללו הם מה שנקרא הערכים הסינגולריים של \( A \). לפעמים קוראים “ערכים סינגולריים” רק לאותם \( \sigma_{i} \)-ים שגדולים ממש מאפס; אני לא אעשה את ההפרדה הזו כרגע, אבל אני כן אכניס סימון חדש לתמונה: \( r \) יהיה המספר של הערכים הסינגולריים שגדולים מאפס, כלומר \( \sigma_{1}\ge\ldots\ge\sigma_{r}>0 \) ו-\( \sigma_{r+1}=\ldots=\sigma_{n}=0 \). בהמשך נראה ש-\( r=\text{rank}A \), אבל ההוכחה לא מיידית אז נחכה עם זה קצת.

עכשיו אנחנו יכולים לבנות מטריצה אלכסונית \( n\times n \) עם הערכים הסינגולריים על האלכסון:

\( \Lambda=\left(\begin{array}{cccc} \sigma_{1}\\ & \sigma_{2}\\ & & \ddots\\ & & & \sigma_{n} \end{array}\right) \)

עכשיו, \( AA^{*} \) לא סתם לכסינה אלא לכסינה אוניטרית, כלומר יש לנו בסיס של וקטורים עצמיים אורתונורמליים \( x_{1},\ldots,x_{n} \) שאפשר לסדר יפה בתור עמודות ולקבל מטריצה אוניטרית \( X\in M_{n,n} \). אני רוצה למצוא פירוק של \( A \) שהוא מהצורה \( A=X\Lambda Y \), אבל מהי \( Y \) הזו? ראשית, \( X\Lambda\in M_{n,n} \) ולכן צריך שיתקיים \( Y\in M_{n,m} \) כדי שכפל המטריצות יהיה מוגדר ונקבל ממנו מטריצה מאותם ממדים כמו \( A \). אבל חוץ מזה, מה אנחנו יודעים עליה? אם \( \Lambda \) היא הפיכה אז הסיטואציה פשוטה: \( Y=\Lambda^{-1}X^{*}A \), אבל זה עובד רק אם \( \Lambda \) הפיכה, כלומר אם כל הערכים העצמיים גדולים מאפס (כלומר אם \( r=n \)). אחרת? המצב קצת מסובך יותר אבל עדיין אפשר לבנות \( Y \) מתאימה. בשביל לעשות את זה, אני קודם אניח ש-\( \Lambda \) כן הפיכה ואראה מה אני יכול להגיד על המבנה של \( Y \):

יהיה לי קצת יותר נוח לבנות את \( Y^{*} \) ולקבל ממנו את \( Y \), אז נתחיל עם לחשב

\( Y^{*}=\left(\Lambda^{-1}X^{*}A\right)^{*}=A^{*}X\Lambda^{-1} \)

כשאני משתמש כאן בכך ש-\( \Lambda^{-1} \) היא מטריצה ממשית אלכסונית ולכן \( \left(\Lambda^{-1}\right)^{*}=\Lambda^{-1} \).

עכשיו, באופן כללי כשיש לנו מכפלת מטריצות \( AB \) אפשר לחשוב על העמודה ה-\( i \) של המכפלה בתור \( Ab_{i} \), כלומר המכפלה של כל \( A \) בעמודה ה-\( i \) של \( B \). זה אומר שהעמודה ה-\( i \) של \( A^{*}X \) היא פשוט \( A^{*}x_{i} \). עכשיו, עוד דרך לחשוב על העמודות של המכפלה \( AB \) היא שהעמודה ה-\( i \) במכפלה היא צירוף לינארי של העמודות של \( A \) עם המקדמים שנמצאים בעמודה ה-\( i \) של \( B \). כך שאם \( B \) היא אלכסונית עם הערך \( b_{ii} \) על האלכסון, אז העמודה ה-\( i \) של \( AB \) תכיל את העמודה ה-\( i \)של \( A \) כשהיא מוכפלת ב-\( \lambda_{ii} \) ותו לא. במקרה שלנו זה אומר שהעמודה ה-\( i \) של \( A^{*}X\Lambda^{-1} \) תהיה \( \sigma_{i}^{-1}A^{*}x_{i} \). לכן, במטריצה \( Y \) שאנחנו בונים, השורה ה-\( i \) תהיה הוקטור \( y_{i}=\left(\sigma_{i}^{-1}A^{*}x_{i}\right)^{*}=\sigma_{i}^{-1}x_{i}^{*}A \). כל זה נכון במקרה שבו \( \Lambda \) הפיכה, אבל גם אם לא - אנחנו יכולים להשתמש בו כדי להגדיר את השורות של \( Y \), כל עוד \( \sigma_{i}\ne0 \), כלומר עבור הערכים הסינגולריים שסימנתי ב-\( \sigma_{1},\ldots,\sigma_{r} \).קיבלנו את השורות \( y_{1},\ldots,y_{r} \), כלומר \( r \) השורות הראשונות במטריצה \( Y \) שאמורה לכלול סך הכל \( n \) שורות שכל אחד מהן היא באורך \( m \) (כי היא מסדר \( n\times m \)).

ה-\( y_{i} \)-ים הללו מקיימים תכונה מהותית אחת - גם הם אורתונורמליים. כדי לראות את זה, בואו נכפול אותם פנימית. אם \( x,y \) הם שני וקטורים ב-\( \mathbb{F}^{n} \), המכפלה הפנימית הסטנדרטית שלהם היא \( \left\langle x,y\right\rangle =y^{*}x \), אבל זה נכון לוקטורי עמודה. אם יש לנו וקטורי שורה, להסתכל על \( xy^{*} \) ישיג את אותו אפקט (מצמיד את אברי \( y \) ומסדר את הממדים כך שכפל שני הוקטורים יניב סקלר). לכן

\( \left\langle y_{i},y_{j}\right\rangle =\left(\sigma_{i}^{-1}x_{i}^{*}A\right)\left(\sigma_{j}^{-1}x_{j}^{*}A\right)^{*}=\left(\sigma_{i}\sigma_{j}\right)^{-1}x_{i}^{*}AA^{*}x_{j} \)

עכשיו, כזכור \( x_{j} \) הוא וקטור עצמי של \( AA^{*} \) עם ערך עצמי \( \lambda_{j}=\sigma_{j}^{2} \) כך שקיבלנו

\( \left(\sigma_{i}\sigma_{j}\right)^{-1}x_{i}^{*}AA^{*}x_{j}=\left(\sigma_{i}\sigma_{j}\right)^{-1}\sigma_{j}^{2}x_{i}^{*}x_{j}=\frac{\sigma_{j}}{\sigma_{i}}\left\langle x_{j},x_{i}\right\rangle =\frac{\sigma_{j}}{\sigma_{i}}\delta_{ij}=\delta_{ij} \)

המעבר האחרון נובע מכך שאם \( i\ne j \) אז \( \frac{\sigma_{j}}{\sigma_{i}}\delta_{ij}=0 \) ואילו אם \( \delta_{ij}=1 \) אז ברכיב \( \frac{\sigma_{j}}{\sigma_{i}} \) יש לנו את אותו איבר ולכן הוא מתבטל.

עכשיו, אם יש לנו קבוצה \( \left\{ y_{1},\ldots,y_{r}\right\} \) של וקטורים אורתונורמליים בלתי תלויים במרחב \( \mathbb{F}_{m} \), כאשר \( r\le n\le m \), אז אפשר להרחיב אותה לקבוצה \( \left\{ y_{1},\ldots,y_{r},y_{r+1},\ldots,y_{n}\right\} \) של וקטורים אורתונורמליים בלתי תלויים בשיטות הסטנדרטיות של השלמה לבסיס וביצוע גרם-שמידט (רק שכאן אנחנו לא צריכים להגיע ל-\( m \) וקטורים אלא יכולים להסתפק ב-\( n \) כאלו). שימו לב שההרחבה הזו לא נקבעת בצורה יחידה, אז זו כבר הנקודה השניה שבה משהו לא נקבע באופן יחיד: גם \( X \) לא נקבעה באופן יחיד, ועכשיו אנחנו רואים שאם לא כל הערכים הסינגולריים שונים מאפס אז גם \( Y \) לא נקבעת באופן יחיד בהינתן \( X \).

קיבלנו מטריצה \( Y \), אבל צריך להראות ש-\( A=X\Lambda Y \), או באופן שקול ש-\( X^{*}A=\Lambda Y \). אפשר להראות ששתי המטריצות הללו שוות, שורה-שורה. עבור \( r \) השורות הראשונות, השורות של \( Y \) הן מהצורה

\( y_{i}=\sigma_{i}^{-1}x_{i}^{*}A \)

ולכן השורות של \( \Lambda Y \) הן מהצורה \( x_{i}^{*}A \), וזו בדיוק הצורה של שורה של \( X^{*}A \) (שני אלו מאותם שיקולים על איך נראות העמודות של מכפלה שהזכרתי קודם, רק כשמפעילים אותם על שורות בתיקונים המתאימים).

עבור שורה \( y_{k} \) שהיא מעבר ל-\( r \) הראשונות, הסקלר המתאים ב-\( \Lambda \) שבו כופלים את השורה ה-\( k \) הוא \( \sigma_{k}=0 \), ולכן מקבלים ב\( \Lambda Y \)- את שורת האפס. מצד שני, השורה המתאימה בצד שמאל היא \( x_{k}^{*}A \). אל מה היא שווה? ובכן, מכיוון שהערך הסינגולרי \( \sigma_{k}=0 \) אז גם \( \lambda_{k}=0 \), כלומר \( \left(AA^{*}\right)x_{k}=\lambda_{k}x_{k}=0 \).

עכשיו אפשר להשתמש בטריק. נכפול את \( \left(AA^{*}\right)x_{k} \) משמאל ב-\( x_{k}^{*} \). מכיוון ש-\( \left(AA^{*}\right)x_{k} \) הוא וקטור האפס, אחרי הכפל ב-\( x_{k}^{*} \) נקבל את סקלר האפס. מצד שני, אפשר להשתמש בפלא של האסוציאטיביות של כפל מטריצות כדי להפוך את המכפלה הזו למכפלה פנימית:

\( 0=x_{k}^{*}\left(AA^{*}\right)x_{k}=\left(x_{k}^{*}A\right)\left(A^{*}x_{k}\right)=\left(A^{*}x_{k}\right)^{*}\left(A^{*}x_{k}\right)=\left\langle A^{*}x_{k},A^{*}x_{k}\right\rangle \)

ולהשתמש בכך שמכפלה פנימית היא חיובית, כך שמכפלה פנימית של איבר בעצמו יצאה 0, האיבר הוא 0, כלומר \( A^{*}x_{k}=0 \), ולכן גם \( 0=\left(A^{*}x_{k}\right)^{*}=x_{k}^{*}A \), כמו שרצינו להראות. זה מסיים את ההוכחה.

בואו נציין שוב במפורש את מה שמצאנו: לכל מטריצה \( A \), תהא אשר תהא (חוץ מההנחה שמספר השורות בה לא גדול ממספר העמודות) קיים פירוק \( A=X\Lambda Y \) כך ש-\( \Lambda \) היא המטריצה האלכסונית של הערכים הסינגולריים של \( A \), \( X \) היא מטריצה אוניטרית, ואילו \( Y \) היא מטריצה בעלת שורות אורתונורמליות.

נקודה אחת שעוד לא ראינו היא ש-\( \Lambda \) נקבעת בצורה יחידה, במובן הבא: אם \( \Lambda \) היא מטריצה אלכסונית כלשהי מסדר \( n\times n \) שהכניסות על האלכסון שלה הן \( \tau_{1}\ge\tau_{2}\ge\ldots\ge\tau_{n} \) ויש פירוק \( A=X\Lambda Y \) עם תכונות האורתונורמליות של \( X,Y \) שציינתי קודם, אז \( \tau_{i}=\sigma_{i} \), כלומר \( \Lambda \) היא המטריצה של הערכים הסינגולריים. אין פירוק אחר שבו באמצע יש מטריצה עם ערכים ממשיים שמסודרים בסדר יורד. כדי לראות את זה, נניח ש-\( A=X\Lambda Y \) ונחשב את \( AA^{*} \):

\( AA^{*}=\left(X\Lambda Y\right)\left(X\Lambda Y\right)^{*}=X\Lambda YY^{*}\Lambda X^{*}=X\Lambda^{2}X^{*} \)

כאן השתמשנו בכך ש-\( YY^{*}=I \) בזכות האורתונורמליות של שורות \( Y \).

עכשיו, מכיוון ש-\( X \) היא מטריצה אוניטרית, המשוואה \( AA^{*}=X\Lambda^{2}X^{*} \) אומרת ש-\( \Lambda^{2} \) היא מה שמתקבל מלכסון אוניטרי של \( AA^{*} \), כלומר הכניסות של \( \Lambda^{2} \) הן הערכים העצמיים של \( AA^{*} \): \( \tau_{i}^{2}=\lambda_{i}=\sigma_{i}^{2} \), ומכיוון שגם \( \sigma_{i} \) וגם \( \tau_{i} \) הם ממשיים אי שליליים, אפשר להוציא שורש ולקבל \( \tau_{i}=\sigma_{i} \).

מקבלים את הפירוק הפולארי ואת פירוק SVD

המטרה של הפוסט היא להראות איך מקבלים את פירוק SVD אבל עם מה שכבר ראינו כל כך קל לקבל את הפירוק הפולארי שיהיה מגוחך להתעלם מזה. אנחנו לוקחים מטריצה \( A \) כלשהי מסדר \( n\times m \) כך ש-\( n\le m \) ועל פי מה שכבר ראינו, מקבלים עבורה פירוק

\( A=X\Lambda Y \)

עכשיו נשתמש בטריק הכי עתיק בספר - נתקע באמצע הביטוי את \( X^{*}X \) ששווה למטריצת היחידה, ונשתמש באסוציאטיביות. נקבל:

\( A=\left(X\Lambda X^{*}\right)\left(XY\right) \)

נסמן \( P=X\Lambda X^{*} \) ו-\( U=XY \) וקיבלנו פירוק \( A=PU \). עכשיו, מה אמרתי על הפירוק הזה קודם? שקיימת \( P\in M_{n,n} \) חיובית מאותה דרגה כמו \( A \), ו-\( U\in M_{n,m} \) כך ש-\( A=PU \), ו-\( U \) היא “אוניטרית” במובן הבא: \( UU^{*}=I_{m\times m} \). כלומר, השורות של \( U \) הן אורתונורמליות. האם שני אלו נכונים?

ראשית, הממדים מתאימים: \( X\Lambda X^{*} \) היא באמת מסדר \( n\times n \), ואילו \( XY \) היא מסדר \( n\times m \). שנית,

\( UU^{*}=XYY^{*}X^{*}=XIX^{*}=XX^{*}=I \)

מה שמשאיר רק להבין למה \( P \) היא חיובית - אבל אנחנו יודעים שמטריצה היא חיובית אם ורק אם הערכים העצמיים שלה הם ממשיים אי שליליים, ו-\( X\Lambda X^{*} \) הוא לכסון אוניטרי, הערכים העצמיים כבר כתובים במפורש ב-\( \Lambda \) והם כולם ממשיים אי שליליים. זה מסיים את ההוכחה - אמרתי שזה יהיה פשוט!

עוד דבר שקל יחסית לראות הוא מתי הפירוק הפולארי הוא יחיד. ראשית, מה זו \( P \)? אנחנו יודעים ש-\( P^{2}=\left(X\Lambda X^{*}\right)\left(X\Lambda X^{*}\right)=X\Lambda^{2}X^{*} \). אבל מי אלו \( X,\Lambda \)? הן לא מטריצות שבאו משום מקום, הן הגיעו מכך שמצאנו לכסון אוניטרי של \( AA^{*} \), ובלכסון האוניטרי הזה \( AA^{*} \) הייתה דומה למטריצה \( \Lambda^{2} \) והמטריצה המלכסנת הייתה \( X \). במילים אחרות, \( P^{2}=AA^{*} \) ולכן \( P \) נקבעת בצורה יחידה, כי בפוסט הקודם ראינו שהשורש החיובי של מטריצה חיובית הוא יחיד.

האם זה קובע באופן יחיד את \( U \)? לא בהכרח, אבל אם \( P \) הפיכה אז כן, כי אז פשוט נקבל \( U=AP^{-1} \) (בפוסט הקודם אמרתי שזה מאוד אנלוגי למה שקורה עם ההצגה הפולארית של מספרים מרוכבים - שם המספר היחיד שאין לו הצגה יחידה הוא 0, שאינו הפיך).

עכשיו בואו נעבור אל SVD. מה שקורה כאן הוא ש-\( A=X\Lambda Y \) הוא לא פירוק מתאים, כי בפירוק \( A=U\Sigma V^{*} \) שאנחנו מחפשים גם \( U \) וגם \( V \) הן ריבועיות ואוניטריות ואילו \( \Sigma \) עלולה להיות לא ריבועית, בזמן שבפירוק \( A=X\Lambda Y \) אמנם \( X \) הוא ריבועית ואוניטרית, אבל \( Y \) לא ריבועית (למרות שהיא כן סוג של אוניטרית במובן הזה ש-\( YY^{*}=I \)) ודווקא \( \Lambda \) היא ריבועית. אז איך עוברים מפירוק אחד לשני? באופן די ישיר, למען האמת.

ראשית, \( X\in M_{n,n} \) היא כבר ריבועית ואוניטרית, אז מה יש לשנות כאן? נגדיר \( U=X \).

שנית, \( \Lambda\in M_{n,n} \) כבר מכילה את הערכים הסינגולריים על האלכסון. הדבר היחיד שמבדיל בינה ובין \( \Sigma \) שתיארנו קודם, הוא ש-\( \Sigma \) יכולה להיות ארוכה יותר - כלומר, עם יותר עמודות. ליתר דיוק, \( \Sigma\in M_{n,m} \) ובכל החלל הריק הנוסף הזה יש רק אפסים. אז ככה נגדיר אותה; פורמלית, מסמנים \( \Sigma=\left[\Lambda|0\right] \) או משהו בסגנון כדי לתאר את המטריצה שמתקבלת מ-\( \Lambda \) על ידי “הדבקה מימין” של מטריצת אפסים מסדר \( n\times\left(m-n\right) \).

האתגר הגדול יותר הוא \( V \). אי אפשר להשתמש סתם ב-\( Y \) כי \( Y \) היא מסדר \( n\times m \). זכרו ש-\( n\le m \) ולכן ייתכן ש”חסרות לה שורות” כדי להיות ריבועית. אבל כמו שעשינו קודם, אפשר להרחיב. אם נסתכל על איך קיבלנו את \( Y \) מלכתחילה, הגדרנו שורות מסוימות שלה במפורש באמצעות ביטוי שעירב את \( A \), את העמודות של \( X \) ואת הערכים הסינגולריים, ואז הוספנו עוד שורות שהיו בלתי תלויות ואורתונורמליות לשורות הקודמות, רק שאז עצרנו באופן שרירותי אחרי שהיו לנו \( n \) שורות, למרות שיכלנו להמשיך (בטכניקות הרגילות של השלמה לבסיס וגרם-שמידט) ולקבל \( m \) שורות כאלו. אז נשלים את ההרחבה; נסמן את המטריצה של השורות הנוספות שהוספנו ב-\( S \) ועכשיו נשים לב שמה שאני רוצה שיהיה איפה ש-\( Y \) נמצאת כרגע הוא לא \( V \) אלא \( V^{*} \), אז נגדיר את \( V \) בתור הפעלת הצמדה על הכל: \( V=\left[Y^{*}|S^{*}\right] \). זו מטריצה מסדר \( m\times m \), אבל האם באמת מתקיים \( A=U\Sigma V^{*} \)? בואו נראה שמתקיים \( U\Sigma V^{*}=X\Lambda Y=A \) ובכך נסיים את זה.

ראשית, \( X=U \) אז המשוואה שצריך להראות היא מהצורה \( U\Sigma V^{*}=U\Lambda Y \) ועל ידי כפל ב-\( U^{*} \) של שני האגפים נקבל שצריך להראות \( \Sigma V^{*}=\Lambda Y \).

נסמן את השורות של \( Y \) ב-\( y_{1},\ldots,y_{r} \) כמו קודם, ואת השורות החדשות, שנמצאות ב-\( S \), ב-\( y_{r+1},\ldots,y_{m} \). אפשר לתאר באופן סכמטי את שני כפלי המטריצות בתור

\( \Sigma V^{*}=\left(\begin{array}{ccccccc} \sigma_{1} & & & & 0 & \cdots & 0\\ & \sigma_{2}\\ & & \ldots\\ & & & \sigma_{n} & 0 & \cdots & 0 \end{array}\right)\left(\begin{array}{c} y_{1}\\ y_{2}\\ \vdots\\ y_{m} \end{array}\right)=\left(\begin{array}{c} \sigma_{1}y_{1}\\ \sigma_{2}y_{2}\\ \vdots\\ \sigma_{n}y_{n} \end{array}\right) \)

\( \Lambda Y=\left(\begin{array}{cccc} \sigma_{1}\\ & \sigma_{2}\\ & & \ldots\\ & & & \sigma_{n} \end{array}\right)\left(\begin{array}{c} y_{1}\\ y_{2}\\ \vdots\\ y_{n} \end{array}\right)=\left(\begin{array}{c} \sigma_{1}y_{1}\\ \sigma_{2}y_{2}\\ \vdots\\ \sigma_{n}y_{n} \end{array}\right) \)

כאן ה”וקטור” של ה-\( y \)-ים הוא לא וקטור, הוא מטריצה - מה שמקבלים כשכותבים במקום כל \( y \) כזה את כל השורה שהוא מייצג (ולכן \( \sigma_{i}y_{i} \) הוא כפל של כל אברי השורה \( y_{i} \) בסקלר \( \sigma_{i} \)). לי אישית הכי קשה לעכל כאן את זה ש-\( \Sigma V^{*} \) כולל כפל ב”וקטור” של \( y_{1},\ldots,y_{m} \) אבל התוצאה מגיעה רק עד \( y_{n} \); אבל זה ברור אם חושבים על זה רגע כי יש לנו שורה בתוצאה רק לכל שורה של \( \Sigma \), לא מעבר לכך. ה-\( y \)-ים שמעבר ל-\( y_{n} \) שב-\( V^{*} \) לא מקבלים הזדמנות לבוא לידי ביטוי כי הם מוכפלים תמיד בחלק של ה-\( 0\cdots0 \) של \( \Sigma \). הסיבה שבגללה הם קיימים היא כדי ש-\( V \) תהיה מטריצה אוניטרית בעצמה, לא יותר מכך.

בואו נכניס את הדרגה לתמונה

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

קודם כל אולי כדאי שאזכיר מה זו דרגה של מטריצה, שאני מסמן ב-\( \text{rank}A \). ההגדרה שלי היא שזה המימד של מרחב העמודות של \( A \) - כלומר, אם \( A\in M_{n,m} \) אז אני לוקח את \( m \) העמודות של \( A \) ולוקח כל צירוף לינארי אפשרי שלהן ובודק מה הגודל של בסיס למרחב הזה. זה הולך להיות מספר בין 0 ל-\( m \), כש-0 פירושו שהמטריצה \( A \) כולה אפסים ואילו \( m \) פירושו שכל העמודות של \( A \) הן בלתי תלויות, וזה שקול לכך ש-\( A \) הפיכה. אם כן, אפשר לחשוב על דרגה של מטריצה בתור כמות “דרגות החופש” שיש בה - כמה אינפורמציה היא מכילה.

יש עוד אפיונים שקולים לדרגה. ראשית, הדרגה שווה גם למימד של מרחב השורות של המטריצה. זו תוצאה לא טריוויאלית, אבל לא אוכיח אותה כאן; זה גם אומר שהדרגה של מטריצה לא יכולה להיות גדולה מ-\( \min\left\{ n,m\right\} \). עכשיו, כשכופלים את \( A \) בוקטור \( v \) כלשהו, אז \( Av \) הוא וקטור שהוא צירוף לינארי של עמודות \( A \) - ולכן אם אנחנו כופלים את \( A \) בכל הוקטורים האפשריים, נקבל בדיוק את מרחב העמודות של המטריצה; ומצד שני נקבל בדיוק את מה שנקרא התמונה של \( A \) ומסומן \( \text{Im}A\triangleq\left\{ Av\ |\ v\in\mathbb{F}^{m}\right\} \), כך שיוצא ש-\( \text{rank}A=\dim\text{Im}A \).

עכשיו, נסתכל על פירוק ה-SVD של \( A \), \( A=U\Sigma V^{*} \). מה אנחנו יודעים על הדרגות של המטריצות המעורבות? מכיוון ש-\( U,V \) הן הפיכות הן מדרגה מקסימלית ביחס לגודל שלהן, ומה שחשוב כאן הוא שכפל במטריצה כזו לא משנה את הדרגה של התוצאה. כלומר, זה שאני כופל את \( \Sigma \) משמאל ב-\( U \) ומימין ב-\( V \) לא ישפיע על הדרגה, והדרגה של \( U\Sigma V^{*} \) (כלומר של \( A \)) תהיה זהה לדרגה של \( \Sigma \). ומה זו הדרגה הזו? \( \Sigma\in M_{n,m} \) ואנחנו יודעים ש-\( n\le m \) אז הדרגה של \( \Sigma \) היא לכל היותר \( n \), אבל היא יכולה להיות קטנה יותר. יש ב-\( \Sigma \) עמודות שכל אחת מהן כוללת ערך סינגולרי יחיד \( \sigma_{i} \), ולכן מספר העמודות השונות מאפס ב-\( \Sigma \) זהה למספר הערכים הסינגולריים ששונים מאפס. כלומר, \( \text{rank}A=r \) אם ורק אם הערכים הסינגולריים הגדולים מאפס של \( A \) הם \( \sigma_{1},\ldots,\sigma_{r} \).

עכשיו בואו נחזור לתחביב שלי “להציג מטריצות כאילו הן וקטורים”. אני אסמן \( U=\left(u_{1}\ u_{2}\ \ldots\ u_{n}\right) \) כאשר כל \( u_{i} \) הוא וקטור עמודה; ואסמן \( V=\left(v_{1}\ v_{2}\ \ldots\ v_{m}\right) \) עם אותו רעיון בדיוק. עכשיו אפשר להציג את \( U\Sigma V^{*} \) כמו כפל של מטריצה בוקטורים מימין ומשמאל, כמו בתבנית בילינארית:

\( U\Sigma V^{*}=\left(u_{1}\ u_{2}\ \ldots\ u_{n}\right)\left(\begin{array}{ccccccc} \sigma_{1} & & & & 0 & \cdots & 0\\ & \sigma_{2}\\ & & \ldots\\ & & & \sigma_{n} & 0 & \cdots & 0 \end{array}\right)\left(\begin{array}{c} v_{1}^{*}\\ v_{2}^{*}\\ \vdots\\ v_{m}^{*} \end{array}\right)=\left(u_{1}\ u_{2}\ \ldots\ u_{n}\right)\left(\begin{array}{c} \sigma_{1}v_{1}^{*}\\ \sigma_{2}v_{2}^{*}\\ \vdots\\ \sigma_{n}v_{n}^{*} \end{array}\right)=\sum_{i=1}^{n}\sigma_{i}u_{i}v_{i}^{*} \)

כזכור, \( u_{i} \) הוא וקטור עמודה מסדר \( n\times1 \) ואילו \( v_{i}^{*} \) הוא וקטור שורה מסדר \( 1\times m \). לכן המכפלה \( u_{i}v_{i}^{*} \) היא מטריצה מסדר \( n\times m \), בדיוק כמו \( A \) המקורית, אבל מכיוון שהיא מכפלה של שתי מטריצות מדרגה 1 גם היא מדרגה 1 לכל היותר (באופן כללי מכפלה של מטריצות יכולה רק להוריד את הדרגה או להותיר אותה ללא שינוי - אי אפשר ליצור אינפורמציה יש מאין). לכן \( \sum_{i=1}^{n}\sigma_{i}u_{i}v_{i}^{*} \) הוא בדיוק מה שרצינו - הצגה של \( A \) בתור צירוף לינארי של מטריצות מדרגה 1. אפשר גם לכתוב \( \sum_{i=1}^{r}\sigma_{i}u_{i}v_{i}^{*} \) כדי להדגיש שמעניינות אותנו רק המטריצות שמתאימות לערכים הסינגולריים החיוביים.

בשביל מה זה טוב...?

אוקיי, תפסתם אותי, אני לא באמת יודע בשביל מה זה טוב - יש לכל זה הרבה שימושים בתחומים שאני לא כל כך מכיר אז אני לא אוכל להיכנס לזה בפוסט הזה. אבל אני כן אדבר על שימוש אחד שנתקלתי בו והוא חביב ודי קל להצגה (ההקשר היה חישוב קוונטי, ספציפית בנייה של מעגלים קוונטיים יעילים כדי לייצור אופרטורים אוניטריים כלליים; אבל זה לא באמת חשוב להמשך): בהינתן מטריצה ריבועית \( A\in M_{n,n} \) ייתכן שהיא לא אוניטרית, אבל אפשר לשאול מי המטריצה האוניטרית “הכי קרובה” אליה. בהקשר שבו נתקלתי בזה, זה היה שימושי בסיטואציות שבהן ביצענו חישוב שהיא אמור להניב מטריצה אוניטרית, אבל בגלל בעיות נומריות נכשל; במקרה כזה סביר להניח שהמטריצה שהייתה אמורה לצאת היא האוניטרית הקרובה ביותר למה שקיבלנו בפועל, אז אם נוכל למצוא אותה נחליף את המטריצה הנוכחית בה.

הטריק הוא מאוד פשוט: אם נמצא את הפירוק הפולארי \( A=PU \), אז \( U \) היא הקירוב האוניטרי הזה. באופן שקול, אם \( A=U\Sigma V^{*} \) הוא פירוק SVD של \( A \) אז המטריצה האוניטרית הקרובה ביותר היא \( UV^{*} \) (כזכור, התחלנו מ-\( A=X\Lambda Y \); במקרה של הפירוק הפולארי הגדרנו \( U=XY \) ואילו במקרה של SVD הגדרנו \( U=X \) וכאשר \( A \) היא ריבועית, ההגדרה של \( V \) יוצאת פשוט \( V=Y^{*} \) ולכן \( UV^{*}=XY \)).

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

עבור וקטור \( a=\left(a_{1},\ldots,a_{n}\right) \), מכפלה פנימית שלנו בעצמו מחזירה לנו את הנורמה \( \|a\|^{2}=\sum_{i=1}^{n}\left|a_{i}\right|^{2} \). יש עוד דרכים להגדיר נורמות על וקטורים, אז נהוג לפעמים לסמן את הנורמה הזו עם “2” כדי לציין את זה שאנחנו מעלים בחזקת 2 את אברי המטריצה (אחרי שלקחנו את הערך המוחלט שלהם) ובסוף מוציאים שורש ריבועי כדי לקבל את הנורמה: \( \|a\|_{2}=\sqrt{\sum_{i=1}^{n}\left|a_{i}\right|^{2}} \). עבור מטריצות אפשר להגדיר את אותו הדבר בדיוק: ניקח את הכניסות של המטריצה, לכל אחת נחשב את הריבוע של הערך המוחלט, נחבר את הכל ונוציא שורש ריבועי. לדבר הזה קוראים לפעמים נורמת פרובניוס ולפעמים סתם נורמה-2 ואני סתם אשתמש בסימן הנורמה:

\( \|A\|=\sqrt{\sum_{i,j}\left|A_{ij}\right|^{2}} \)

יש דרך קצת יותר נקייה לתאר את הנורמה הזו. כזכור, \( AA^{*} \) שכבר ראינו כמה פעמים היא מטריצה שבה הכניסה ה-\( ij \) היא מכפלה של השורה ה-\( i \) בהצמדה של השורה ה-\( j \) של \( A \). בפרט, אם נסתכל על האלכסון של \( AA^{*} \), מה שיש שם הוא את המכפלה של השורה ה-\( i \) בהצמדה של עצמה, מה שנותן בדיוק את נורמת-2 בריבוע של וקטור השורה הזו. אז אם נחבר את כל אברי האלכסון, נקבל בדיוק את סכום כל הכניסות במטריצה, בערך מוחלט, בריבוע. וכשמדברים על מטריצות, יש שם וסימון פשוטים לסכום אברי האלכסון של המטריצה: “עקבה”, trace. במילים אחרות,

\( \|A\|^{2}=\text{tr}\left(AA^{*}\right) \)

זה מקרה פרטי של המכפלה הפנימית הכללית: \( \left\langle A,B\right\rangle =\text{tr}\left(AB^{*}\right) \).

למעבר לשימוש ב-\( \text{tr} \) יש יתרונות לא זניחים, כי זו פונקציה שאנחנו מכירים יפה אותה ואת המוזרויות שלה. מוזרות שימושית במיוחד נקראת התכונה הציקלית של העקבה. היא אומרת שאם יש לנו מטריצות \( A,B,C,D \) אז

\( \text{tr}\left(ABCD\right)=\text{tr}\left(DABC\right) \)

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

אוקיי, בואו נחזור לעניין שלנו. אפשר להשתמש בנורמת פרובניוס כדי להגדיר מרחק בין שתי מטריצות על ידי \( \|A-B\| \). בהקשר שלנו, השאלה היא זו: נתונה לנו \( A\in M_{n,n} \) ריבועית ואנחנו רוצים למצוא מטריצה \( U\in M_{n,n} \) אוניטרית כך ש-\( \|A-U\| \) יהיה מינימלי (כשהמינימום נלקח על פני כל הערכים האפשריים של \( U\in M_{n,n} \) האוניטריות).

בשביל למצוא \( U \) כזו, בואו נתייחס אל \( \|A-U\| \) בתור מכפלה פנימית ונשתמש בחוקי החשבון הרגילים של מכפלות פנימיות:

\( \|A-U\|=\left\langle A-U,A-U\right\rangle =\left\langle A,A\right\rangle -\left\langle A,U\right\rangle -\left\langle U,A\right\rangle +\left\langle U,U\right\rangle \)

\( =\|A\|^{2}-\left\langle A,U\right\rangle -\overline{\left\langle A,U\right\rangle }+\|U\|^{2}=\|A\|^{2}-2\text{Re}\left\langle A,U\right\rangle +\|U\|^{2} \)

עכשיו, \( \|A\|^{2} \) הוא מספר קבוע (כי \( A \) קבועה) ואילו \( \|U\|^{2}=n \), כי \( U \) אוניטרית ולכן

\( \|U\|^{2}=\left\langle U,U\right\rangle =\text{tr}\left(UU^{*}\right)=\text{tr}\left(I\right) \)

אז הדבר היחיד שיכול להשתנות בערך של \( \|A-U\| \) כשאנחנו עוברים על ה-\( U \) האוניטריות הוא החלק \( -2\text{Re}\left\langle A,U\right\rangle \). אם אנחנו רוצים להקטין את \( \|A-U\| \) ככל הניתן, אנחנו רוצים למקסם את \( \text{Re}\left\langle A,U\right\rangle \) ככל הניתן. עכשיו,

\( \text{Re}\left\langle A,U\right\rangle =\text{Re}\text{tr}\left(AU^{*}\right) \)

עכשיו אפשר להכניס לתמונה את התותח הכבד שלנו: ניקח פירוק SVD של \( A \), \( A=V\Sigma W^{*} \) (אני לא משתמש ב-\( U \) כמו בדרך כלל כי הוא כבר תפוס). אז קיבלנו

\( \text{Re}\text{tr}\left(AU^{*}\right)=\text{Re}\text{tr}\left(V\Sigma W^{*}U^{*}\right)=\text{Re}\text{tr}\left(\Sigma W^{*}U^{*}V\right) \)

כשהמעבר האחרון הוא התכונה הציקלית הידועה לשמצה. זה טוב לנו, כי עכשיו \( \Sigma \) היא בהתחלה, והיא מטריצה אלכסונית עם אלכסון של הערכים הסינגולריים \( \left(\sigma_{1},\ldots,\sigma_{n}\right) \). כזכור, לכפול משמאל במטריצה אלכסונית מכפיל את השורות של מה שמימין בסקלרים של המטריצה האלכסונית. אז אם נסמן \( T=W^{*}U^{*}V \) אז נקבל

\( \text{tr}\left(\Sigma T\right)=\sum_{i=1}^{n}\sigma_{i}t_{ii} \)

ומכיוון שהערכים הסינגולריים הם ממשיים, אפשר להכניס את ה-\( \text{Re} \) פנימה:

\( \text{Re}\text{tr}\left(\Sigma T\right)=\sum_{i=1}^{n}\sigma_{i}\text{Re}\left(t_{ii}\right) \)

עכשיו, \( T \) היא מכפלה של שלוש מטריצות אוניטריות, ולכן גם היא עצמה אוניטרית. זה בפרט אומר שהעמודות של \( T \) הן אורתונורמליות, כלומר מנורמה 1. לכן \( \sum_{i=1}^{n}\left|t_{ij}\right|^{2}=1 \) ובפרט \( \text{Re}\left(t_{ii}\right)\le\left|t_{ii}\right|^{2}\le1 \). לכן הסכום \( \sum_{i=1}^{n}\sigma_{i}\text{Re}\left(t_{ii}\right) \) יקבל את ערכו המקסימלי אם \( \text{Re}\left(t_{ii}\right)=1 \) לכל \( 1\le i\le n \), מה שקורה אם \( T=I \), כלומר אם \( W^{*}U^{*}V=I \) כלומר אם \( U^{*}=WV^{*} \), כלומר אם \( U=VW^{*} \), וזו בדיוק התוצאה שהבטחתי.

מה שאני אוהב כאן הוא שבעזרת SVD אנחנו מקבלים הוכחה פשוטה מאוד לטענה הזו, ובעזרת הפירוק הפולארי אנחנו גם יכולים לקבל אינטואיציה: במספרים מרוכבים, אם היינו רוצים את המספר המרוכב מנורמה \( 1 \) הקרוב ביותר אל \( z \) היינו מותחים קו ישר מ-\( z \) אל ראשית הצירים ובודקים איפה הוא חותך את מעגל היחידה- כלומר, היינו מייצגים את \( z \) בתור \( z=re^{i\theta} \) ואז פשוט היינו מציבים \( r=1 \) ונשארים עם \( e^{i\theta} \). זה בעצם גם מה שאנחנו עושים כאן, כשאנחנו מוצאים את \( A=PU \) ואז מחליפים את \( P \) ב-\( I \). אלגברה לינארית זה כיף.