Linear regression with an unknown permutation: Statistical and computational limits
Linear regression with an unknown permutation: Statistical and computational limits
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 × 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 …