2021/05/07 by Minoh Jeong, Jeong, Minoh, Alex Dytso +3
Computer Science · Decision Sciences · Mathematics · #Distributed Sensor Networks and Detection Algorithms #FOS: Computer and information sciences #FOS: Electrical engineering #FOS: Mathematics #Information Theory (cs.IT) #Probability and Risk Models #Random Matrices and Applications #Signal Processing (eess.SP) #Statistics Theory (math.ST) #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.2105.03015
openalex publication_date 2021/05/07 · openalex created_date 2021/05/24 · openalex updated_date 2026/07/28
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 σ, where σ 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/σ, and the exact expression for the rate of convergence is also provided.