Linear Regression with an Unknown Permutation: Statistical and Computational Limits

2016/08/09 by Pananjady, Ashwin, Wainwright, Martin J., Courtade, Thomas A.
#FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Machine Learning (stat.ML) #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.1608.02902

Abstract

Consider a noisy linear observation model with an unknown permutation, based on observing y = Π^* A x^* + w, where x^* ∈ ℝ^d is an unknown vector, Π^* is an unknown n × n permutation matrix, and w ∈ ℝⁿ 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 Π^* is exactly and approximately recoverable. On the computational front, we show that the maximum likelihood estimate of Π^* is NP-hard to compute, while also providing a polynomial time algorithm when d =1.

Related

• Sharp Information-Theoretic Thresholds for Shuffled Linear Regression
• Recovering Data Permutations from Noisy Observations: The Linear Regime
• Retrieving Data Permutations from Noisy Observations: High and Low Noise Asymptotics
• A computational transition for detecting multivariate shuffled linear regression by low-degree polynomials
• Permuted and Unlinked Monotone Regression in ℝ^d: an approach based on mixture modeling and optimal transport