Linear Regression With Shuffled Data: Statistical and Computational Limits of Permutation Recovery
Lists
Only you see this
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...