论文标题
在各向异性随机几何图中检测高维几何形状的阈值
Threshold for Detecting High Dimensional Geometry in Anisotropic Random Geometric Graphs
论文作者
论文摘要
在各向异性随机几何图模型中，顶点对应于从高维高斯分布中得出的点，如果它们的距离小于指定的阈值，则连接两个顶点。我们研究了何时可以在具有相同边缘概率的ERDőS-Rényi图之间进行假设检验。如果$ n $是顶点的数量，而$α$是特征值的向量，则Eldan和Mikulincer表明当$ N^3 \ gg（\ | | | | _2/\ | _2/\ | | _3 \ | _3）^6 $时，可以检测到检测（\ |α\ | _2/\ | |α\ | _4）^4 $。当$ n^3 \ ll（\ | | | | _2/\ |α\ | _3）^6 $时，我们表明检测是不可能的。
In the anisotropic random geometric graph model, vertices correspond to points drawn from a high-dimensional Gaussian distribution and two vertices are connected if their distance is smaller than a specified threshold. We study when it is possible to hypothesis test between such a graph and an Erdős-Rényi graph with the same edge probability. If $n$ is the number of vertices and $α$ is the vector of eigenvalues, Eldan and Mikulincer show that detection is possible when $n^3 \gg (\|α\|_2/\|α\|_3)^6$ and impossible when $n^3 \ll (\|α\|_2/\|α\|_4)^4$. We show detection is impossible when $n^3 \ll (\|α\|_2/\|α\|_3)^6$, closing this gap and affirmatively resolving the conjecture of Eldan and Mikulincer.
