{"id":2911,"date":"2025-04-07T07:02:33","date_gmt":"2025-04-07T07:02:33","guid":{"rendered":"https:\/\/mailitics.com\/index.php\/2025\/04\/07\/2504-03097\/"},"modified":"2025-04-07T07:02:33","modified_gmt":"2025-04-07T07:02:33","slug":"2504-03097","status":"publish","type":"post","link":"https:\/\/mailitics.com\/index.php\/2025\/04\/07\/2504-03097\/","title":{"rendered":"A computational transition for detecting multivariate shuffled linear regression by low-degree polynomials"},"content":{"rendered":"

A computational transition for detecting multivariate shuffled linear regression by low-degree polynomials
\n \t

\n
<\/BR>
\n
\n \t

\n
<\/BR><\/p>\n

arXiv:2504.03097v1 Announce Type: new
\nAbstract: 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=tfrac{1}{sqrt{1+sigma^2}}(Pi_* X Q_* + sigma Z)$, where $X$ is an $n*d$ standard Gaussian design matrix, $Z$ is an $n*m$ Gaussian noise matrix, $Pi_*$ is an unknown $n*n$ permutation matrix, and $Q_*$ is an unknown $d*m$ on the Grassmanian manifold satisfying $Q_*^{top} Q_* = mathbb I_m$.
\n Consider the hypothesis testing problem of distinguishing this model from the case where $X$ and $Y$ are independent Gaussian random matrices of sizes $n*d$ and $n*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 $sigma=0$, provided with $D^4=obig( tfrac{d}{m} big)$. (2) When $m=d$ and $sigma=omega(1)$, we show that all degree-$D$ polynomials fail to distinguish these two models provided with $D=o(sigma)$. (3) When $m=d$ and $sigma=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 $sigma$, and the computational complexity of the testing task.<\/div>\n

\t

\n
<\/BR>
\n Zhangsong Li
\n \t

\n
<\/BR>
\nGo to original source<\/a>
\n \t

\n
<\/BR><\/p>\n","protected":false},"excerpt":{"rendered":"

A computational transition for detecting multivariate shuffled linear regression by low-degree polynomials arXiv:2504.03097v1 Announce Type: new 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=tfrac{1}{sqrt{1+sigma^2}}(Pi_* X Q_* + […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[62,113,420,190,112,191],"tags":[1764,2291,2292],"class_list":["post-2911","post","type-post","status-publish","format-standard","hentry","category-aimldsaimlds","category-cs-lg","category-math-pr","category-math-st","category-stat-ml","category-stat-th","tag-degree","tag-sigma","tag-transition"],"_links":{"self":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/posts\/2911"}],"collection":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/comments?post=2911"}],"version-history":[{"count":0,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/posts\/2911\/revisions"}],"wp:attachment":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/media?parent=2911"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/categories?post=2911"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/tags?post=2911"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}