פירוק לערכים סינגולריים

הדגמה חזותית של פירוק SVD של מטריצה ממשית דו-ממדית M שהיא Shear transformation. תחילה, ניתן לראות את דיסק היחידה, בכחול, ועליו מסומנים שני וקטורי היחידה הקאנוניים. לאחר מכן ניתן לראות את הפעולה של M, שמעתיקה את הדיסק לאליפסה.
פירוק ה-SVD מפרק את M לשלוש העתקות פשוטות: העתקת סיבוב (rotation)‏ V*‎, העתקת מתיחה (scaling)‏ Σ שמותחת את הנקודות לאורך מערכת הצירים המסובבת והעתקת סיבוב נוספת U. הערכים σ₁ ו-σ₂ של צירי האליפסה הם הערכים הסינגולריים של M.

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

פורמלית, פירוק לערכים סינגולריים של מטריצה ממשית או מרוכבת M בעלת ממדים m×n הוא פירוק מהצורה:

$\mathbf {M} =\mathbf {U} {\boldsymbol {\Sigma }}\mathbf {V} ^{*}$

כאשר U היא מטריצה אוניטרית ממשית או מרוכבת מממד m×m, ‏Σ היא מטריצה אלכסונית מלבנית מממד m×n עם ערכים ממשיים לא-שליליים על האלכסון, ו-V*‎ (הצמודה ההרמיטית של V) היא מטריצה אוניטרית ממשית או מרוכבת מממד n×n. ערכי האלכסון של Σ, ‏Σ_i,i, נקראים הערכים הסינגולריים של M והם מסודרים מהגדול לקטן. כמו כן, m העמודות של U ו-n העמודות של V נקראות הווקטורים הסינגולריים השמאליים והווקטורים הסינגולריים הימניים של M, בהתאמה.

הפירוק מקיים את התכונות הבאות:

• הווקטורים הסינגולריים השמאליים של M הם וקטורים עצמיים של MM*‎.
• הווקטורים הסינגולריים הימניים של M הם וקטורים עצמיים של M*M.

• הערכים הסינגולריים השונים מאפס של M (שעל האלכסון של Σ) הם שורשים ריבועיים של הערכים עצמיים השונים מאפס הן של M*M והן של MM*‎.

נורמות

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

• הערך הסינגולרי הגדול ביותר הוא נורמה. נורמה זו נקראת הנורמה הספקטרלית והיא שווה לנורמה p המושרית עבור p=2. באופן פורמלי: $\sigma _{1}(M)=||M||_{2}={\text{sup}}{\frac {||Mx||_{2}}{||x||_{2}}}$
• נורמת Frobenius, השווה לשורש סכום ריבועי איברי המטריצה, שווה גם לשורש סכום ריבועי הערכים הסינגולריים: $\Vert M\Vert _{F}^{2}=\sum \sum \vert m_{ij}\vert ^{2}=\sum \sigma _{i}^{2}$
• נורמת Ky-Fan, השווה לסכום k הערכים הסינגולרים הגדולים ביותר: $\Vert M\Vert _{(k)}=\sum _{i=1}^{k}\sigma _{i}$. כאשר סוכמים את כל הערכים הסינגולריים, הנורמה נקראת גם Nuclear Norm. נורמה זו, משמשת לעיתים (בעיקר בבעיות אופטימיזציה) כתחליף ל- rank, כיוון שהיא קמורה (convex) ורציפה. סימון מקובל עבור נורמת ה Nuclear הינו: $\Vert M\Vert _{*}$.
• נורמת Schatten, שהיא בעצם נורמת p הרגילה לוקטורים מופעלת על הערכים הסינגולריים: $\Vert M\Vert _{p}^{p}=\sum \sigma _{i}^{p}$. עבור p=2 מתקבלת נורמת Frobenius ועבור p=1 מתקבלת ה Nuclear norm.

שימושים

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

• מציאת הדרגה (rank) של מטריצה. הדרגה שווה למספר הערכים הסינגולריים הגדולים מאפס.
• מציאת מרחב האפס (null space) ימני או שמאלי, בפתרון מערכת משוואות לינאריות הומוגנית. מרחב האפס נפרס על ידי הווקטורים הסינגולריים המתאימים לערכים הסינגולרים שהם אפס.
• חישוב Pseudo-Inverse.
• חישוב PCA מבלי לחשב את מטריצת הקורלציה.
• מציאת קירוב על ידי מטריצה מדרגה נמוכה למטריצה כלשהי (Low Rank Approximation). הקירוב מתבצע על ידי איפוס של k הערכים הסינגולרים הקטנים ביותר והוא אופטימלי הן במובן הנורמה הספקטרלית והן במובן נורמת Frobenius.
• הקירוב הטוב ביותר למטריצה כלשהי $M$ בעזרת מטריצה אורתוגנלית תחת נורמת Frobenius. ידועה גם כבעיית "מיטת סדום". הפתרון נתון על ידי הביטוי $UV^{*}$, כאשר $U$ ו-$V$ מתקבלים מחישוב ה-SVD של $M$. שיטה זו משמשת למשל על-מנת למצוא את מטריצת הסיבוב (שהיא כמובן אורתוגנולית) בין שני סטים של נקודות דו-ממדיות.
• Condition number של מטריצה - מספר שאינו קטן מ-1, הקובע את יציבות הבעיה המתמטית ואת שגיאת החישוב המקסימלית העשויה להתקבל במחשב הפועל באריתמטיקה של נקודה צפה. מוגדר כ- $\kappa (M)={\frac {\sigma _{\text{max}}}{\sigma _{\text{min}}}}$. ערך גדול משמעותו שהבעיה היא ill-conditioned. חשוב לציין שלמרות שה- condition number מהווה מדד לשגיאת חישוב אפשרית, זוהי תכונה של המטריצה ולא של האלגוריתם או הייצוג האריתמטי בו משתמשים.

חישוב Pseudo-Inverse

פירוק SVD יכול לשמש כדי לחשב את ה-Pseudo-Inverse של מטריצה, כאשר עבור M שהפירוק שלה הוא $\mathbf {M} =\mathbf {U} {\boldsymbol {\Sigma }}\mathbf {V} ^{*}$ ניתן למצוא את ה-Pseudo-Inverse:

$\mathbf {M} ^{+}=\mathbf {V} {\boldsymbol {\Sigma }}^{+}\mathbf {U} ^{*}$

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

לקריאה נוספת

• Golub, Gene H.; Van Loan, Charles F. (2013), Matrix Computations (4th ed.), Johns Hopkins, מסת"ב 978-1421407944.

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