Linear Regression with an Unknown Permutation: Statistical and Computational Limits

Ashwin Pananjady, Martin J. Wainwright, Thomas A. Courtade

Consider a noisy linear observation model with an unknown permutation, based on observing $y={\Pi }^{\ast }A{x}^{\ast }+w$, where $x^{\ast }\in {\mathbb{R}}^d$ is an unknown vector, ${\Pi }^{\ast }$ is an unknow…