מתמטיקה שימושית ו־AᵀA

SVD — מארבע תנועות אל אנרגיה

Positive Definite Matrices and the SVD

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

יחידת לימוד עצמאיתשיעור 2 מתוך 5כ־85 דקות כולל תרגול5 מטרות למידה

1
נקודת פתיחהמה כבר ידוע ומה השאלה?
2
ניבוימה יקרה במקרה הפשוט?
3
המחשהמה באמת משתנה בתמונה?
4
ניסוח והצדקהשם, נוסחה ולמה היא נכונה
5
בדיקהדוגמה, תרגול ומשוב
6
העברהמקרה חדש והמשך המסלול

שאלה לפני נוסחה

מה אנחנו מנסים לראות?

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

מטריצה מסובכת אינה חייבת להיות תנועה מסובכת: Vᵀ מסובבת את כיווני הקלט אל הצירים, Σ מותחת ומוחקת או מוסיפה ממדים, ו־U מסובבת אל כיווני הפלט. במבט אחר, האנרגיה xᵀSx היא גובה מעל המישור: ערכים חיוביים בכל כיוון יוצרים קערה, סימנים מעורבים יוצרים אוכף, וכיוון בעל אנרגיה אפס יוצר עמק שטוח.

לפני ההמחשה: קראו רק את הכותרת “מן המעגל אל אליפסת המתיחות”. מה לדעתכם ישתנה, מה יישאר קבוע, ואיזה סימן בתמונה יוכל להפריך את הניבוי?

לראות לפני שמחשבים · מסע חזותי

בואו נבנה את ה־SVD, רעיון אחד בכל פעם

אין צורך לזכור עדיין את U,‏ Σ או V. בכל תחנה נשאל שאלה אחת, נראה פעולה אחת, ורק בסוף נחבר את השמות לנוסחה.

תחנה 1 מתוך 6

אותו ציור, אבל לא אותו וקטור

הווקטורים ‎(1,2) ו־‎(1,2,0) יכולים להיראות זהים על הדף. הראשון אינו מכיר בכלל ציר z; לשני יש רכיב z שערכו כרגע אפס.

הבדיקה הפשוטה: אפשר להזיז את ‎(1,2,0) בכיוון z. שום סיבוב בתוך R² לא יעניק ל־‎(1,2) רכיב שלישי.

לכן השאלה הבאה היא: איזו פעולה יכולה להעביר וקטור מעולם אחד לאחר?

האנימציה חוזרת בכל מעבר לתחנה

תקציר כל שש התחנות

R² ו־R³ הם מרחבים שונים גם כאשר הרכיב השלישי הוא אפס.
מטריצה מלבנית מעבירה מ־Rⁿ אל Rᵐ; “מוחק ממד” מסיר רכיב ו“מוסיף ממד” מוסיף רכיב אפס.
AᵀA ו־AAᵀ סימטריות וחיוביות למחצה; הווקטורים העצמיים שלהן הם vᵢ ו־uᵢ והערכים המשותפים הם σᵢ².
Vᵀ מסובבת את הקלט, Σ מותחת ומשנה ממד, ו־U מסובבת אל מרחב הפלט.
כל כדור נשלח לאליפסואיד שציריו באורכי הערכים הסינגולריים.
סכום שכבות מדרגה אחת מוביל לקירוב מדרגה נמוכה, דחיסת תמונות, סינון רעש ו־PCA; ההקבלה לפורייה היא פירוק של אובייקט מסובך לרכיבים פשוטים.

אחרי שראינו

בסוף השיעור תוכלו

להסביר מדוע מטריצה m×n מעבירה וקטורים מ־Rⁿ אל Rᵐ ומה עושים “מוחק ממד” ו“מוסיף ממד”.
לבנות את הווקטורים הסינגולריים מ־AᵀA ומ־AAᵀ ולפרש את ארבע הפעולות Vᵀ,‏ Σ ו־U.
לבדוק חיוביות בהחלט באמצעות אנרגיה, ערכים עצמיים או pivots.
להוכיח xᵀAᵀAx=‖Ax‖² ולהסיק מתי AᵀA חיובית בהחלט.
לפרש דרגה, condition number, קירוב מדרגה נמוכה והקשר ל־PCA באמצעות הערכים הסינגולריים.

נותנים שמות למה שראינו

מושגים שנשתמש בהם

מטריצה מלבנית m×n: טרנספורמציה לינארית מ־Rⁿ אל Rᵐ; מספר העמודות הוא ממד הקלט ומספר השורות הוא ממד הפלט.
וקטור סינגולרי ימני vᵢ: כיוון קלט שהוא וקטור עצמי של AᵀA.
וקטור סינגולרי שמאלי uᵢ: כיוון פלט שהוא וקטור עצמי של AAᵀ ומקיים Avᵢ=σᵢuᵢ כאשר σᵢ>0.
חיובית בהחלט: מטריצה סימטרית S שעבורה xᵀSx>0 לכל x≠0.
חיובית למחצה: מטריצה סימטרית שעבורה xᵀSx≥0, אך ייתכן כיוון לא־אפס בעל אנרגיה אפס.
ערך סינגולרי σ: שורש לא־שלילי של ערך עצמי של AᵀA.
SVD: הפירוק A=UΣVᵀ עם U,V אורתוגונליות ו־Σ אלכסונית מלבנית ולא־שלילית.
condition number: היחס κ=σmax/σmin; הוא מודד עד כמה A מעוותת יחסים וכמה הפתרון רגיש.
rank: מספר הערכים הסינגולריים החיוביים.

מהמילים אל הסימנים

כותבים את הפעולה שכבר ראינו

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

להצגת נוסחת המפתח

קראו כל סימן כפעולה, לא כמשהו שצריך לשנןA=UΣVᵀ; xᵀAᵀAx=‖Ax‖²

מרכיבים את הפעולות

מהתמונה אל הנוסחה — הגזירה, בלי לדלג על הצעדים

מגדירים אנרגיה ריבועית
ל־S סימטרית, xᵀSx הוא מספר. בבסיס העצמי הוא סכום משוקלל של ריבועי הקואורדינטות.
S=QΛQᵀ, x=Qc ⇒ xᵀSx=Σλᵢcᵢ²
שלושה מבחנים לאותה תכונה
חיוביות בהחלט שקולה לערכים עצמיים חיוביים. באלימינציה סימטרית היא שקולה ל־pivots חיוביים; ב־2×2 מספיק a>0 ו־det(S)>0.
S≻0 ⇔ λᵢ>0 ⇔ pivots>0
מדוע AᵀA לעולם אינה שלילית
הכפל מתקפל לנורמה של Ax, ולכן האנרגיה אינה יכולה להיות שלילית. היא אפס בדיוק בכיוונים ש־A מוחקת.
xᵀAᵀAx=(Ax)ᵀ(Ax)=‖Ax‖²≥0
מתי החיוביות חזקה?
כדי לקבל >0 לכל x≠0, אסור שיהיה כיוון לא־אפס ב־N(A). לכן עמודות בלתי תלויות הן התנאי המדויק.
AᵀA≻0 ⇔ N(A)={0}
מוצאים את V ואת Σ
מפעילים את משפט הספקטרום על AᵀA. הווקטורים העצמיים האורתונורמליים הם עמודות V, ושורשי הערכים העצמיים הם σᵢ.
AᵀAvᵢ=σᵢ²vᵢ
מוצאים את U
כאשר σᵢ>0, הווקטור Avᵢ באורך σᵢ. חלוקה באורך נותנת uᵢ יחידה ומבטיחה Avᵢ=σᵢuᵢ.
uᵢ=Avᵢ/σᵢ; AV=UΣ
מרכיבים ומפרשים
Vᵀ מעביר לכיווני הקלט, Σ מותחת, ו־U מחזירה לכיווני הפלט. מחיקת σ קטנים יוצרת קירוב מדרגה נמוכה ומסננת כיוונים רגישים.
A=UΣVᵀ=Σσᵢuᵢvᵢᵀ

עכשיו רואים את השיטה בפעולה

דוגמאות פתורות, צעד אחר צעד

דוגמה 1

מטריצה מדרגה אחת

בנו SVD עבור A=[[1,2],[3,6]].

מחשבים AᵀA=[[10,20],[20,40]], שערכיה העצמיים 50 ו־0.
וקטורי היחידה הם v₁=(1,2)/√5 ו־v₂=(−2,1)/√5. לכן σ₁=√50 ו־σ₂=0.
u₁=Av₁/σ₁=(1,3)/√10. בוחרים u₂ מאונך, למשל (−3,1)/√10.
הפירוק הוא A=σ₁u₁v₁ᵀ; אין איבר שני מפני ש־σ₂=0.
הדרגה היא 1 ו־κ אינסופי: הכיוון v₂ נמחק לגמרי.

התוצאה ומה היא אומרת

σ=(√50,0), rank(A)=1, N(A)=span{(−2,1)}.

דוגמה 2

קערה או אוכף?

סווגו את S=[[5,6],[6,7]] ואת T=[[1,2],[2,9]].

ל־S האיבר הראשון 5>0 אך det(S)=35−36=−1<0.
לכן הערכים העצמיים בעלי סימנים מנוגדים והאנרגיה יוצרת אוכף.
ל־T מתקיים 1>0 ו־det(T)=9−4=5>0.
לכן שני ה־pivots ושני הערכים העצמיים חיוביים: T חיובית בהחלט.

התוצאה ומה היא אומרת

S בלתי־מוגדרת; T חיובית בהחלט.

איפה זה פוגש את העולם

יישום

SVD משמשת לדחיסת תמונות ולסינון רעש באמצעות השמטת שכבות σᵢuᵢvᵢᵀ קטנות, ול־PCA באמצעות זיהוי כיווני השונות המרכזיים. ערך סינגולרי קטן מזהיר שכיוון מסוים כמעט נמחק ולכן שגיאה קטנה בנתונים עלולה להפוך לשינוי גדול במקדמים.

מלכודת נפוצה

מה כדאי לבדוק

לבלבל בין ערכים עצמיים של A לבין ערכים סינגולריים. ערכים עצמיים עלולים להיות שליליים או מרוכבים ותלויים בכך ש־A ריבועית; σ תמיד ממשיים ולא־שליליים ומוגדרים לכל מטריצה.

בודקים שהרעיון יושב

תרגול ומשוב

בדיקת הבנה

בחרו תשובה ורק אז בדקו את עצמכם

ל־A יש עמודות תלויות. מה נכון לגבי AᵀA?

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

בחרו אחת מהאפשרויות כדי להמשיך.

עכשיו אתם

אתגר קצר

עבור A=[[1,1],[0,ε]], תארו מה קורה ל־σ₂ ול־κ כאשר ε מתקרב לאפס, והסבירו גאומטרית.

רמז ראשון

הדטרמיננטה של A היא ε ומכפלת הערכים הסינגולריים היא |ε|. σ₁ נשארת בערך √2.

הצגת דרך הפתרון

AᵀA=[[1,1],[1,1+ε²]].
כאשר ε→0, המטריצה מתקרבת לדרגה 1 ולכן σ₂→0.
מאחר σ₁ נשאר חיובי, κ=σ₁/σ₂→∞.
המעגל נמחץ לאליפסה דקה מאוד: הבדלים בכיוון החלש כמעט אינם נראים בפלט.

מימוש הנושא

קוד שאפשר לקחת לניסוי

הקוד מיישם את אותו רעיון מתמטי. ב־JavaScript אפשר להריץ אותו כאן; גרסת Python זמינה להשוואה ולהעתקה.

הקשר למתמטיקה

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

פלט צפוי

עבור [[1,2],[3,6]] יתקבלו σ₁≈7.071, σ₂=0 ו־rank=1.

ניסוי המשך

החליפו את 6 ב־6.1. כיצד משתנים σ₂ וה־condition number כאשר המטריצה כבר אינה בדיוק מדרגה אחת?

מהרעיון אל הקוד

מימוש חישובי

function singularValues2x2(A) {
  const a=A[0][0]**2+A[1][0]**2;
  const b=A[0][0]*A[0][1]+A[1][0]*A[1][1];
  const d=A[0][1]**2+A[1][1]**2;
  const trace=a+d, determinant=a*d-b*b;
  const root=Math.sqrt(Math.max(0,trace**2-4*determinant));
  const values=[(trace+root)/2,(trace-root)/2];
  return values.map(value=>Math.sqrt(Math.max(0,value)));
}

const A=[[1,2],[3,6]];
const sigma=singularValues2x2(A);
console.log({sigma,rank:sigma.filter(value=>value>1e-10).length});

from math import sqrt

def singular_values_2x2(A):
    a=A[0][0]**2+A[1][0]**2
    b=A[0][0]*A[0][1]+A[1][0]*A[1][1]
    d=A[0][1]**2+A[1][1]**2
    trace, determinant=a+d, a*d-b*b
    root=sqrt(max(0,trace**2-4*determinant))
    values=[(trace+root)/2,(trace-root)/2]
    return [sqrt(max(0,value)) for value in values]

A=[[1,2],[3,6]]
sigma=singular_values_2x2(A)
print({"sigma":sigma,"rank":sum(value>1e-10 for value in sigma)})

לפני שממשיכים

מה לוקחים מהשיעור

מטריצה m×n פועלת מ־Rⁿ אל Rᵐ; Σ היא המקום שבו מתרחשים המתיחה ושינוי הממד.
חיוביות בהחלט היא טענה על האנרגיה בכל כיוון, לא רק על איברי האלכסון.
AᵀA תמיד חיובית למחצה וחיובית בהחלט בדיוק כשעמודות A בלתי תלויות.
ה־SVD מפריד סיבוב קלט Vᵀ, מתיחות ושינוי ממד Σ, וסיבוב פלט U.
ערכים סינגולריים קטנים חושפים אובדן מידע, דרגה נמוכה ורגישות מספרית; שמירת הגדולים בלבד נותנת קירוב מדרגה נמוכה.

משימת מעבדה לשיעור הזה

תחנה 2 — לראות מעגל הופך לאליפסה

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

לפתיחת התחנה

מקורות להעמקה בלבד — השיעור עומד בפני עצמו

מדריך המרצים: עמ׳ 197–204

ספר הלימוד: עמ׳ 396–405