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

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

פורמלית, פירוק לערכים סינגולריים של מטריצה ממשית או מרוכבת ${\displaystyle \mathbf {M} }$ בעלת ממדים ${\displaystyle m\times n}$ הוא פירוק מהצורה:

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

כאשר U היא מטריצה אוניטרית ממשית או מרוכבת מממד ${\displaystyle m\times m}$, ‏${\displaystyle {\boldsymbol {\Sigma }$ היא מטריצה אלכסונית מלבנית מממד ${\displaystyle \mathbf {m\times n} }$ עם ערכים ממשיים לא-שליליים על האלכסון, ו-${\displaystyle \mathbf {V} ^{*}={\overline {\mathbf {V} ^{\top }$ (הצמודה ההרמיטית של ${\displaystyle \mathbf {V} }$) היא מטריצה אוניטרית ממשית או מרוכבת מממד ${\displaystyle n\times n}$. ערכי האלכסון של ${\displaystyle {\boldsymbol {\Sigma }$, ‏${\displaystyle \sigma _{i}={\boldsymbol {\Sigma }_{i,i}$, נקראים הערכים הסינגולריים של ${\displaystyle \mathbf {M} }$ והם מסודרים מהגדול לקטן. כמו כן, m העמודות של ${\displaystyle \mathbf {U} }$ ו-n העמודות של ${\displaystyle \mathbf {V} }$ נקראות הווקטורים הסינגולריים השמאליים והווקטורים הסינגולריים הימניים של ${\displaystyle \mathbf {M} }$, בהתאמה.

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

• הווקטורים הסינגולריים השמאליים של ${\displaystyle \mathbf {M} }$ הם וקטורים עצמיים של ${\displaystyle \mathbf {M} \mathbf {M} ^{*}$.
• הווקטורים הסינגולריים הימניים של ${\displaystyle \mathbf {M} }$ הם וקטורים עצמיים של ${\displaystyle \mathbf {M} ^{*}\mathbf {M} }$.
• הערכים הסינגולריים השונים מאפס של ${\displaystyle \mathbf {M} }$ (שעל האלכסון של ${\displaystyle {\boldsymbol {\Sigma }$) הם שורשים ריבועיים של הערכים עצמיים השונים מאפס הן של ${\displaystyle \mathbf {M} ^{*}\mathbf {M} }$ והן של ${\displaystyle \mathbf {M} \mathbf {M} ^{*}$.

את הפירוק ניתן לרשום גם כ-$${\displaystyle \mathbf {M} =\sum _{r=1}^{\operatorname {rank} (\mathbf {M} )}\sigma _{r}\mathbf {U} _{\downarrow r}(\mathbf {V} ^{*})_{r\rightarrow }$$ כאשר ${\displaystyle \operatorname {rank} (\mathbf {M} )\leq \min\{m,n\}$ היא הדרגה של ${\displaystyle \mathbf {M} }$.

עבור המטריצה $${\displaystyle \mathbf {M} ={\begin{bmatrix}1&0&0&0&2\\0&0&3&0&0\\0&0&0&0&0\\0&2&0&0&0\end{bmatrix}$$

הפירוק נתון על ידי ${\displaystyle \mathbf {U} \mathbf {\Sigma } \mathbf {V} ^{*}$ באשר

$${\displaystyle {\begin{aligned}\mathbf {U} &={\begin{bmatrix}\color {Green}0&\color {Blue}-1&\color {Cyan}0&\color {Emerald}0\\\color {Green}-1&\color {Blue}0&\color {Cyan}0&\color {Emerald}0\\\color {Green}0&\color {Blue}0&\color {Cyan}0&\color {Emerald}-1\\\color {Green}0&\color {Blue}0&\color {Cyan}-1&\color {Emerald}0\end{bmatrix}\\[6pt]\mathbf {\Sigma } &={\begin{bmatrix}3&0&0&0&\color {Gray}{\mathit {0}\\0&{\sqrt {5}&0&0&\color {Gray}{\mathit {0}\\0&0&2&0&\color {Gray}{\mathit {0}\\0&0&0&\color {Red}\mathbf {0} &\color {Gray}{\mathit {0}\end{bmatrix}\\[6pt]\mathbf {V} ^{*}&={\begin{bmatrix}\color {Violet}0&\color {Violet}0&\color {Violet}-1&\color {Violet}0&\color {Violet}0\\\color {Plum}-{\sqrt {0.2}&\color {Plum}0&\color {Plum}0&\color {Plum}0&\color {Plum}-{\sqrt {0.8}\\\color {Magenta}0&\color {Magenta}-1&\color {Magenta}0&\color {Magenta}0&\color {Magenta}0\\\color {Orchid}0&\color {Orchid}0&\color {Orchid}0&\color {Orchid}1&\color {Orchid}0\\\color {Purple}-{\sqrt {0.8}&\color {Purple}0&\color {Purple}0&\color {Purple}0&\color {Purple}{\sqrt {0.2}\end{bmatrix}\end{aligned}$$

מטריצת הערכים הסינגולריים ${\displaystyle {\boldsymbol {\Sigma }$, שמבצעת מתיחה ושינוי סקלה, מורכבת רק מ-0ים מחוץ לאלכסון הראשי (כאשר העמודה שמחוץ לבלוק הריבועי המקסימלי מסומנת בכתב אפור נטוי) ואילו באלכסון הראשי רק אחד הערכים הסינגולריים הוא 0 (צבוע באדום). מכאן אפשר להסיק שדרגת המטריצה היא 3 (מספר הערכים הסינגולריים שאינם 0). המטריצות ${\displaystyle \mathbf {U} }$ ו-${\displaystyle \mathbf {V} ^{*}$ הן אוניטריות, ומכיוון שהן ממשיות (כלומר: כל איבריהן הן מספרים ממשיים) הן גם אורתוגונליות. פירוש העובדה שהן אוניטריות היא: $${\displaystyle {\begin{aligned}\mathbf {U} \mathbf {U} ^{*}&={\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\end{bmatrix}=\mathbf {I} _{4}\\[6pt]\mathbf {V} \mathbf {V} ^{*}&={\begin{bmatrix}1&0&0&0&0\\0&1&0&0&0\\0&0&1&0&0\\0&0&0&1&0\\0&0&0&0&1\end{bmatrix}=\mathbf {I} _{5}\end{aligned}$$

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

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

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

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

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

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

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

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

• פירוק לערכים סינגולריים, באתר MathWorld (באנגלית)