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 language||English (US)|
|Title of host publication||2021 IEEE International Symposium on Information Theory, ISIT 2021 - Proceedings|
|Publisher||Institute of Electrical and Electronics Engineers Inc.|
|Number of pages||6|
|State||Published - Jul 12 2021|
|Event||2021 IEEE International Symposium on Information Theory, ISIT 2021 - Virtual, Melbourne, Australia|
Duration: Jul 12 2021 → Jul 20 2021
|Name||2021 IEEE International Symposium on Information Theory (ISIT)|
|Conference||2021 IEEE International Symposium on Information Theory, ISIT 2021|
|Period||7/12/21 → 7/20/21|
Bibliographical noteFunding Information:
The work of M. Jeong and M. Cardone was supported in part by the U.S. National Science Foundation under Grant CCF-1849757.
© 2021 IEEE.