Optimal Compression of Unit Norm Vectors in the High Distortion Regime
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914665462759424 |
|---|---|
| author | Zhu, Heng Ghosh, Avishek Mazumdar, Arya |
| author_facet | Zhu, Heng Ghosh, Avishek Mazumdar, Arya |
| contents | Motivated by the need for communication-efficient distributed learning, we investigate the method for compressing a unit norm vector into the minimum number of bits, while still allowing for some acceptable level of distortion in recovery. This problem has been explored in the rate-distortion/covering code literature, but our focus is exclusively on the "high-distortion" regime. We approach this problem in a worst-case scenario, without any prior information on the vector, but allowing for the use of randomized compression maps. Our study considers both biased and unbiased compression methods and determines the optimal compression rates. It turns out that simple compression schemes are nearly optimal in this scenario. While the results are a mix of new and known, they are compiled in this paper for completeness. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_07941 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Optimal Compression of Unit Norm Vectors in the High Distortion Regime Zhu, Heng Ghosh, Avishek Mazumdar, Arya Information Theory Distributed, Parallel, and Cluster Computing Machine Learning Motivated by the need for communication-efficient distributed learning, we investigate the method for compressing a unit norm vector into the minimum number of bits, while still allowing for some acceptable level of distortion in recovery. This problem has been explored in the rate-distortion/covering code literature, but our focus is exclusively on the "high-distortion" regime. We approach this problem in a worst-case scenario, without any prior information on the vector, but allowing for the use of randomized compression maps. Our study considers both biased and unbiased compression methods and determines the optimal compression rates. It turns out that simple compression schemes are nearly optimal in this scenario. While the results are a mix of new and known, they are compiled in this paper for completeness. |
| title | Optimal Compression of Unit Norm Vectors in the High Distortion Regime |
| topic | Information Theory Distributed, Parallel, and Cluster Computing Machine Learning |
| url | https://arxiv.org/abs/2307.07941 |