Graph-theoretic procedures for dimension identification
ABSTRACT:
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 theoretical
foundation for the methodology proposed. We illustrate how our method can be of help in dimension
reduction procedures.
This is joint work with A. J. Quiroz and J. E. Yukich
