אפסילון רשת

הנקודות האדומות הן חלק מה - ε-רשת עבור המישור האוקלידי, כאשר ε הוא הרדיוס של הדיסקים הצהובים. הדיסקים הצהובים מכסים יחדיו את כל המרחב, ולכן מקיימים את ההגדרה של ε-רשת. הרדיוס של הדיסקים הכחולים הוא מחצית מזה של הצהובים, ולכן הם זרים זה לזה.

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

ε-רשת עוזרת לפשט מרחב מטרי בכך שהיא נותנת מספר סופי של נקודות שמקרבות את המרחב במידה מסוימת. קירובים אלה שימושיים בין היתר במרחבים מממד גבוה שם חישובים מדויקים יכולים להיות יקרים חישובית.

הגדרות

בהינתן מרחב מטרי $(X,d)$ ותת קבוצה $A\subset X$, $N\subset X$ היא ε-רשת של $A$ אם עבור כל נקודה $x\in A$ קיימת נקודה $n\in N$ כך ש - $d(x,n)\le \epsilon$. המשמעות היא שהאיחוד של הכדורים הפתוחים ברדיוס $\epsilon$, שמרכזיהם ב-$N$, מכסה את $A$ כולה.

מספר הכיסוי של $A$, שאותו מסמנים ב-$𝒩(A,d,\epsilon )$, הוא הגודל המינימלי של ε-רשת עבור הקבוצה $A$ במרחב המטרי $(X,d)$. מספר הכיסוי מודד מה המספר המינימלי של כדורים ברדיוס $\epsilon$ הנדרשים כדי לכסות את הקבוצה $A$.

דוגמאות

משושה מכוסה על ידי אפסילון רשת המורכבת משבעה מעגלים ולכן מספר הכיסוי של המחומש הוא 7 לכל היותר

כיסוי של משושה: המשושה $K$ עם צלע באורך 1 מכוסה על ידי שבעה עיגולים ברדיוס $\epsilon =1/2$ ולכן $𝒩(K,1/2)\le 7$.

כיסוי של קבוצה במרחב האוקלידי ${ℝ}^n$: תהי $K\subset {ℝ}^n$ ו-$\epsilon >0$ אז קיימים חסמים למספר הכיסוי של הקבוצה התלוי בקבוצה K וב-ε:

$\frac{|K|}{|\epsilon B_2^n|}\le 𝒩(K,\epsilon )\le \frac{|K+(\epsilon /2)B_2^n|}{|(\epsilon /2)B_2^n|}$ כאשר $\epsilon B_2^n$ הוא כדור ברדיוס $\epsilon$, והערך המוחלט מציין את מידת הקבוצה.

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

שימושים במתמטיקה

מטריצות אקראיות

בתורת המטריצות האקראיות ε-רשת משמשת להערכת הנורמה הספקטרלית של מטריצה אקראית.

נורמת האופרטור של מטריצה A היא $\Vert A\Vert =\underset{\Vert x\Vert =1}{\sup }\Vert Ax\Vert$ כאשר $\Vert x\Vert$ היא הנורמה האוקלידית של הווקטור $x$. על ידי כיסוי של ספרת היחידה $S^{n-1}$ ב-ε-רשת $N$. ניתן להעריך את נורמת האופרטור של המטריצה: $\Vert A\Vert \approx \underset{x\in N}{\max }\Vert Ax\Vert +\epsilon \Vert A\Vert$ כיוון ש-$N$ סופית ניתן להעריך את $\underset{x\in N}{\max }\Vert Ax\Vert$ על קבוצה סופית במקום להעריך את $\underset{\Vert x\Vert =1}{\sup }\Vert Ax\Vert$ על הקבוצה הרציפה $\{x\in X|\Vert x\Vert =1\}$ במרחב המטרי $X$.

גבולות בהסתברות

ε-רשת מאפשרות שליטה על הגבולות בהסתברות של נורמת האופרטור של מטריצות אקראיות. על ידי שליטה בגודל ε-רשת בשילוב עם אי שוויון בול ואי שוויוני ריכוז ניתן להעריך את ההסתברות ש-$\Vert A\Vert$ תהיה גדולה מסף מסוים. טכניקה זו שימושית בהוכחת תוצאות כמו משפט באי-ין.

משפט באי-ין (Bai-Yin)

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

משפט באי-ין החזק, חסם עליון

יהי $\xi$ משתנה מקרי ממשי עם תוחלת אפס, שונות 1 ומומנט רביעי סופי. ולכל $1\le i\le j$ תהי ${\xi }_{ij}$ סדרה משתנים בלתי תלויה בזהות המתפלגים זהה עם התפלגות $\xi$ וגם ${\xi }_{ij}={\xi }_{ji}$. תהי $M_n:=({\xi }_{ij}{)}_{1\le i,j\le n}$ המטריצה האקראית הנוצרת מהגוש העליון השמאלי בגודל $n\times n$ אז כמעט בוודאות מתקיים: $\underset{n\to \mathrm{\infty }}{\mathrm{lim\; sup}}\frac{\Vert M_n{\Vert }_{\text{op}}}{\sqrt{n}}\le 2$

משפט באי-ין, חסם תחתון

תהי $M$ מטריצה אקראית סימטרית ממשית, כאשר האלמנטים מעל האלכסון ${\xi }_{ij},i\le j$ הם בלתי תלויים במשותף, עם תוחלת אפס ושונות אחת, והם חסומים בגודלם על ידי $O(1)$. אז החציון (או הממוצע) של $\Vert M{\Vert }_{\text{op}}$ הוא לפחות: $(2-o(1))\sqrt{n}$.

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

תהליכים אקראיים

תהליכים אקראיים הם תהליכים שהתפתחותם תלויה בגורמים מקריים, ויש להם שימושים רבים מפיזיקה, ביואינפורמטיקה, שוק ההון ועוד. טיעוני ε-רשת משמשים להוכחת לאי שוויונים מרכזיים בתחום.

אי שוויון הצמצום סודקוב

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

יהי $(X_t{)}_{t\in T}$ תהליך אקראי גאוסי עם תוחלת אפס ותהי $d$ מטריקה על קבוצת האינדקס $T$ כך ש - $d(t,s)=\Vert X_t-X_s{\Vert }_L^2=(𝔼(|X_t-X_s|{)}^2{)}^{\frac{1}{2}}$ אז לכל $\epsilon >0$ קיים קבוע $c$ כך ש - $𝔼\sup (X_t{)}_{t\in T}\ge c\epsilon \sqrt{\log 𝒩(T,d,\epsilon )}$.

אי שוויון הצמצום של סודקוב ב-${ℝ}^n$

אי שוויון הצמצום סודקוב משמש כדי להעריך מספרי כיסוי על קבוצות $T\subset {ℝ}^n$ במרחב האוקלידי. עבור תהליך גאוסיאני $X_t:=⟨g,t⟩,t\in T,g\sim N(0,I_n)$ לכל $\epsilon >0$ $𝔼\sup ⟨g,t{⟩}_{t\in T}\ge c\epsilon \sqrt{\log N(T,\epsilon )}$.

כתוצאה מאי שוויון זה, הוכיחו כי עבור פוליטיפ ב-${ℝ}^n$ שהוא אובייקט גאומטרי עם פאות שטוחות, וקוטרו קטן מאחד בעל $N$ קודקודים ש - $𝒩(P,\epsilon )\le N^{c/{\epsilon }^2}$.

שימושים נוספים

קוד תיקון שגיאות

טיעונים של מספרי כיסוי מופיעים רבות בשימושים בתורת הקודים ובקוד תיקון שגיאות. מספרי כיסוי מודדים את רמת המורכבות של קבוצה. לפיכך הלוגריתם של מספר כיסוי של קבוצה $K$ ${\log }_2𝒩(K,\epsilon )$ מכונה מטריקת האנטרופיה של $K$.

הקשר בין מטריקת האנטרופיה וקידוד

יהי $(T,d)$ מרחב מטרי, $K\subset T$ תת-קבוצה במרחב. נגדיר את $𝒞(K,d,\epsilon )$ להיות המספר הקטן ביותר של ביטים המספיק כדי לציין כל נקודה $x\in K$ בדיוק $\epsilon$ אז: ${\log }_2𝒩(K,\epsilon )\le 𝒞(K,d,\epsilon )\le \lceil {\log }_2𝒩(K,\epsilon /2)\rceil$.

ערובה עבור קוד תיקון שגיאות

בעזרת טיעוני ε-רשת על המרחב $\{0,1{\}}^n$ עם מרחק המינג ניתן להבטיח ערובה לקוד תיקון שגיאות.

נניח ש - $k,n$ ו - $r$ הם מספרים טבעיים כך ש - $n>=k+2r{\log }_2(\frac{en}{2r})$ אז קיים קידון תיקוד שגיאות המקודד מחרוזות של $k$-ביטים לתוך מחרוזות באורך $n$-ביטים שיכול לתקן $r$ שגיאות.

ניתן לראות דוגמה ליכולת של קוד לתקן שגיאות במשחק ההחלפות של ברלקאמפ. תבנית:אנ

תורת האינפורמציה הקוונטית

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

אוסזמאנייק, סוויקי והורדקי השתמשו בטיעוני ε-רשת על מנת להפוך בעיות מורכבות על מרחבים רציפים לבעיות על קבוצות סופיות שאפשרו שימוש בטכניקות מהסתברות וקומבינטוריקה עבור הערכה של הקבוצות הללו.

קירוב אוניטרי של תכנון-$t$

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

בעבודתם הם הראו כי שיש קשר בין תכנון-$t$ ו-קירוב אוניטרי של תכנון-t ל-ε-רשת וש-ε-רשת יכולה להגדיר $(\epsilon t)-approximatet-design$. בעזרת קישור זה הם הראו בנייה חדשה ויעילה של פולינום קירוב לפונקציית דלתא של דיראק במרחב של ערוצים קוונטים תבנית:אנ.

אלגוריתמי קירוב

הר-פלד ורייכל תיארו פרדיגמה אלגוריתמית הנקראת "רשת וגיזום" (net and prune) לתכנון אלגוריתמי קירוב עבור סוגים מסוימים של בעיות אופטימיזציה גאומטריות המוגדרות על קבוצות של נקודות במרחבים אוקלידיים.

האלגוריתם פועל באופן הבא:

1. בחירת נקודה אקראית: בחר נקודה אקראית $p$ מקבוצת הנקודות, מצא את השכן הקרוב ביותר שלה $q$, וקבע את $\epsilon$ להיות המרחק ביניהם $d(p,q)$.

2. בדיקת ערך האופטימום: בדוק האם $\epsilon$ גדול או קטן (בקירוב) מערך פתרון האופטימום, באמצעות טכניקה ספציפית לבעיה הנפתרת.

3. גיזום:

   - אם $\epsilon$ גדול, הסר מהקלט את הנקודות שהשכן הקרוב אליהן הוא במרחק גדול מ-$\epsilon$.

   - אם $\epsilon$ קטן, בנה ε-רשת $N$, והסר מהקלט את הנקודות שאינן ב-$N$.

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

עץ רשת (net-tree), מערכת היררכית של רשתות, יכול לשמש במרחבים בעלי ממד הכפלה מוגבל לבניית פירוקי זוגות מופרדים היטב, ספנרים גאומטריים, וקירוב שכנים קרובים.

ראו גם

• Topics in random matrix theory - Terence Tao
• High dimensional probability book - Roman Vershynin
• מטריצות אקראיות
• ניתוח אשכולות