论文标题
检测相关的高斯数据库
Detecting Correlated Gaussian Databases
论文作者
论文摘要
本文考虑了检测两个数据库（每个数据库）是否由$ n $用户组成的问题是相关的。在零假设下，数据库是独立的。在替代假设下，在未知行排列下，这些特征在数据库之间相关。开发了一个简单的测试，以表明检测可以在$ρ^2 \ of frac {1} {d} $上方实现。对于相反，使用截断的第二钟方法来确定在大约$ρ^2 \ of frac {1} {d \ sqrt {n}} $下方的检测是不可能的。将这些结果与相应的恢复问题进行了比较，该问题的目标是解码行排列，并且先前已显示了大约$ρ^2 \ 1 -n^{ - 4/d} $的相反结合。对于某些参数选择，检测可实现性限制的效果优于此恢复相反的结合，这表明在这种情况下，检测比恢复更容易。
This paper considers the problem of detecting whether two databases, each consisting of $n$ users with $d$ Gaussian features, are correlated. Under the null hypothesis, the databases are independent. Under the alternate hypothesis, the features are correlated across databases, under an unknown row permutation. A simple test is developed to show that detection is achievable above $ρ^2 \approx \frac{1}{d}$. For the converse, the truncated second moment method is used to establish that detection is impossible below roughly $ρ^2 \approx \frac{1}{d\sqrt{n}}$. These results are compared to the corresponding recovery problem, where the goal is to decode the row permutation, and a converse bound of roughly $ρ^2 \approx 1 - n^{-4/d}$ has been previously shown. For certain choices of parameters, the detection achievability bound outperforms this recovery converse bound, demonstrating that detection can be easier than recovery in this scenario.
