All Dates/Times are Australian Eastern Standard Time (AEST)

Technical Program

Paper Detail

Paper IDD3-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.