# Linear Regression with an Unknown Permutation: Statistical and Computational Limits

arXiv: https://arxiv.org/abs/1608.02902 · HTML: https://mlsanity.com/paper/1608.02902/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Aug 2016.

## Built on by (most cited first, 3 of 3)

- [Optimal Full Ranking from Pairwise Comparisons](https://mlsanity.com/paper/2101.08421/) (2021)
- [The graph alignment problem: fundamental limits and efficient algorithms](https://mlsanity.com/paper/2404.12418/) (2024)
- [Finite-Sample Inference for Sparsely Permuted Linear Regression](https://mlsanity.com/paper/2601.14872/) (2026)

## Abstract (arXiv)

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.