CaltechAUTHORS
  A Caltech Library Service

Bounds for Permutation Rate-Distortion

Farnoud, Farzad and Schwartz, Moshe and Bruck, Jehoshua (2016) Bounds for Permutation Rate-Distortion. IEEE Transactions on Information Theory, 62 (2). pp. 703-712. ISSN 0018-9448. http://resolver.caltech.edu/CaltechAUTHORS:20160119-151223798

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20160119-151223798

Abstract

We study the rate-distortion relationship in the set of permutations endowed with the Kendall t-metric and the Chebyshev metric. Our study is motivated by the application of permutation rate-distortion to the average-case and worst-case distortion analysis of algorithms for ranking with incomplete information and approximate sorting algorithms. For the Kendall τ-metric we provide bounds for small, medium, and large distortion regimes, while for the Chebyshev metric we present bounds that are valid for all distortions and are especially accurate for small distortions. In addition, for the Chebyshev metric, we provide a construction for covering codes.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1109/TIT.2015.2504521DOIArticle
http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=7342968.jsp?arnumber=6874784PublisherArticle
http://resolver.caltech.edu/CaltechAUTHORS:20150227-075642886Related ItemConference Paper
Additional Information:© 2015 IEEE. Manuscript received November 19, 2014; revised September 13, 2015; accepted November 16, 2015. Date of publication December 4, 2015; date of current version January 18, 2016. This work was supported in part by the National Science Foundation under Grant CIF-1218005 and in part by the Israel Science Foundation under Grant 130/14. This paper was presented in part at the 2014 IEEE International Symposium on Information Theory. The authors would like to thank the associate editor and anonymous reviewers, whose comments helped improve the presentation of the paper.
Funders:
Funding AgencyGrant Number
NSFCIF-1218005
Israeli Science Foundation130/14
Subject Keywords:Rank modulation, rate-distortion, covering codes, permutations, Kendall τ-metric, Chebyshev metric, ℓ∞-metric
Record Number:CaltechAUTHORS:20160119-151223798
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20160119-151223798
Official Citation:Farnoud Hassanzadeh, F.; Schwartz, M.; Bruck, J., "Bounds for Permutation Rate-Distortion," in Information Theory, IEEE Transactions on , vol.62, no.2, pp.703-712, Feb. 2016 doi: 10.1109/TIT.2015.2504521
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:63776
Collection:CaltechAUTHORS
Deposited By: Ruth Sustaita
Deposited On:19 Jan 2016 23:35
Last Modified:19 Jan 2016 23:35

Repository Staff Only: item control page