利用信号相关性，突破传统检测瓶颈，实现高效信号恢复。
The Algorithmic Phase Transition in Correlated Spiked Models
- 基于边标记环计数设计新算法，利用双矩阵信号相关性。
- 在λ²/γ>1或μ²/γ>1时可成功检测与估计信号。
- 适用于单侧难恢复但双侧相关场景，适合高维统计与机器学习研究者。
我们研究了在一对带相关尖峰的矩阵中检测和估计相关信号的计算任务：$ X=\tfracλ{\sqrt{n}} xu^{\top}+W, \quad Y=\tfracμ{\sqrt{n}} yv^{\top}+Z $，其中尖峰 $x,y$ 的相关系数为 $ρ$。考虑两类模型：(1) 相关尖峰威格纳模型，信噪比为 $λ,μ$；(2) 相关尖峰 $n×N$ 威沙特（协方差）模型，信噪比为 $\sqrtλ,\sqrtμ$。提出一种基于特定边标记环计数的高效检测与估计算法。其性能由函数 $$ F(λ,μ,ρ,γ)=\max\Big\{ \frac{ λ^2 }{ γ}, \frac{ μ^2 }{ γ}, \frac{ λ^2 ρ^2 }{ γ-λ^2+λ^2 ρ^2 } + \frac{ μ^2 ρ^2 }{ γ-μ^2+μ^2 ρ^2 } \Big\} $$ 决定。证明该算法在 $F(λ,μ,ρ,1)>1$ 时对威格纳模型有效，在 $F(λ,μ,ρ,\tfrac{n}{N})>1$ 时对威沙特模型有效。结果表明，即使单独从 $X$ 或 $Y$ 中无法高效恢复 $x$ 或 $y$，算法仍可借助尖峰相关性实现恢复。我们还提供了计算下界证据：当 $F<1$ 时，所有低次多项式算法无法区分 $(X,Y)$ 与独立噪声情形。这强烈暗示 $F=1$ 是精确的计算阈值。
原文摘要 · Abstract (English)
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)>1$, and succeeds for the correlated spiked Wishart model whenever $F(λ,μ,ρ,\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(λ,μ,ρ,1)<1$ for the correlated spiked Wigner model and when $F(λ,μ,ρ,\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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。