Abstract
This paper considers the problem of recovering the ranking of a data vector from noisy observations, up to a distortion. Specifically, the noisy observations consist of the original data vector corrupted by isotropic additive Gaussian noise, and the distortion is measured in terms of a distance function between the estimated ranking and the true ranking of the original data vector. First, it is shown that an optimal (in terms of error probability) decision rule for the estimation task simply outputs the ranking of the noisy observation. Then, the error probability incurred by such a decision rule is characterized in the low-noise regime, and shown to grow sublinearly with the noise standard deviation. This result highlights that the proposed approximate version of the ranking recovery problem is significantly less noise-dominated than the exact recovery considered in [Jeong, ISIT 2021].
| Original language | English (US) |
|---|---|
| Title of host publication | 2022 IEEE International Symposium on Information Theory, ISIT 2022 |
| Publisher | Institute of Electrical and Electronics Engineers Inc. |
| Pages | 1993-1998 |
| Number of pages | 6 |
| ISBN (Electronic) | 9781665421591 |
| DOIs | |
| State | Published - 2022 |
| Event | 2022 IEEE International Symposium on Information Theory, ISIT 2022 - Espoo, Finland Duration: Jun 26 2022 → Jul 1 2022 |
Publication series
| Name | IEEE International Symposium on Information Theory - Proceedings |
|---|---|
| Volume | 2022-June |
| ISSN (Print) | 2157-8095 |
Conference
| Conference | 2022 IEEE International Symposium on Information Theory, ISIT 2022 |
|---|---|
| Country/Territory | Finland |
| City | Espoo |
| Period | 6/26/22 → 7/1/22 |
Bibliographical note
Funding Information:The work of M. Jeong and M. Cardone was supported in part by the U.S. National Science Foundation under Grant CCF-1849757.
Publisher Copyright:
© 2022 IEEE.