Linear Regression with an Unknown Permutation: Statistical and Computational Limits

Consider a noisy linear observation model with an unknown permutation, based on observing y = Pi^* A x^* + w, where x^* ∈ ℝd is an unknown vector, Pi^* is an unknown n × n permutation matrix, and w ∈ ℝn is additive Gaussian noise. We analyze the problem of permutation recovery in a random design setting in which the entries of the matrix A are drawn i.i.d. from a standard Gaussian distribution, and establish sharp conditions on the SNR, 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, while also providing a polynomial time algorithm when d =1.