Information and dimensionality of anisotropic random geometric graphs
Information and dimensionality of anisotropic random geometric graphs
复制标题
各向异性随机几何图的信息和维数
DOI：
--
复制
发表时间：
2016
影响因子：
--
通讯作者：
Dan Mikulincer
中科院分区：
文献类型：
--
作者：
Ronen Eldan;Dan Mikulincer
研究了随机图中高维非各向同性几何结构的检测问题。也就是说，我们研究了一个随机几何图的模型，其中顶点对应于随机生成的点，独立于非各向同性的d维高斯分布，两个顶点连接，如果它们之间的距离小于一些预先指定的阈值。我们得到新的概念的维数依赖于高斯分布的协方差的特征值。如果α表示特征值向量，n是顶点数，则数量\（\left（\frac {\left \lVert \alpha \right \rVert _2}{\left \lVert \alpha \right \rVert _3}\right）^6/n^3\）和\（\left（\frac {\left \lVert \alpha \right \rVert _2}{\left \lVert \alpha \right \rVert _4}\right）^4/n^3\）确定检测可能性的上限和下限。这概括了Bubeck、Ding、Racz和Bubeck等人的第一位指定作者最近的结果（Random Struct Algoritm 49（3）：503-532，2016），该结果表明量d n3决定了各向同性几何的检测边界。我们的方法涉及傅立叶分析和特征函数理论来研究模型的潜在概率。下界的证明使用信息论工具，基于Bubeck和Ganguly提出的方法（Int Math Res Not 2018（2）：588-606，2016）。
This paper deals with the problem of detecting non-isotropic high-dimensional geometric structure in random graphs. Namely, we study a model of a random geometric graph in which vertices correspond to points generated randomly and independently from a non-isotropic d-dimensional Gaussian distribution, and two vertices are connected if the distance between them is smaller than some pre-specified threshold. We derive new notions of dimensionality which depend upon the eigenvalues of the covariance of the Gaussian distribution. If α denotes the vector of eigenvalues, and n is the number of vertices, then the quantities \(\left (\frac {\left \lVert \alpha \right \rVert _2}{\left \lVert \alpha \right \rVert _3}\right )^6/n^3\) and \(\left (\frac {\left \lVert \alpha \right \rVert _2}{\left \lVert \alpha \right \rVert _4}\right )^4/n^3\) determine upper and lower bounds for the possibility of detection. This generalizes a recent result by Bubeck, Ding, Racz and the first named author from Bubeck et al. (Random Struct Algoritm 49(3):503–532, 2016) which shows that the quantity d∕n3 determines the boundary of detection for isotropic geometry. Our methods involve Fourier analysis and the theory of characteristic functions to investigate the underlying probabilities of the model. The proof of the lower bound uses information theoretic tools, based on the method presented in Bubeck and Ganguly (Int Math Res Not 2018(2):588–606, 2016).