关于从随机几何图中估算维度的注记

Nov, 2023

关于从随机几何图中估算维度的注记

A note on estimating the dimension from a random geometric graph

Caelan Atamanchuk, Luc Devroye, Gabor Lugosi

TL;DR给定以未知密度 f 为基础的 n 个 i.i.d. 随机向量 Xi 产生的随机几何图 Gn，估计其潜在空间的维度 d 的问题。研究发现，在满足条件 n^(3/2) r_n^d→∞和 r_n=o (1) 的情况下，存在一个估计器，其在概率意义下收敛于 d，对于所有满足∫f^5<∞的密度函数。条件允许极其稀疏的图，当 n^(3/2) r_n^d→0 时，图仅包含孤立边的概率很高。同时证明，在不对密度函数做任何条件的情况下，当 n r_n^d→∞和 r_n=o (1) 时，存在一个一致估计器来估计 d。

Abstract

Let $G_n$ be a random geometric graph with vertex set $[n]$ based on $n$ i.i.d.\ random vectors $X_1,\ldots,X_n$ drawn from an unknown density $f$ on $\R^d$. An edge $(i,j)$ is present when $\|X_i -X_j\| \le r_n$, for a given threshold $r_n$ possibly depending upon $n$, where $\| \cdot

random geometric graph estimating dimension adjacency matrix estimator sparsity

发现论文，激发创造

在随机图中测试高维几何

研究了如何检测随机图中的高维几何结构问题，提出了一种基于新量的近乎最优和高效的测试方法，并针对稠密和稀疏情况提出了检测界和估计维度的猜想。

Nov, 2014

随机几何图的色数

该论文研究了具有共同概率分布的独立随机点构成的随机几何图中色数和团数的关系，并确定了色数相对于团数的渐近比例，同时发现了一个尖锐的阈值。

Jan, 2011

软几何图的连通性

本文利用泊松分布定理研究了高维度的随机几何图上连接性的概率和孤立点的数量。

Nov, 2013

随机几何图的潜在距离估计

本文提出了一种基于样本点的谱估计器来构建随机几何图的方法，并证明其与非参数估计方法具有相同的收敛速率，同时提供了一种高效的计算方法，并通过该方法能够稳定地估计潜在空间的维度。

Sep, 2019

有向无权图中的度量恢复

本文展示了在至少需要 ω(n^(2/(d+2))) 的节点度时（其中 d 为维度），可以从有向无权图中恢复欧几里得度量和相关密度的估计，其中我们的估计器基于有向图上的随机游走的特征化和相应连续极限。

Nov, 2014

边独立随机图的谱

本文研究随机图模型及其邻接矩阵、拉普拉斯矩阵的谱性质，其中包括对 Erdős-Rényi 图的分析，证明了矩阵与其期望的偏差在一定条件下的上界，并对已有的结果进行了改进。

Apr, 2012

对二次随机点拟合椭球

研究拟合 n 个高斯随机向量到以原点为中心的椭球体边界问题，证明了它在 n 与 d 趋近于无穷大的情况下具有尖锐的可行性转变，并使用 Bartl&Mendelson 的关键结果和矩阵专业性质得出了当 n ≤ d²/C 时 (此处 C>0 是一个常数)，该问题是可行的且概率高。

Jul, 2023

基于广义最近邻图的 Rényi 熵和互信息估计

本文提出了一种基于非参数估计和广义最近邻图的计算 Renyi 熵和互信息的算法，证明了这种算法的几乎必然一致性和上限的收敛速度，并在实验中展示了其在独立子空间分析中的实用性。

Mar, 2010

随机图的浓缩和正则化

本文通过研究谱范数中邻接矩阵和拉普拉斯矩阵的浓度来探索随机图与其期望值之间的典型接近程度，其中包括不同概率的独立形成的具有 n 个顶点的不均匀 Erdos-Renyi 随机图，对于稀疏随机图，其期望度数小于 o（logn），需要使这种度数正则化，本文通过一些方法，例如重量重排或删除足够的边等操作来实现，演示了在社区检测问题中，集中结果的应用。

Jun, 2015

随机图中的独立集

本研究证明：在随机图中，最大独立集问题的组合结构会在独立集大小 k 超过 k nln (d)/d 这个点时发生相变，形成一个错综复杂的景象，局部搜索算法难以摆脱。这一现象通过 Metropolis 过程，即一个用于采样独立集的马尔可夫链实现了指数下界。

Jul, 2010