arXiv:2511.06040v4 Announce Type: replace-cross
Abstract: We study the computational task of detecting and estimating correlated signals in a pair of spiked matrices $$ X=tfrac{lambda}{sqrt{n}} xu^{top}+W, quad Y=tfrac{mu}{sqrt{n}} yv^{top}+Z $$ where the spikes $x,y$ have correlation $rho$. Specifically, we consider two fundamental models: (1) Correlated spiked Wigner model with signal-to-noise ratio $lambda,mu$; (2) Correlated spiked $n*N$ Wishart (covariance) model with signal-to-noise ratio $sqrtlambda,sqrtmu$.
We propose an efficient detection and estimation algorithm based on counting a specific family of edge-decorated cycles. The algorithm’s performance is governed by the function $$ F(lambda,mu,rho,gamma)=maxBig{ frac{ lambda^2 }{ gamma }, frac{ mu^2 }{ gamma }, frac{ lambda^2 rho^2 }{ gamma-lambda^2+lambda^2 rho^2 } + frac{ mu^2 rho^2 }{ gamma-mu^2+mu^2 rho^2 } Big} ,. $$ We prove our algorithm succeeds for the correlated spiked Wigner model whenever $F(lambda,mu,rho,1)>1$, and succeeds for the correlated spiked Wishart model whenever $F(lambda,mu,rho,tfrac{n}{N})>1$. 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 results with evidence for a matching computational lower bound. In particular, we prove that when $F(lambda,mu,rho,1)<1$ for the correlated spiked Wigner model and when $F(lambda,mu,rho,tfrac{n}{N})<1$ for the spiked Wishart model, all algorithms based on low-degree polynomials fails to distinguish $({X},{Y})$ with two independent noise matrices. This strongly suggests that $F=1$ is the precise computation threshold for our models.