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 ^{*} A x^{*} + w , where x^{*} \in {\mathbb {R}} ^{d} is an unknown vector, \Pi ^{*} is an unknown n \times n permutation matrix, and w \in {\mathbb {R}} ^{n} is additive Gaussian noise. We ana...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information theory 2018-05, Vol.64 (5), p.3286-3300
Main Authors: Pananjady, Ashwin, Wainwright, Martin J., Courtade, Thomas A.
Format: Article
Language:English
Subjects:
Bioinformatics
Computation
Correspondence estimation
Data recovery
Estimation
Gaussian distribution
Genomics
information-theoretic bounds
Linear regression
Mathematical analysis
Mathematical model
Matrix methods
Maximum likelihood estimates
Noise measurement
Normal distribution
permutation recovery
Permutations
Polynomials
random gprojections
Random noise
Regression analysis
Robot sensing systems
Statistical analysis
unlabeled sensing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Consider a noisy linear observation model with an unknown permutation, based on observing y = \Pi ^{*} A x^{*} + w , where x^{*} \in {\mathbb {R}} ^{d} is an unknown vector, \Pi ^{*} is an unknown n \times n permutation matrix, and w \in {\mathbb {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 .
ISSN:0018-9448
1557-9654
DOI:10.1109/TIT.2017.2776217