{"ID":2844660,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.06040","arxiv_id":"2511.06040","title":"The Algorithmic Phase Transition in Correlated Spiked Models","abstract":"We study the computational task of detecting and estimating correlated signals in a pair of spiked matrices $$ X=\\tfracλ{\\sqrt{n}} xu^{\\top}+W, \\quad Y=\\tfracμ{\\sqrt{n}} yv^{\\top}+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 $\\sqrtλ,\\sqrtμ$. 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(λ,μ,ρ,γ)=\\max\\Big\\{ \\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)\u003e1$, and succeeds for the correlated spiked Wishart model whenever $F(λ,μ,ρ,\\tfrac{n}{N})\u003e1$. 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)\u003c1$ for the correlated spiked Wigner model and when $F(λ,μ,ρ,\\tfrac{n}{N})\u003c1$ 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.","short_abstract":"We study the computational task of detecting and estimating correlated signals in a pair of spiked matrices $$ X=\\tfracλ{\\sqrt{n}} xu^{\\top}+W, \\quad Y=\\tfracμ{\\sqrt{n}} yv^{\\top}+Z $$ where the spikes $x,y$ have correlation $ρ$. Specifically, we consider two fundamental models: (1) Correlated spiked Wigner model with...","url_abs":"https://arxiv.org/abs/2511.06040","url_pdf":"https://arxiv.org/pdf/2511.06040v4","authors":"[\"Zhangsong Li\"]","published":"2025-11-08T15:23:44Z","proceeding":"math.ST","tasks":"[\"math.ST\",\"cs.LG\",\"math.PR\",\"stat.ML\"]","methods":"[]","has_code":false}