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

Ashwin Pananjady, Martin J. Wainwright, Thomas A. CourtadeIEEE Trans. Information Theory 2018 · DOI · OpenReview

Abstract

Consider a noisy linear observation model with an unknown permutation, based on observing y = Π* Ax* + w, where x* ∈ ℝ <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">d</sup> is an unknown vector, Π* is an unknown n x n permutation matrix, and w ∈ ℝ <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> 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 Π* is exactly and approximately recoverable. On the computational front, we show that the maximum likelihood estimate of Π* is NP-hard to compute for general d, while also providing a polynomial time algorithm when d = 1.
BibTeX
@article{pananjady2018linear,
  author = {Ashwin Pananjady and Martin J. Wainwright and Thomas A. Courtade},
  title = {{Linear Regression With Shuffled Data: Statistical and Computational Limits of Permutation Recovery}},
  journal = {IEEE Trans. Information Theory},
  year = {2018},
  doi = {10.1109/tit.2017.2776217},
}

Loading related content...

Figure