A Computational Transition for Detecting Multivariate Shuffled Linear Regression by Low-Degree Polynomials

In this paper, we study the problem of multivariate shuffled linear regression, where the correspondence between predictors and responses in a linear model is obfuscated by a latent permutation. Specifically, we investigate the modelY= (Π*XQ*+σZ)/√1+σ2, whereXis ann * dstandard Gaussian design matrix, Z is an n*m Gaussian noise matrix, Π*is an unknownn*npermutation matrix, andQ*is an unknownd * mon the Grassmanian manifold satisfyingQ*TQ*= Im. Consider the hypothesis testing problem of distinguishing this model from the case whereXandYare independent Gaussian random matrices of sizesn * dandn * m, respectively. Our results reveal a phase transition phenomenon in the performance oflow-degree polynomial algorithmsfor this task. (1) Whenm = o(d), we show that all degree-Dpolynomials fail to distinguish these two models even when σ = 0, provided withD4=o(d/m). (2) Whenm = dand σ = ω(1), we show that all degree-Dpolynomials fail to distinguish these two models provided withD=o(σ). (3) Whenm = dand σ =o(1), we show that there exists a constantdegree polynomial that strongly distinguish these two models. These results establish a smooth transition in the effectiveness of low-degree polynomial algorithms for this problem, highlighting the interplay between the dimensionsmandd, the noise level σ, and the computational complexity of the testing task.