אפסילון רשת
פעולות נוספות
בתאוריה המתמטית של מרחבים מטריים, ε-רשת (אפסילון רשת) היא מונח שמשמש לקירוב ודיסקרטיזציה של מרחבים רציפים. ε-רשת הוא מושג מרכזי בהסתברות בממד גבוה ומטריצות אקראיות, שעוזר למדוד כיסוי של קבוצה במרחב מטרי.
ε-רשת עוזרת לפשט מרחב מטרי בכך שהיא נותנת מספר סופי של נקודות שמקרבות את המרחב במידה מסוימת. קירובים אלה שימושיים בין היתר במרחבים מממד גבוה שם חישובים מדויקים יכולים להיות יקרים חישובית.
הגדרות עריכה
בהינתן מרחב מטרי <math>(X,d)</math> ותת קבוצה <math>A\subset X </math>, <math>N \subset X </math> היא ε-רשת של <math>A </math> אם עבור כל נקודה <math>x \in A </math> קיימת נקודה <math>n \in N </math> כך ש - <math>d(x,n)\leq\varepsilon </math>. המשמעות היא שהאיחוד של הכדורים הפתוחים ברדיוס <math>\varepsilon </math>, שמרכזיהם ב-<math>N </math>, מכסה את <math>A </math> כולה.
מספר הכיסוי של <math>A </math>, שאותו מסמנים ב-<math>\mathcal{N}(A,d,\varepsilon) </math>, הוא הגודל המינימלי של ε-רשת עבור הקבוצה <math>A </math> במרחב המטרי <math>(X,d) </math>. מספר הכיסוי מודד מה המספר המינימלי של כדורים ברדיוס <math>\varepsilon </math> הנדרשים כדי לכסות את הקבוצה <math>A </math>.
דוגמאות עריכה
כיסוי של משושה: המשושה <math>K </math> עם צלע באורך 1 מכוסה על ידי שבעה עיגולים ברדיוס <math>\varepsilon = 1/2 </math> ולכן <math>\mathcal{N}(K,1/2)\leq7 </math>.
כיסוי של קבוצה במרחב האוקלידי <math>\mathbb{\R}^n </math>: תהי <math>K\subset\mathbb{R}^n
</math> ו-<math>\varepsilon>0 </math> אז קיימים חסמים למספר הכיסוי של הקבוצה התלוי בקבוצה K וב-ε:
<math>\frac{|K|} {|\varepsilon B^n_2|}\leq \mathcal{N}(K,\varepsilon)\leq \frac{|K+(\varepsilon/2)B^n_2|} {|(\varepsilon/2)B^n_2|} </math> כאשר <math>\varepsilon B^n_2 </math> הוא כדור ברדיוס <math>\varepsilon </math>, והערך המוחלט מציין את מידת הקבוצה.
אי שוויון זה מספק חסם עליון וחסם תחתון למספר הכיסוי של קבוצה לפי הנפח של הקבוצה ושל סכום מינקובסקי (אנ') של הקבוצה עם כדור.
שימושים במתמטיקה עריכה
מטריצות אקראיות עריכה
בתורת המטריצות האקראיות ε-רשת משמשת להערכת הנורמה הספקטרלית של מטריצה אקראית.
נורמת האופרטור של מטריצה A היא <math>\|A\| = \sup_{\|x\| = 1}\|Ax\| </math> כאשר <math>\|x\| </math> היא הנורמה האוקלידית של הווקטור <math>x </math>. על ידי כיסוי של ספרת היחידה <math>S^{n-1} </math> ב-ε-רשת <math>N </math>. ניתן להעריך את נורמת האופרטור של המטריצה: <math>\|A\| \approx \max_{x\in N} \|Ax\| + \varepsilon \|A\|</math> כיוון ש-<math>N </math> סופית ניתן להעריך את <math>\max_{x\in N} \|Ax\|</math> על קבוצה סופית במקום להעריך את <math>\sup _{\|x\|=1} \|Ax\|</math> על הקבוצה הרציפה <math>\{ x\in X | \|x\|=1 \}</math> במרחב המטרי <math>X</math>.
גבולות בהסתברות עריכה
ε-רשת מאפשרות שליטה על הגבולות בהסתברות של נורמת האופרטור של מטריצות אקראיות. על ידי שליטה בגודל ε-רשת בשילוב עם אי שוויון בול ואי שוויוני ריכוז ניתן להעריך את ההסתברות ש-<math>\|A\|</math> תהיה גדולה מסף מסוים. טכניקה זו שימושית בהוכחת תוצאות כמו משפט באי-ין.
משפט באי-ין (Bai-Yin) עריכה
המשפט[1] מאפיין את ההתנהגות של הערכים הסינגולרים הקיצוניים של מטריצות אקראיות גדולות ומספק חסמים על נורמת האופרטור של המטריצה. משפט זה הוא יסודי לתחום המטריצות האקראיות, ומספק גבולות כמעט בוודאות על נורמת האופרטור ככל שהמטריצה גדלה, ובכך עוזר להבין את התכונות הספקטרליות של מטריצות אקראיות גדולות.
משפט באי-ין החזק, חסם עליון עריכה
יהי <math>\xi</math> משתנה מקרי ממשי עם תוחלת אפס, שונות 1 ומומנט רביעי סופי. ולכל <math>1\leq i\leq j</math> תהי <math>\xi_{ij}</math> סדרה משתנים בלתי תלויה בזהות המתפלגים זהה עם התפלגות <math>\xi</math> וגם <math>\xi_{ij} = \xi_{ji}</math>. תהי <math>M_n := (\xi_{ij})_{1 \leq i,j \leq n}\ </math> המטריצה האקראית הנוצרת מהגוש העליון השמאלי בגודל <math>n \times n</math> אז כמעט בוודאות מתקיים: <math>\limsup_{n \to \infty} \frac{\|M_n\|_{\text{op}}}{\sqrt{n}} \leq 2</math>
משפט באי-ין, חסם תחתון עריכה
תהי <math>M </math> מטריצה אקראית סימטרית ממשית, כאשר האלמנטים מעל האלכסון <math>\xi_{ij},i\leq j</math> הם בלתי תלויים במשותף, עם תוחלת אפס ושונות אחת, והם חסומים בגודלם על ידי <math>O(1)</math>. אז החציון (או הממוצע) של <math>\|M\|_{\text{op}} </math> הוא לפחות: <math>(2 - o(1))\sqrt{n}</math>.
בהוכחת המשפט משתמשים בטיעון ε-רשת להערכת נורמת האופרטור של מטריצות אקראיות. הרשת מכסה את כדור היחידה במרחב, ומאפשרת הצבת חסם על הנורמה עבור וקטורים קרובים לנקודות ברשת, מה שמוביל לחסמים טובים לערכים הסינגולריים של המטריצה.
תהליכים אקראיים עריכה
תהליכים אקראיים הם תהליכים שהתפתחותם תלויה בגורמים מקריים, ויש להם שימושים רבים מפיזיקה, ביואינפורמטיקה, שוק ההון ועוד. טיעוני ε-רשת משמשים להוכחת לאי שוויונים מרכזיים בתחום.
אי שוויון הצמצום סודקוב עריכה
אי שוויון הצמצום סודקוב הוא אי שוויון מרכזי עבור תהליכים גאוסים עם ממוצע אפס התלוי במספר כיסוי של קבוצה ומספק חסם תחתון לסופרמום של תהליך גאוסיאני.
יהי <math>({X_t})_{t\in T} </math> תהליך אקראי גאוסי עם תוחלת אפס ותהי <math>d</math> מטריקה על קבוצת האינדקס <math>T</math> כך ש - <math>d(t,s) = \|X_t - X_s\|_L^2 = (\mathbb{E}(|X_t - X_s|)^2)^{\frac{1} {2}} </math> אז לכל <math>\varepsilon>0
</math> קיים קבוע <math>c</math> כך ש - <math>\mathbb{E}\sup (X_t)_{t\in T} \geq c\varepsilon \sqrt{\log \mathcal{N}(T,d,\varepsilon)}</math>.
אי שוויון הצמצום של סודקוב ב-<math>\mathbb{R}^n </math> עריכה
אי שוויון הצמצום סודקוב משמש כדי להעריך מספרי כיסוי על קבוצות <math>T \subset \mathbb{R}^n </math> במרחב האוקלידי. עבור תהליך גאוסיאני <math>X_t := \langle g,t \rangle, t\in T, g \sim N(0,I_n) </math> לכל <math>\varepsilon>0
</math> <math>\mathbb{E}\sup \langle g,t \rangle _{t\in T} \geq c\varepsilon \sqrt{\log N(T,\varepsilon)}</math>.
כתוצאה מאי שוויון זה, הוכיחו כי עבור פוליטיפ ב-<math>\mathbb{R}^n </math> שהוא אובייקט גאומטרי עם פאות שטוחות, וקוטרו קטן מאחד בעל <math>N</math> קודקודים ש - <math>\mathcal{N}(P,\varepsilon) \leq N^{c/\varepsilon^2} </math>.
שימושים נוספים עריכה
קוד תיקון שגיאות עריכה
טיעונים של מספרי כיסוי מופיעים רבות בשימושים בתורת הקודים ובקוד תיקון שגיאות. מספרי כיסוי מודדים את רמת המורכבות של קבוצה. לפיכך הלוגריתם של מספר כיסוי של קבוצה <math>K </math> <math>\log_2\mathcal{N}(K,\varepsilon) </math> מכונה מטריקת האנטרופיה של <math>K </math>.
הקשר בין מטריקת האנטרופיה וקידוד עריכה
יהי <math>(T,d) </math> מרחב מטרי, <math>K\subset T </math> תת-קבוצה במרחב. נגדיר את <math>\mathcal{C}(K,d,\varepsilon)</math> להיות המספר הקטן ביותר של ביטים המספיק כדי לציין כל נקודה <math>x \in K </math> בדיוק <math>\varepsilon</math> אז: <math>\log_2\mathcal{N}(K,\varepsilon)\leq \mathcal{C}(K,d,\varepsilon)\leq\lceil\log_2\mathcal{N}(K,\varepsilon/2)\rceil </math>.
ערובה עבור קוד תיקון שגיאות עריכה
בעזרת טיעוני ε-רשת על המרחב <math>\{ 0,1 \}^n </math> עם מרחק המינג ניתן להבטיח ערובה לקוד תיקון שגיאות.
נניח ש - <math>k,n </math> ו - <math>r </math> הם מספרים טבעיים כך ש - <math>n >= k + 2r\log_2(\frac{en} {2r}) </math> אז קיים קידון תיקוד שגיאות המקודד מחרוזות של <math>k </math>-ביטים לתוך מחרוזות באורך <math>n </math>-ביטים שיכול לתקן <math>r </math> שגיאות.
ניתן לראות דוגמה ליכולת של קוד לתקן שגיאות במשחק ההחלפות של ברלקאמפ. (אנ')
תורת האינפורמציה הקוונטית עריכה
תורת האינפורמציה הקוונטית היא ענף במדעי המחשב ופיזיקה המרחיב את תחום תורת המידע על ידי שילוב של מושגים מתורת הקוונטים העוסק בחילוץ מידע בקנה מידה מיקרוסקופי, המתייחס למידע בתור משהו פיזי המקודד לתוך מצב של מערכת קוונטית. בתורת המידע הקוונטית.
אוסזמאנייק, סוויקי והורדקי[2] השתמשו בטיעוני ε-רשת על מנת להפוך בעיות מורכבות על מרחבים רציפים לבעיות על קבוצות סופיות שאפשרו שימוש בטכניקות מהסתברות וקומבינטוריקה עבור הערכה של הקבוצות הללו.
קירוב אוניטרי של תכנון-<math>t </math> עריכה
הם כלי לשחזור המומנטים הסטטיסטים מדרגה לכל היותר <math>t </math> של מידת האר על החבורה האוניטרית[3] ויש להם שימושים רבים בתורת האינפורמציה הקוונטית[4][5][6].
בעבודתם הם הראו כי שיש קשר בין תכנון-<math>t </math> ו-קירוב אוניטרי של תכנון-t ל-ε-רשת וש-ε-רשת יכולה להגדיר <math>(\varepsilon t)-approximate\ t-design </math>. בעזרת קישור זה הם הראו בנייה חדשה ויעילה של פולינום קירוב לפונקציית דלתא של דיראק במרחב של ערוצים קוונטים (אנ').
אלגוריתמי קירוב עריכה
הר-פלד ורייכל[7] תיארו פרדיגמה אלגוריתמית הנקראת "רשת וגיזום" (net and prune) לתכנון אלגוריתמי קירוב עבור סוגים מסוימים של בעיות אופטימיזציה גאומטריות המוגדרות על קבוצות של נקודות במרחבים אוקלידיים.
האלגוריתם פועל באופן הבא:
1. בחירת נקודה אקראית: בחר נקודה אקראית <math>p </math> מקבוצת הנקודות, מצא את השכן הקרוב ביותר שלה <math>q
</math>, וקבע את <math>\varepsilon </math> להיות המרחק ביניהם <math>d(p,q) </math>.
2. בדיקת ערך האופטימום: בדוק האם <math>\varepsilon
</math> גדול או קטן (בקירוב) מערך פתרון האופטימום, באמצעות טכניקה ספציפית לבעיה הנפתרת.
3. גיזום:
- אם <math>\varepsilon </math> גדול, הסר מהקלט את הנקודות שהשכן הקרוב אליהן הוא במרחק גדול מ-<math>\varepsilon </math>.
- אם <math>\varepsilon </math> קטן, בנה ε-רשת <math>N </math>, והסר מהקלט את הנקודות שאינן ב-<math>N </math>.
בכל אחד מהמקרים, המספר הצפוי של הנקודות הנותרות פוחת בפקטור קבוע, כך שהזמן הכולל נשלט על ידי שלב הבדיקה. פרדיגמה זו מאפשרת לפתח אלגוריתמי קירוב מהירים עבור בעיות כמו ניתוח אשכולות - אלגוריתם k-מרכזים, מציאת זוג נקודות עם מרחק חציוני, ובעיות קשורות.
עץ רשת (net-tree), מערכת היררכית של רשתות, יכול לשמש במרחבים בעלי ממד הכפלה מוגבל לבניית פירוקי זוגות מופרדים היטב, ספנרים גאומטריים, וקירוב שכנים קרובים[8][9].
ראו גם עריכה
הערות שוליים עריכה
- ^ Z. D. Bai, Y. Q. Yin, Necessary and Sufficient Conditions for Almost Sure Convergence of the Largest Eigenvalue of a Wigner Matrix, The Annals of Probability 16, 1988-10-01 doi: 10.1214/aop/1176991594
- ^ Michał Oszmaniec, Adam Sawicki, Michał Horodecki, Epsilon-nets, unitary designs and random quantum circuits, arXiv.org, 2020-07-21 (ב־English)
- ^ Christoph Dankert, Richard Cleve, Joseph Emerson, Etera Livine, Exact and Approximate Unitary 2-Designs: Constructions and Applications, arXiv.org, 2006-06-20 (ב־English)
- ^ Hsin-Yuan Huang, Richard Kueng, John Preskill, Predicting Many Properties of a Quantum System from Very Few Measurements, Nature Physics 16, 2020-10, עמ' 1050–1057 doi: 10.1038/s41567-020-0932-7
- ^ Oleg Szehr, Frédéric Dupuis, Marco Tomamichel, Renato Renner, Decoupling with unitary approximate two-designs, New Journal of Physics 15, 2013-05-15, עמ' 053022 doi: 10.1088/1367-2630/15/5/053022
- ^ Anura Abeyesinghe, Igor Devetak, Patrick Hayden, Andreas Winter, The mother of all protocols: Restructuring quantum information's family tree, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 465, 2009-08-08, עמ' 2537–2563 doi: 10.1098/rspa.2009.0202
- ^ Sariel Har-Peled, Benjamin Adam Raichel, Net and prune, Proceedings of the forty-fifth annual ACM symposium on Theory of Computing 2, ACM, 2013-06, עמ' 605–614 doi: 10.1145/2488608.2488684
- ^ Sariel Har-Peled, Manor Mendel, Fast Construction of Nets in Low-Dimensional Metrics and Their Applications, SIAM Journal on Computing 35, 2006-01, עמ' 1148–1184 doi: 10.1137/S0097539704446281
- ^ Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms: New Orleans, LA, January 11 - 13, 2004, Philadelphia: Society for Industrial and Applied Mathematics, 2004, ISBN 978-0-89871-558-3