Graph-Theoretic Procedures for Dimension Identification

We consider the problem of identifying the dimension in which a sample of data points lives, when only their interpoint distances are known. We study as a random variable the average “reach” of vertices in the k-nearest-neighbors graph associated to the interpoint distance matrix, and we show how this variable can be used to accurately (from a probabilistic viewpoint) identify the unknown dimension at low computational cost. We discuss results that serve as the theoretical foundation for the methodology proposed. We illustrate how our method can help in dimension reduction procedures.