Graph-theoretic procedures for dimension identification
type: Item
instance of: scholarly article
title: Graph-theoretic procedures for dimension identification
zbMATH Open document ID: 1006.60024
author: A. J. Quiroz
author: M. R. Brito
author: J. E. Yukich
published in: Journal of Multivariate Analysis
publication date: 2002-07-08T00:00:00Z
review text: 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.
reviewed by: Pavel Froněk
Mathematics Subject Classification ID: 60F15
Mathematics Subject Classification ID: 62H30
Mathematics Subject Classification ID: 65C60
zbMATH DE Number: 1764694
zbMATH Keywords: proximity data
zbMATH Keywords: multidimensional scaling
zbMATH Keywords: \(k\)-nearest-neighbors graph
zbMATH Keywords: dimensionality reduction
MaRDI profile type: Publication
full work available at URL: jmva.2001.1992
OpenAlex ID: W1967417740
cites work: Q3327527
cites work: Connectivity of the mutual \(k\)-nearest-neighbor graph in clustering and outlier detection
cites work: Q3217346
cites work: Q4885394
cites work: Parallel concepts in graph theory
cites work: Nonmetric multidimensional scaling. A numerical method
cites work: Q3994387
cites work: Q3870155
cites work: Central limit theorems for some graphs in computational geometry.
cites work: Some Statistical Approaches to Multidimensional Scaling Data
cites work: Q3395931
cites work: Q4524432
DOI: 10.1006/JMVA.2001.1992
description: scientific article; zbMATH DE number 1764694