{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:5451092"},"canonical_url":"https://search.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:5451092","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"Fast Quantized Johnson-Lindenstrauss Tranforms","abstract":"Η κβαντοποίηση έχει αναδειχθεί ως μία από τις βασικές τεχνικές για τη μείωση της κατανάλωσης μνήμης των μεγάλων γλωσσικών μοντέλων κατά τη διάρκεια της εξαγωγής συμπερασμάτων. Ένα χαρακτηριστικό παράδειγμα είναι το Quantized Johnson–Lindenstrauss (QJL), το οποίο συμπιέζει τις κρυφές μνήμες KV χρησιμοποιώντας ασύμμετρη κβαντοποίηση 1-bit, διατηρώντας παράλληλα κατά προσέγγιση τα εσωτερικά γινόμενα που απαιτούνται από τον μηχανισμό προσοχής. Πρόσφατες θεωρητικές και πρακτικές εργασίες στοχεύουν στην αντικατάσταση των πυκνών γκαουσιανών προβολών που χρησιμοποιούνται από τους προαναφερθέντες μετασχηματισμούς με πιο δομημένες ενσωματώσεις — όπως συνθέσεις τυχαιοποιημένων μετασχηματισμών Hadamard — διατηρώντας παράλληλα την ίδια διάσταση ένθεσης. Στην παρούσα διατριβή, εισάγουμε δύο κατασκευές που βασίζονται σε σύνθεση τυχαιοποιημένων μετασχηματισμών Hadamard, αν και με διαγώνιο Γκαουσιανό και όχι Rademacher στο δεύτερο στάδιο. Η πρώτη προσθέτει Γκαουσιανό dithering για την εξομάλυνση του κβαντιστή, ενώ η δεύτερη εισάγει μια τυχαία μετάθεση για την κανονικοποίηση της δομής συνδιακύμανσης των προκύπτοντων Γκαουσιανών μετρήσεων. Αποδυκνείουμε εγγυήσεις για τη διάσταση ένθεσης και τον χρόνο εκτέλεσης ανάλογες με αυτές του Fast JL στο μη κβαντισμένο πλαισίο. Η πρώτη κατασκευή επιτυγχάνει \\(m=O(\\varepsilon^{-2}\\log^2(d/\\delta))\\), ενώ η δεύτερη επιτυγχάνει \\(m=O(\\varepsilon^{-2}\\log(d/\\delta))\\) υπό έναν περιορισμό στο \\(m\\). Και οι δύο κατασκευές μπορούν να εφαρμοστούν σε χρόνο \\(O(d\\log d)\\).","abstract_html":"Η κβαντοποίηση έχει αναδειχθεί ως μία από τις βασικές τεχνικές για τη μείωση της κατανάλωσης μνήμης των μεγάλων γλωσσικών μοντέλων κατά τη διάρκεια της εξαγωγής συμπερασμάτων. Ένα χαρακτηριστικό παράδειγμα είναι το Quantized Johnson–Lindenstrauss (QJL), το οποίο συμπιέζει τις κρυφές μνήμες KV χρησιμοποιώντας ασύμμετρη κβαντοποίηση 1-bit, διατηρώντας παράλληλα κατά προσέγγιση τα εσωτερικά γινόμενα που απαιτούνται από τον μηχανισμό προσοχής. Πρόσφατες θεωρητικές και πρακτικές εργασίες στοχεύουν στην αντικατάσταση των πυκνών γκαουσιανών προβολών που χρησιμοποιούνται από τους προαναφερθέντες μετασχηματισμούς με πιο δομημένες ενσωματώσεις — όπως συνθέσεις τυχαιοποιημένων μετασχηματισμών Hadamard — διατηρώντας παράλληλα την ίδια διάσταση ένθεσης. Στην παρούσα διατριβή, εισάγουμε δύο κατασκευές που βασίζονται σε σύνθεση τυχαιοποιημένων μετασχηματισμών Hadamard, αν και με διαγώνιο Γκαουσιανό και όχι Rademacher στο δεύτερο στάδιο. Η πρώτη προσθέτει Γκαουσιανό dithering για την εξομάλυνση του κβαντιστή, ενώ η δεύτερη εισάγει μια τυχαία μετάθεση για την κανονικοποίηση της δομής συνδιακύμανσης των προκύπτοντων Γκαουσιανών μετρήσεων. Αποδυκνείουμε εγγυήσεις για τη διάσταση ένθεσης και τον χρόνο εκτέλεσης ανάλογες με αυτές του Fast JL στο μη κβαντισμένο πλαισίο. Η πρώτη κατασκευή επιτυγχάνει <span class=\"etd-inline-math\">m=O(\\varepsilon<sup>-2</sup>\\log<sup>2</sup>(d/&delta;))</span>, ενώ η δεύτερη επιτυγχάνει <span class=\"etd-inline-math\">m=O(\\varepsilon<sup>-2</sup>\\log(d/&delta;))</span> υπό έναν περιορισμό στο \\(m\\). Και οι δύο κατασκευές μπορούν να εφαρμοστούν σε χρόνο \\(O(d\\log d)\\).","abstract_has_math":true,"creators":["ΚΟΡΑΚΙΤΗΣ ΑΓΓΕΛΟΣ","KORAKITIS ANGELOS"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2026,"date_issued":"2026","date_published":"2026","updated_at":"2026-11-19T05:20:47Z","subjects":["Θετικές Επιστήμες","Science"],"languages":["English"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:5451092"],"render_values":[{"text":"uoadl:5451092","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/5451092","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/5451092","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Alib.uoa.gr%3Auoadl%3A5451092","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["ΚΟΡΑΚΙΤΗΣ ΑΓΓΕΛΟΣ","KORAKITIS ANGELOS"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2026"]},{"key":"dc:type","label":"Dc Type","values":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Θετικές Επιστήμες","Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:5451092","https://pergamos.lib.uoa.gr/uoa/dl/object/5451092"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Η κβαντοποίηση έχει αναδειχθεί ως μία από τις βασικές τεχνικές για τη μείωση της κατανάλωσης μνήμης των μεγάλων γλωσσικών μοντέλων κατά τη διάρκεια της εξαγωγής συμπερασμάτων. Ένα χαρακτηριστικό παράδειγμα είναι το Quantized Johnson–Lindenstrauss (QJL), το οποίο συμπιέζει τις κρυφές μνήμες KV χρησιμοποιώντας ασύμμετρη κβαντοποίηση 1-bit, διατηρώντας παράλληλα κατά προσέγγιση τα εσωτερικά γινόμενα που απαιτούνται από τον μηχανισμό προσοχής. Πρόσφατες θεωρητικές και πρακτικές εργασίες στοχεύουν στην αντικατάσταση των πυκνών γκαουσιανών προβολών που χρησιμοποιούνται από τους προαναφερθέντες μετασχηματισμούς με πιο δομημένες ενσωματώσεις — όπως συνθέσεις τυχαιοποιημένων μετασχηματισμών Hadamard — διατηρώντας παράλληλα την ίδια διάσταση ένθεσης. Στην παρούσα διατριβή, εισάγουμε δύο κατασκευές που βασίζονται σε σύνθεση τυχαιοποιημένων μετασχηματισμών Hadamard, αν και με διαγώνιο Γκαουσιανό και όχι Rademacher στο δεύτερο στάδιο. Η πρώτη προσθέτει Γκαουσιανό dithering για την εξομάλυνση του κβαντιστή, ενώ η δεύτερη εισάγει μια τυχαία μετάθεση για την κανονικοποίηση της δομής συνδιακύμανσης των προκύπτοντων Γκαουσιανών μετρήσεων. Αποδυκνείουμε εγγυήσεις για τη διάσταση ένθεσης και τον χρόνο εκτέλεσης ανάλογες με αυτές του Fast JL στο μη κβαντισμένο πλαισίο. Η πρώτη κατασκευή επιτυγχάνει \\(m=O(\\varepsilon^{-2}\\log^2(d/\\delta))\\), ενώ η δεύτερη επιτυγχάνει \\(m=O(\\varepsilon^{-2}\\log(d/\\delta))\\) υπό έναν περιορισμό στο \\(m\\). Και οι δύο κατασκευές μπορούν να εφαρμοστούν σε χρόνο \\(O(d\\log d)\\).","Quantization has emerged as one of the primary techniques for reducing the memory footprint of large language models during inference. A prominent example is Quantized Johnson–Lindenstrauss (QJL), which compresses KV caches using 1-bit asymmetric quantization while approximately preserving the inner products required by the attention mechanism. Recent theoretical and practical work aims at replacing the dense Gaussian projections used by the aforementioned transforms with more structured embeddings — such as compositions of randomized Hadamard transforms — while retaining the same embedding dimension. In this thesis, we introduce two constructions based on a composition of randomized Hadamard transforms, albeit with a Gaussian rather than Rademacher diagonal in the second stage. The first adds Gaussian dithering to smooth the quantizer, while the second inserts a random permutation to regularize the covariance structure of the resulting Gaussian measurements. We prove embedding-dimension and running-time guarantees analogous to those of Fast JL in the non-quantized setting. The first construction achieves \\(m=O(\\varepsilon^{-2}\\log^2(d/\\delta))\\), while the second achieves \\(m=O(\\varepsilon^{-2}\\log(d/\\delta))\\) under a restriction on \\(m\\). Both constructions can be applied in \\(O(d\\log d)\\) time."]},{"key":"dc:title","label":"Title","values":["Fast Quantized Johnson-Lindenstrauss Tranforms"]}]}],"canonical_facts":{"dc:creator":["ΚΟΡΑΚΙΤΗΣ ΑΓΓΕΛΟΣ","KORAKITIS ANGELOS"],"dc:date":["2026"],"dc:description":["Η κβαντοποίηση έχει αναδειχθεί ως μία από τις βασικές τεχνικές για τη μείωση της κατανάλωσης μνήμης των μεγάλων γλωσσικών μοντέλων κατά τη διάρκεια της εξαγωγής συμπερασμάτων. Ένα χαρακτηριστικό παράδειγμα είναι το Quantized Johnson–Lindenstrauss (QJL), το οποίο συμπιέζει τις κρυφές μνήμες KV χρησιμοποιώντας ασύμμετρη κβαντοποίηση 1-bit, διατηρώντας παράλληλα κατά προσέγγιση τα εσωτερικά γινόμενα που απαιτούνται από τον μηχανισμό προσοχής. Πρόσφατες θεωρητικές και πρακτικές εργασίες στοχεύουν στην αντικατάσταση των πυκνών γκαουσιανών προβολών που χρησιμοποιούνται από τους προαναφερθέντες μετασχηματισμούς με πιο δομημένες ενσωματώσεις — όπως συνθέσεις τυχαιοποιημένων μετασχηματισμών Hadamard — διατηρώντας παράλληλα την ίδια διάσταση ένθεσης. Στην παρούσα διατριβή, εισάγουμε δύο κατασκευές που βασίζονται σε σύνθεση τυχαιοποιημένων μετασχηματισμών Hadamard, αν και με διαγώνιο Γκαουσιανό και όχι Rademacher στο δεύτερο στάδιο. Η πρώτη προσθέτει Γκαουσιανό dithering για την εξομάλυνση του κβαντιστή, ενώ η δεύτερη εισάγει μια τυχαία μετάθεση για την κανονικοποίηση της δομής συνδιακύμανσης των προκύπτοντων Γκαουσιανών μετρήσεων. Αποδυκνείουμε εγγυήσεις για τη διάσταση ένθεσης και τον χρόνο εκτέλεσης ανάλογες με αυτές του Fast JL στο μη κβαντισμένο πλαισίο. Η πρώτη κατασκευή επιτυγχάνει \\(m=O(\\varepsilon^{-2}\\log^2(d/\\delta))\\), ενώ η δεύτερη επιτυγχάνει \\(m=O(\\varepsilon^{-2}\\log(d/\\delta))\\) υπό έναν περιορισμό στο \\(m\\). Και οι δύο κατασκευές μπορούν να εφαρμοστούν σε χρόνο \\(O(d\\log d)\\).","Quantization has emerged as one of the primary techniques for reducing the memory footprint of large language models during inference. A prominent example is Quantized Johnson–Lindenstrauss (QJL), which compresses KV caches using 1-bit asymmetric quantization while approximately preserving the inner products required by the attention mechanism. Recent theoretical and practical work aims at replacing the dense Gaussian projections used by the aforementioned transforms with more structured embeddings — such as compositions of randomized Hadamard transforms — while retaining the same embedding dimension. In this thesis, we introduce two constructions based on a composition of randomized Hadamard transforms, albeit with a Gaussian rather than Rademacher diagonal in the second stage. The first adds Gaussian dithering to smooth the quantizer, while the second inserts a random permutation to regularize the covariance structure of the resulting Gaussian measurements. We prove embedding-dimension and running-time guarantees analogous to those of Fast JL in the non-quantized setting. The first construction achieves \\(m=O(\\varepsilon^{-2}\\log^2(d/\\delta))\\), while the second achieves \\(m=O(\\varepsilon^{-2}\\log(d/\\delta))\\) under a restriction on \\(m\\). Both constructions can be applied in \\(O(d\\log d)\\) time."],"dc:identifier":["uoadl:5451092","https://pergamos.lib.uoa.gr/uoa/dl/object/5451092"],"dc:language":["English"],"dc:subject":["Θετικές Επιστήμες","Science"],"dc:title":["Fast Quantized Johnson-Lindenstrauss Tranforms"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-11-19T05:20:47Z"}