ההתנהגות האופיינית של בניות חכמות של בסיסים מוגדלים
פרסום מחקר פורץ דרך במגזין PNAS
בעבודת מחקר פורצת דרך שפורסמה החודש בכתב העת של האקדמיה האמריקאית למדעים PNAS , מראים מרינה חייקין - תלמידה לתואר שני בהנדסת חשמל בהנחייתו של פרופ' רמי זמיר מבית הספר להנדסת חשמל באוניברסיטת תל אביב, יחד עם ד״ר מתן גביש מבית הספר להנדסה ומדעי המחשב באוניברסיטה העברית - שניתן לייצר בסיסים מוגדלים טובים על ידי וקטורי הזמן של תת-קבוצה לא רגולרית של תדרים מתוך מטריצת התמרת פורייה דיסקרטית (DFT).
האפליקציה – קידוד אנלוגי בתקשורת
מידע המשודר דרך תווך פיזיקלי סובל מתופעות של רעש, דעיכות, הפרעות ועיוותים שונים. בכדי לאפשר שיחזור של המידע במקלט נדרש להגן עליו מראש על ידי תוספת של יתירות (redundantre presentation). שיטת התקשורת הנפוצה בימינו היא ספרתית (digital communication), שאז היתירות נוצרת על ידי הוספה של ביטי בדיקת זוגייות (parity-check bits). למרות זאת, יש לזכור שבדרך כלל הן המידע והן התווך הם במהותם אנלוגיים; לדוגמא, שידור של אותות דיבור ותמונה דרך ערוץ אלחוטי. לכן טיבעי לבחון גם גישות להוספת "יתירות אנלוגית": הרחבה ספקטראלית של אות המידע, או באופן כללי - פרישה של מרחב האותות על ידי בסיס מוגדל. למעשה, לקידוד אנלוגי יש יתרונות נוספים, כמו עמידות טובה יותר בתנאים של אי וודאות, וסיבוכייות מופחתת.
מה זה בעצם בסיס מוגדל?
למדנו באלגברה שבסיס אורתוגונלי פורש את המרחב אם גודלו שווה למימד המרחב, או את מרחב האותות אם גודלו כמספר דרגות החופש. בסיס מוגדל(over-complete basis, frame) לעומת זאת מכיל יותר וקטורים מממד המרחב. עובדה זו מאפשרת מגוון של שימושים בעיבוד אותות ותקשורת, דוגמת ייצוג אותות "דלילים" או הוספת יתירות לצורך קידוד אנלוגי. כמובן שבסיס כזה לא יכול להיות אורתוגונלי, וההגדרה של מהו "בסיס מוגדל טוב" נתונה לפרשנות. על פי אחת ההגדרות, בסיס מוגדל טוב נבחן ביכולת שלו לשחזר את המקור (כלומר לפתור מערכת של משוואות לינאריות) מתוך תת-קבוצה אקראית של היטלים רועשים. תכנון וניתוח של בסיסים כאלה בממד גבוה הוא אתגר לא פשוט, שלרוב נפתר על ידי הגרלה אקראית של הווקטורים ואנליזה סטוכסטית, למשל ביישומים נפוצים כמו חישה דחוסה (compressed sensing) ולמידה חישובית (machine learning).
איזה תכונה אוניברסלית חדשה ומפתיעה מצאתם?
בבסיס העבודה נמצאת תכונת אוניברסליות חדשה ומפתיעה שגילינו, לפיה לבסיס מוגדל "טוב" יש תכונות דומות לאלו של מטריצות MANOVA, מבנה המוכר מהתורה של מטריצות אקראיות. דוגמא לתכונה כזו היא פילוג הערכים הסינגולריים של תת-קבוצה אקראית של בסיס מוגדל.
אלו השלכות מעניינות של התוצאה גיליתם?
השלכה מעניינת של תוצאה זו היא שבחירה פשוטה אך מושכלת של וקטורי הבסיס מבטיחה ביצועי שיחזור טובים יותר מאלה (של בסיס אקראי) שעבורו לערכים הסינגולריים יש פילוג אופייני מסוגMarcenko Pasturהעבודה עוסקת במגוון רחב של בסיסים מפורסמים – דטרמיניסטיים ואקראיים, וכוללת ניתוח שחלקו סטטיסטי וחלקו אנליטי עבור מגוון של פרמטרים ומדדי טיב. התכונות הטובות של בסיסים דטרמיניסטיים מאפשרות, בנוסף לשיפור בביצועים, חסכון בסיבוכיות מקום של מערכות תקשורת שיכולות לייצר את מנגנון הקידוד באופן מהיר ומובנה, במקום לשמור מטריצות אקראיות גדולות.
מחקרים אחרונים
