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

Abstract

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 model $Y=\frac{1}{\sqrt{1+\ddot{I}{ƒ}^2}}({\hat{I}}_{\ast }X{Q}_{\ast }+\ddot{I}ƒZ)$, where $X$ is an $n\ast d$ standard Gaussian design matrix, $Z$ is an $n\ast m$ Gaussian noise matrix, ${\hat{I}}_{\ast }$ is an unknown $n\ast n$ permutation matrix, and $Q_{\ast }$ is an unknown $d\ast m$ on the Grassmanian manifold satisfying $Q_{\ast }^{\top }{Q}_{\ast }={\mathbb{I}}_m$. Consider the hypothesis testing problem of distinguishing this model from the case where $X$ and $Y$ are independent Gaussian random matrices of sizes $n\ast d$ and $n\ast m$, respectively. Our results reveal a phase transition phenomenon in the performance of low-degree polynomial algorithms for this task. (1) When $m=o(d)$, we show that all degree-$D$ polynomials fail to distinguish these two models even when $\ddot{I}ƒ=0$, provided with $D^4=o\left(\frac{d}{m}\right)$. (2) When $m=d$ and $\ddot{I}ƒ=\ddot{I}‰(1)$, we show that all degree-$D$ polynomials fail to distinguish these two models provided with $D=o(\ddot{I}ƒ)$. (3) When $m=d$ and $\ddot{I}ƒ=o(1)$, we show that there exists a constant-degree 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 dimensions $m$ and $d$, the noise level $\ddot{I}ƒ$, and the computational complexity of the testing task.

27 pages; improved exposition