Graph-theoretic procedures for dimension identification (Q1604619)

The matrix \(D\) of dissimilarity or proximity data is considered. The main problem is to find a dimension \(d\) and a set of points in \(\mathbb{R}^d\), such that the Euclidean interpoint distances between the points are close to the entries in \(D\) (multidimensional scaling). The authors consider a graph theoretic tool, that can be useful for the identification of dimension \(d\geq 1\). The \(k\)-nearest-neighbors graph, which can be built from \(D\), is considered. The vertices in this graph become more ``interconnected'' as the dimension increases. The average reach represents here the measure of ``interconnectedness''. The average reach is, in expectation, an increasing function of the dimension of the data. A Monte Carlo experiment is used to validate this intuition. A simple procedure, based on one of the average reaches, for assigning a dimension between 2 and 5, is presented. The average reach converges for i.i.d. data having a continuous density to a constant, which represents the average number of points reachable for an arbitrary point adjoined to a homogeneous Poisson process of the unit intensity in \(\mathbb{R}^d\). The asymptotic normality of the reach statistics is studied.