Clustering Based on Pairwise Distances When the Data is of Mixed Dimensions

In the context of clustering, we consider a generative model in a Euclidean ambient space with clusters of different shapes, dimensions, sizes, and densities. In an asymptotic setting where the number of points becomes large, we obtain theoretical guaranties for some emblematic methods based on pairwise distances: a simple algorithm based on the extraction of connected components in a neighborhood graph; hierarchical clustering with single linkage; and the spectral clustering method of Ng, Jordan, and Weiss. The methods are shown to enjoy some near-optimal properties in terms of separation between clusters and robustness to outliers. The local scaling method of Zelnik-Manor and Perona is shown to lead to a near-optimal choice for the scale in the first and third methods. We also provide a lower bound on the spectral gap to consistently choose the correct number of clusters in the spectral method.