Linear Regression With Shuffled Data: Statistical and Computational Limits of Permutation Recovery

Consider a noisy linear observation model with an unknown permutation, based on observing y = Pi*Ax* + w, where x* epsilon R-d is an unknown vector, Pi* is an unknown n x n permutation matrix, and w epsilon R-n is additive Gaussian noise. We analyze the problem of permutation recovery in a random design setting in which the entries of matrix A are drawn independently from a standard Gaussian distribution and establish sharp conditions on the signal-to-noise ratio, sample size n, and dimension d under which Pi* is exactly and approximately recoverable. On the computational front, we show that the maximum likelihood estimate of Pi* is NP-hard to compute for general d, while also providing a polynomial time algorithm when d = 1.