A note on estimating the dimension from a random geometric graph
This addresses a theoretical problem in statistical inference for random geometric graphs, with incremental contributions to dimension estimation under sparse graph conditions.
The paper tackles the problem of estimating the dimension d from a random geometric graph without knowing the threshold or vectors, and shows that an estimator converges in probability to d under certain conditions, such as when n^{3/2} r_n^d → ∞ and r_n = o(1) for densities with ∫ f^5 < ∞, and also provides a consistent estimator without density conditions when n r_n^d → ∞ and r_n = o(1).
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 \|$ denotes Euclidean distance. We study the problem of estimating the dimension $d$ of the underlying space when we have access to the adjacency matrix of the graph but do not know $r_n$ or the vectors $X_i$. The main result of the paper is that there exists an estimator of $d$ that converges to $d$ in probability as $n \to \infty$ for all densities with $\int f^5 < \infty$ whenever $n^{3/2} r_n^d \to \infty$ and $r_n = o(1)$. The conditions allow very sparse graphs since when $n^{3/2} r_n^d \to 0$, the graph contains isolated edges only, with high probability. We also show that, without any condition on the density, a consistent estimator of $d$ exists when $n r_n^d \to \infty$ and $r_n = o(1)$.