Title:The Algorithmic Phase Transition in Symmetric Correlated Spiked Wigner Model

Abstract:We study the computational task of detecting and estimating correlated signals in a pair of spiked Wigner matrices. Our model consists of observations
$$
X = \tfrac{\lambda}{\sqrt{n}} xx^{\top} + W \,, \quad Y = \tfrac{\mu}{\sqrt{n}} yy^{\top} + Z \,.
$$
where $x,y \in \mathbb R^n$ are signal vectors with norm $\|x\|,\|y\| \approx\sqrt{n}$ and correlation $\langle x,y \rangle \approx \rho\|x\|\|y\|$, while $W,Z$ are independent Gaussian noise matrices. We propose an efficient algorithm that succeeds whenever $F(\lambda,\mu,\rho)>1$, where
$$
F(\lambda,\mu,\rho)=\max\Big\{ \lambda,\mu, \frac{ \lambda^2 \rho^2 }{ 1-\lambda^2+\lambda^2 \rho^2 } + \frac{ \mu^2 \rho^2 }{ 1-\mu^2+\mu^2 \rho^2 } \Big\} \,.
$$
Our result shows that an algorithm can leverage the correlation between the spikes to detect and estimate the signals even in regimes where efficiently recovering either $x$ from $X$ alone or $y$ from $Y$ alone is believed to be computationally infeasible.
We complement our algorithmic result with evidence for a matching computational lower bound. In particular, we prove that when $F(\lambda,\mu,\rho)<1$, all algorithms based on {\em low-degree polynomials} fails to distinguish $(X,Y)$ with two independent Wigner matrices. This low-degree analysis strongly suggests that $F(\lambda,\mu,\rho)=1$ is the precise computation threshold for this problem.