Compression in the Space of Permutations

Da Wang; Arya Mazumdar; Gregory W. Wornell

doi:10.1109/TIT.2015.2485270

Compression in the Space of Permutations

Da Wang, Arya Mazumdar, Gregory W. Wornell

Electrical and Computer Engineering

Research output: Contribution to journal › Article › peer-review

8 Scopus citations

Abstract

We investigate lossy compression (source coding) of data in the form of permutations. This problem has direct applications in the storage of ordinal data or rankings, and in the analysis of sorting algorithms. We analyze the rate-distortion characteristic for the permutation space under the uniform distribution, and the minimum achievable rate of compression that allows a bounded distortion after recovery. Our analysis is with respect to different practical and useful distortion measures, including Kendall tau distance, Spearman's footrule, Chebyshev distance, and inversion-ℓ₁ distance. We establish equivalence of source code designs under certain distortions and show simple explicit code designs that incur low encoding/decoding complexities and are asymptotically optimal. Finally, we show that for the Mallows model, a popular nonuniform ranking model on the permutation space, both the entropy and the maximum distortion at zero rate are much lower than the uniform counterparts, which motivates the future design of efficient compression schemes for this model.

Original language	English (US)
Article number	7286821
Pages (from-to)	6417-6431
Number of pages	15
Journal	IEEE Transactions on Information Theory
Volume	61
Issue number	12
DOIs	https://doi.org/10.1109/TIT.2015.2485270
State	Published - Dec 1 2015

Bibliographical note

Funding Information:
This work was supported in part by the National Science Foundation under Grant CCF-1017772 and Grant CCF-1318093, and in part by the Air Force Office of Scientific Research under Grant FA9550-11-1-0183. The authors are grateful to an anonymous reviewer whose comment prompted an important correction to an earlier version of this paper.

Keywords

lossy compressions
mallows model
partial sorting
permutation space

Access

10.1109/TIT.2015.2485270

Fingerprint Dive into the research topics of 'Compression in the Space of Permutations'. Together they form a unique fingerprint.

Cite this

@article{d19acf9b9cd449bc96795fa534fe8305,

title = "Compression in the Space of Permutations",

abstract = "We investigate lossy compression (source coding) of data in the form of permutations. This problem has direct applications in the storage of ordinal data or rankings, and in the analysis of sorting algorithms. We analyze the rate-distortion characteristic for the permutation space under the uniform distribution, and the minimum achievable rate of compression that allows a bounded distortion after recovery. Our analysis is with respect to different practical and useful distortion measures, including Kendall tau distance, Spearman's footrule, Chebyshev distance, and inversion-ℓ1 distance. We establish equivalence of source code designs under certain distortions and show simple explicit code designs that incur low encoding/decoding complexities and are asymptotically optimal. Finally, we show that for the Mallows model, a popular nonuniform ranking model on the permutation space, both the entropy and the maximum distortion at zero rate are much lower than the uniform counterparts, which motivates the future design of efficient compression schemes for this model.",

keywords = "lossy compressions, mallows model, partial sorting, permutation space",

author = "Da Wang and Arya Mazumdar and Wornell, {Gregory W.}",

note = "Funding Information: This work was supported in part by the National Science Foundation under Grant CCF-1017772 and Grant CCF-1318093, and in part by the Air Force Office of Scientific Research under Grant FA9550-11-1-0183. The authors are grateful to an anonymous reviewer whose comment prompted an important correction to an earlier version of this paper.",

year = "2015",

month = dec,

day = "1",

doi = "10.1109/TIT.2015.2485270",

language = "English (US)",

volume = "61",

pages = "6417--6431",

journal = "IEEE Transactions on Information Theory",

issn = "0018-9448",

publisher = "IEEE",

number = "12",

}

TY - JOUR

T1 - Compression in the Space of Permutations

AU - Wang, Da

AU - Mazumdar, Arya

AU - Wornell, Gregory W.

N1 - Funding Information: This work was supported in part by the National Science Foundation under Grant CCF-1017772 and Grant CCF-1318093, and in part by the Air Force Office of Scientific Research under Grant FA9550-11-1-0183. The authors are grateful to an anonymous reviewer whose comment prompted an important correction to an earlier version of this paper.

PY - 2015/12/1

Y1 - 2015/12/1

N2 - We investigate lossy compression (source coding) of data in the form of permutations. This problem has direct applications in the storage of ordinal data or rankings, and in the analysis of sorting algorithms. We analyze the rate-distortion characteristic for the permutation space under the uniform distribution, and the minimum achievable rate of compression that allows a bounded distortion after recovery. Our analysis is with respect to different practical and useful distortion measures, including Kendall tau distance, Spearman's footrule, Chebyshev distance, and inversion-ℓ1 distance. We establish equivalence of source code designs under certain distortions and show simple explicit code designs that incur low encoding/decoding complexities and are asymptotically optimal. Finally, we show that for the Mallows model, a popular nonuniform ranking model on the permutation space, both the entropy and the maximum distortion at zero rate are much lower than the uniform counterparts, which motivates the future design of efficient compression schemes for this model.

AB - We investigate lossy compression (source coding) of data in the form of permutations. This problem has direct applications in the storage of ordinal data or rankings, and in the analysis of sorting algorithms. We analyze the rate-distortion characteristic for the permutation space under the uniform distribution, and the minimum achievable rate of compression that allows a bounded distortion after recovery. Our analysis is with respect to different practical and useful distortion measures, including Kendall tau distance, Spearman's footrule, Chebyshev distance, and inversion-ℓ1 distance. We establish equivalence of source code designs under certain distortions and show simple explicit code designs that incur low encoding/decoding complexities and are asymptotically optimal. Finally, we show that for the Mallows model, a popular nonuniform ranking model on the permutation space, both the entropy and the maximum distortion at zero rate are much lower than the uniform counterparts, which motivates the future design of efficient compression schemes for this model.

KW - lossy compressions

KW - mallows model

KW - partial sorting

KW - permutation space

UR - http://www.scopus.com/inward/record.url?scp=84959343904&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84959343904&partnerID=8YFLogxK

U2 - 10.1109/TIT.2015.2485270

DO - 10.1109/TIT.2015.2485270

M3 - Article

AN - SCOPUS:84959343904

VL - 61

SP - 6417

EP - 6431

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

SN - 0018-9448

IS - 12

M1 - 7286821

ER -

Compression in the Space of Permutations

Abstract

Bibliographical note

Keywords

Access

Other files and links

Cite this