Retrieving Data Permutations from Noisy Observations: High and Low Noise Asymptotics

Minoh Jeong, Alex Dytso, Martina Cardone

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

This paper considers the problem of recovering the permutation of an n-dimensional random vector X observed in Gaussian noise. First, a general expression for the probability of error is derived when a linear decoder (i.e., linear estimator followed by a sorting operation) is used. The derived expression holds with minimal assumptions on the distribution of X and when the noise has memory. Second, for the case of isotropic noise (i.e., noise with a diagonal scalar covariance matrix), the rates of convergence of the probability of error are characterized in the high and low noise regimes. In the low noise regime, for every dimension n, the probability of error is shown to behave proportionally to \sigma, where \sigma is the noise standard deviation. Moreover, the slope is computed exactly for several distributions and it is shown to behave quadratically in n. In the high noise regime, for every dimension n, the probability of correctness is shown to behave as 1/\sigma, and the exact expression for the rate of convergence is also provided.

Original languageEnglish (US)
Title of host publication2021 IEEE International Symposium on Information Theory, ISIT 2021 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1100-1105
Number of pages6
ISBN (Electronic)9781538682098
DOIs
StatePublished - Jul 12 2021
Event2021 IEEE International Symposium on Information Theory, ISIT 2021 - Virtual, Melbourne, Australia
Duration: Jul 12 2021Jul 20 2021

Publication series

Name2021 IEEE International Symposium on Information Theory (ISIT)

Conference

Conference2021 IEEE International Symposium on Information Theory, ISIT 2021
Country/TerritoryAustralia
CityVirtual, Melbourne
Period7/12/217/20/21

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:
© 2021 IEEE.

Fingerprint

Dive into the research topics of 'Retrieving Data Permutations from Noisy Observations: High and Low Noise Asymptotics'. Together they form a unique fingerprint.

Cite this