The Algorithmic Phase Transition in Correlated Spiked Models

We study the computational task of detecting and estimating correlated signals in a pair of spiked matrices X=tfracλ√n xutop+W, quad Y=tfracμ√n yvtop+Z where the spikes x,y have correlation ρ. Specifically, we consider two fundamental models: (1) Correlated spiked Wigner model with signal-to-noise ratio λ,μ; (2) Correlated spiked n*N Wishart (covariance) model with signal-to-noise ratio √λ,√μ. 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(λ,μ,ρ,γ)=maxBig frac λ2 γ , frac μ2 γ , frac λ2 ρ2 γ-λ2+λ2 ρ2 + frac μ2 ρ2 γ-μ2+μ2 ρ2 Big ,. We prove our algorithm succeeds for the correlated spiked Wigner model whenever F(λ,μ,ρ,1)>1, and succeeds for the correlated spiked Wishart model whenever F(λ,μ,ρ,tfracnN)>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(λ,μ,ρ,1)<1 for the correlated spiked Wigner model and when F(λ,μ,ρ,tfracnN)<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.