  This paper considers a noisy data structure recovery problem. The goal is to
investigate the following question: Given a noisy observation of a permuted
data set, according to which permutation was the original data sorted? The
focus is on scenarios where data is generated according to an isotropic
Gaussian distribution, and the noise is additive Gaussian with an arbitrary
covariance matrix. This problem is posed within a hypothesis testing framework.
The objective is to study the linear regime in which the optimal decoder has a
polynomial complexity in the data size, and it declares the permutation by
simply computing a permutation-independent linear function of the noisy
observations. The main result of the paper is a complete characterization of
the linear regime in terms of the noise covariance matrix. Specifically, it is
shown that this matrix must have a very flat spectrum with at most three
distinct eigenvalues to induce the linear regime. Several practically relevant
implications of this result are discussed, and the error probability incurred
by the decision criterion in the linear regime is also characterized. A core
technical component consists of using linear algebraic and geometric tools,
such as Steiner symmetrization.
