Lossy compression of permutations
We investigate the lossy compression of permutations by analyzing the trade-off between the size of a source code and the distortion with respect to Kendall tau distance, Spearman's footrule, Chebyshev distance and ℓ[subscript 1] distance of inversion vectors. We show that given two permutation...
| Egile Nagusiak: | , , |
|---|---|
| Beste egile batzuk: | |
| Formatua: | Artikulua |
| Hizkuntza: | en_US |
| Argitaratua: |
Institute of Electrical and Electronics Engineers (IEEE)
2014
|
| Sarrera elektronikoa: | http://hdl.handle.net/1721.1/91133 https://orcid.org/0000-0001-9166-4758 |
| _version_ | 1826204333424771072 |
|---|---|
| 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 permutations by analyzing the trade-off between the size of a source code and the distortion with respect to Kendall tau distance, Spearman's footrule, Chebyshev distance and ℓ[subscript 1] distance of inversion vectors. We show that given two permutations, Kendall tau distance upper bounds the ℓ[subscript 1] distance of inversion vectors and a scaled version of Kendall tau distance lower bounds the ℓ[subscript 1] distance of inversion vectors with high probability, which indicates an equivalence of the source code designs under these two distortion measures. Similar equivalence is established for all the above distortion measures, every one of which has different operational significance and applications in ranking and sorting. These findings show that an optimal coding scheme for one distortion measure is effectively optimal for other distortion measures above. |
| first_indexed | 2024-09-23T12:52:56Z |
| format | Article |
| id | mit-1721.1/91133 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T12:52:56Z |
| publishDate | 2014 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/911332022-10-01T11:40:39Z Lossy compression of permutations 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 permutations by analyzing the trade-off between the size of a source code and the distortion with respect to Kendall tau distance, Spearman's footrule, Chebyshev distance and ℓ[subscript 1] distance of inversion vectors. We show that given two permutations, Kendall tau distance upper bounds the ℓ[subscript 1] distance of inversion vectors and a scaled version of Kendall tau distance lower bounds the ℓ[subscript 1] distance of inversion vectors with high probability, which indicates an equivalence of the source code designs under these two distortion measures. Similar equivalence is established for all the above distortion measures, every one of which has different operational significance and applications in ranking and sorting. These findings show that an optimal coding scheme for one distortion measure is effectively optimal for other distortion measures above. United States. Air Force Office of Scientific Research (Grant FA9550-11-1-0183) National Science Foundation (U.S.) (Grant CCF-1017772) 2014-10-21T17:56:53Z 2014-10-21T17:56:53Z 2014-06 Article http://purl.org/eprint/type/ConferencePaper 978-1-4799-5186-4 http://hdl.handle.net/1721.1/91133 Wang, Da, Arya Mazumdar, and Gregory W. Wornell. “Lossy Compression of Permutations.” 2014 IEEE International Symposium on Information Theory (June 2014). https://orcid.org/0000-0001-9166-4758 en_US http://dx.doi.org/10.1109/ISIT.2014.6874785 Proceedings of the 2014 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. Lossy compression of permutations |
| title | Lossy compression of permutations |
| title_full | Lossy compression of permutations |
| title_fullStr | Lossy compression of permutations |
| title_full_unstemmed | Lossy compression of permutations |
| title_short | Lossy compression of permutations |
| title_sort | lossy compression of permutations |
| url | http://hdl.handle.net/1721.1/91133 https://orcid.org/0000-0001-9166-4758 |
| work_keys_str_mv | AT wangda lossycompressionofpermutations AT mazumdararya lossycompressionofpermutations AT wornellgregoryw lossycompressionofpermutations |