Retrieving Data Permutations From Noisy Observations: Asymptotics

This paper studies the problem of data permutation recovery, where the goal is to estimate the ordering of an
$n$
-dimensional data vector given a noisy observation of it. The focus is on scenarios where the noise is additive Gaussian with an arbitrary known covariance matrix. The goal is to characterize the probability of error and its behavior when a linear decoder (that is, a linear estimator followed by a sorting operation) is employed. First, a general expression is derived for the probability of error when a linear decoder is used. The derived expression holds for any continuous distribution of the input data vector, and when the noise has memory. Then, the rates of convergence of the probability of error in the low-noise and high-noise regimes are investigated when a simple linear decoder is used. It is shown that in the low-noise regime, the probability of error can quadratically increase with
$n$
, and in the high-noise regime it behaves as
$1-1/n!$
for several distributions of interest. Finally, upper and lower bounds on the probability of correctness with respect to
$n$
are derived for the case of an i.i.d. data distribution and show that the rate of convergence is at least exponential in
$n$
. The results showcase that the permutation recovery problem is noise dominated, which motivates the study of more relaxed versions of the permutation recovery problem that are also discussed.