对称相关尖峰维格模型中的算法阶段过渡
我们研究在一对尖峰Wigner矩阵中检测和估计相关信号的计算任务。 我们的模型由观测值组成:X = λ√(n) xx^⊤ + W ,Y = μ√(n) yy^⊤ + Z . 其中 x,y ∈R^n 是具有规范 x,y≈√(n) 和相关性 ⟨ x,y ⟩≈ρxy 的信号向量,而 W,Z 是独立的高斯噪声矩阵。 我们提出了一个高效的算法,每当F(λ,μ,ρ)>1,其中F(λ,μ,ρ)=max{λ,μ,λ^2 / 1-λ^2 + μ^2 ρ^2 ρ^2 + μ^2 ρ^2 ρ^2 ρ^2 ρ^2 / 1-μ^2 + μ^2 / 1-μ^2+μ^2 }。 我们的结果表明,算法可以利用尖峰之间的相关性来检测和估计信号,即使在那些有效地从X单独或y单独恢复x的系统中,被认为在计算上是不可行的。 我们用匹配的计算下界的证据来补充我们的算法结果。 特别是,我们证明,当F(λ,μ,ρ)<1,所有基于低度多项式算法的算法都未能用两个独立的Wigner矩阵来区分(X,Y)。 这种低度分析强烈表明F(λ,μ,ρ)=1是这个问题的精确计算阈值。
统计理论机器学习概率论机器学习 (统计)
