Section outline

  • Λήμμα Johnson-Lindenstrauss
    Ανισότητα Khintchine
    Ανισότητα Hanson-Wright
    Γρήγορος Μετασχηματισμός Johson-Lindenstrauss
    Aνισότητα Bernstein

    Επιπρόσθετα:
    Eίδαμε ότι μπορώ να βρω εκθετικά πολλά "σχεδόν κάθετα" μοναδιαία διανύσματα ( |<v_i,v_j>| <= ε) στον R^m, και ότι αυτό είναι το δυϊκό πρόβλημα των ε-(μη συνοχικών πινάκων) που είδαμε στο τρίτο μάθημα. Oρίστε διάφορες κατασκευές  και λίγα ιστορικά γεγονότα.


    1. Με τυχαία πρόσημα: Παίρνω n =  2^{( O( ε^2  m )} διανύσματα, με κάθε συντεταγμένη να είναι στην τύχη +- 1 (μπορείς να διαιρέσεις με ριζα( m ) για να γίνουν μοναδιαία). Είτε η ανισότητα του  Khintchine είτε τα φράγματα Chernoff θα δώσουν το ζητούμενο!
    2. Παίρνοντας τυχαία σημεία πάνω στη σφαίρα. Παίρνουμε n =  2^{( O( ε^2   m )} διανύσματα v_1, v_2 .... Κάθε συντεταγμένη του v_j είναι γκαουσιανή, και το κανονικοποιούμε ώστε  να γίνει μοναδιαίο. Η απόδειξη είναι παρόμοια με το Λήμμα Johnson-Lindenstrauss που είδαμε ((υπάρχει μια τεχνικά πιο απλή απόδειξη: παίρνεις κάθε συντεταγμένη γκαουσιάνη και ΔΕΝ κανονικοποιείς, αποδεικνύοντας την "σχεδόν καθετότητα" (αλλά με ε/10 αντί για ε, θα δείτε μετά γιατί) χωρίς να είναι μοναδιαία τα διανύσματα- ωστόσο, η συντριπτική πλειοψηφία θα έχουν μέτρο στο [1/10,  10], οπότε κρατάς μόνο αυτά και πετάς τα υπόλοιπα, κανονικοποιείς και τελείωσες! )).
    3. Με κώδικες επιδιόρθωσης σφαλμάτων:
        i. Όπως είδαμε στο δεύτερο μάθημα, αλλά αλλάζοντας λίγο τις παραμέτρους. Για την ακρίβεια, η κατασκευή στο δεύτερο μάθημα είναι κατασκευή με ε= 1/5 (γιατί; ).
        ii. Με κώδικες Reed-Solomon (πολυώνυμα χαμηλού βαθμού), όπως είδαμε στο πρόβλημα των ell_1 ε-βαρέων στοιχείων.
    4.Μέσω ισοτιμιών με πρώτους αριθμούς. Λέγεται και Κώδικας κινέζικων υπολοίπων. Είναι πάντα χειρότερος είτε από τις τυχαίες κατασκευές είτε από την κατασκευή με τον κώδικα Reed-Solomon. Στα θετικά είναι ότι μπορείς γρήγορα να βρεις το v_j αν σου ζητηθεί (όπως και στους Reed-Solomon κώδικες).
    5. Παίρνοντας στην τύχη έναν m x n υποπίνακα του n x n  πίνακα Walsh-Hadamard (ή οποιουδήποτε άλλου ορθοκανονικού πίνακα με εγγραφές <= 1/ρίζα (n) ), και παίρνοντας ως v_j τη j-οστή στήλη, αφού κανονικοποιήσουμε . Κλασικά, έχουμε n =   2^{( O( ε^2  *m )}. Η απόδειξη είναι μέσω της ανισότητας του Bernstein που είδαμε στο μάθημα.
    6. Μέσω πυρηνικών όπλων (δίνει το ίδιο αποτέλεσμα με Reed-Solomon): Με ένα σπουδαίο αποτέλεσμα του Deligne, ο οποίος απέδειξε μια εικασία του Weil (λέγεται/λεγόταν και υπόθεση του Ρίμαν για ελλειπτικές καμπύλες). Δείτε και εδώ την κατασκευή. Αυτή η ιδέα έχει εφαμοστεί ανεξάρτητα και στους κώδικες BCH.