A rate-distortion theory for permutation spaces
We investigate the lossy compression of the permutation space by analyzing the trade-off between the size of a source code and the distortion with respect to either Kendall tau distance or ℓ[subscript 1] distance of the inversion vectors. For both distortion measures, we characterize the rate-distor...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2014
|
| Online Access: | http://hdl.handle.net/1721.1/91130 https://orcid.org/0000-0001-9166-4758 |
| _version_ | 1826204433555390464 |
|---|---|
| author | Wang, Da Mazumdar, Arya Wornell, Gregory W. |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Wang, Da Mazumdar, Arya Wornell, Gregory W. |
| author_sort | Wang, Da |
| collection | MIT |
| description | We investigate the lossy compression of the permutation space by analyzing the trade-off between the size of a source code and the distortion with respect to either Kendall tau distance or ℓ[subscript 1] distance of the inversion vectors. For both distortion measures, we characterize the rate-distortion functions and provide explicit code designs that achieve them. Finally, we provide bounds on the higher order terms in the codebook size when the distortion levels lead to degenerate code rates (0 or 1). |
| first_indexed | 2024-09-23T12:54:59Z |
| format | Article |
| id | mit-1721.1/91130 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T12:54:59Z |
| publishDate | 2014 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/911302022-09-28T10:52:12Z A rate-distortion theory for permutation spaces Wang, Da Mazumdar, Arya Wornell, Gregory W. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Wang, Da Wornell, Gregory W. We investigate the lossy compression of the permutation space by analyzing the trade-off between the size of a source code and the distortion with respect to either Kendall tau distance or ℓ[subscript 1] distance of the inversion vectors. For both distortion measures, we characterize the rate-distortion functions and provide explicit code designs that achieve them. Finally, we provide bounds on the higher order terms in the codebook size when the distortion levels lead to degenerate code rates (0 or 1). United States. Air Force Office of Scientific Research (Grant FA9550-11-1-0183) National Science Foundation (U.S.) (Grant CCF-1017772) 2014-10-21T17:41:57Z 2014-10-21T17:41:57Z 2013-07 Article http://purl.org/eprint/type/ConferencePaper 978-1-4799-0446-4 2157-8095 http://hdl.handle.net/1721.1/91130 Wang, Da, Arya Mazumdar, and Gregory W. Wornell. “A Rate-Distortion Theory for Permutation Spaces.” 2013 IEEE International Symposium on Information Theory (July 2013). https://orcid.org/0000-0001-9166-4758 en_US http://dx.doi.org/10.1109/ISIT.2013.6620689 Proceedings of the 2013 IEEE International Symposium on Information Theory Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) MIT web domain |
| spellingShingle | Wang, Da Mazumdar, Arya Wornell, Gregory W. A rate-distortion theory for permutation spaces |
| title | A rate-distortion theory for permutation spaces |
| title_full | A rate-distortion theory for permutation spaces |
| title_fullStr | A rate-distortion theory for permutation spaces |
| title_full_unstemmed | A rate-distortion theory for permutation spaces |
| title_short | A rate-distortion theory for permutation spaces |
| title_sort | rate distortion theory for permutation spaces |
| url | http://hdl.handle.net/1721.1/91130 https://orcid.org/0000-0001-9166-4758 |
| work_keys_str_mv | AT wangda aratedistortiontheoryforpermutationspaces AT mazumdararya aratedistortiontheoryforpermutationspaces AT wornellgregoryw aratedistortiontheoryforpermutationspaces AT wangda ratedistortiontheoryforpermutationspaces AT mazumdararya ratedistortiontheoryforpermutationspaces AT wornellgregoryw ratedistortiontheoryforpermutationspaces |