| Paper ID | D3-S2-T3.2 |
| Paper Title |
Retrieving Data Permutations from Noisy Observations: High and Low Noise Asymptotics |
| Authors |
Minoh Jeong, University of Minnesota, United States; Alex Dytso, New Jersey Institute of Technology, United States; Martina Cardone, University of Minnesota, United States |
| Session |
D3-S2-T3: Inference & Learning |
| Chaired Session: |
Wednesday, 14 July, 22:20 - 22:40 |
| Engagement Session: |
Wednesday, 14 July, 22:40 - 23:00 |
| 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.
|
