TY - GEN
T1 - Lossy compression of permutations
AU - Wang, Da
AU - Mazumdar, Arya
AU - Wornell, Gregory W.
PY - 2014
Y1 - 2014
N2 - 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 ℓ1 distance of inversion vectors. We show that given two permutations, Kendall tau distance upper bounds the ℓ1 distance of inversion vectors and a scaled version of Kendall tau distance lower bounds the ℓ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.
AB - 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 ℓ1 distance of inversion vectors. We show that given two permutations, Kendall tau distance upper bounds the ℓ1 distance of inversion vectors and a scaled version of Kendall tau distance lower bounds the ℓ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.
UR - http://www.scopus.com/inward/record.url?scp=84906542585&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84906542585&partnerID=8YFLogxK
U2 - 10.1109/ISIT.2014.6874785
DO - 10.1109/ISIT.2014.6874785
M3 - Conference contribution
AN - SCOPUS:84906542585
SN - 9781479951864
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 11
EP - 15
BT - 2014 IEEE International Symposium on Information Theory, ISIT 2014
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2014 IEEE International Symposium on Information Theory, ISIT 2014
Y2 - 29 June 2014 through 4 July 2014
ER -