Data spectroscopy: Eigenspaces of convolution operators and clustering

Abstract

This paper focuses on obtaining clustering information about a distribution from its i.i.d. samples. We develop theoretical results to understand and use clustering information contained in the eigenvectors of data adjacency matrices based on a radial kernel function with a sufficiently fast tail decay. In particular, we provide population analyses to gain insights into which eigenvectors should be used and when the clustering information for the distribution can be recovered from the sample. We learn that a fixed number of top eigenvectors might at the same time contain redundant clustering information and miss relevant clustering information. We use this insight to design the data spectroscopic clustering (DaSpec) algorithm that utilizes properly selected eigenvectors to determine the number of clusters automatically and to group the data accordingly. Our findings extend the intuitions underlying existing spectral techniques such as spectral clustering and Kernel Principal Components Analysis, and provide new understanding into their usability and modes of failure. Simulation studies and experiments on real-world data are conducted to show the potential of our algorithm. In particular, DaSpec is found to handle unbalanced groups and recover clusters of different shapes better than the competing methods.

Published in at http://dx.doi.org/10.1214/09-AOS700 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (2)

• Consistency of spectral clustering
• Horseshoes in multidimensional scaling and local kernel methods

Cited by in corpus (15)

• The geometry of kernelized spectral clustering
• Nonparametric Conditional Density Estimation in a High-Dimensional Regression Setting
• A Spectral Series Approach to High-Dimensional Nonparametric Regression
• Learning by Unsupervised Nonlinear Diffusion
• Co-clustering for directed graphs: the Stochastic co-Blockmodel and spectral algorithm Di-Sim
• Information Plane Analysis of Deep Neural Networks via Matrix-Based Renyi's Entropy and Tensor Kernels
• Clustering and Community Detection with Imbalanced Clusters
• Inverse Density as an Inverse Problem: The Fredholm Equation Approach
• Covariate Regularized Community Detection in Sparse Graphs
• The Geometry of Nonlinear Embeddings in Kernel Discriminant Analysis
• An Improved Bound for the Nystrom Method for Large Eigengap
• Learning latent causal graphs via mixture oracles
• Spectral Properties of Radial Kernels and Clustering in High Dimensions
• Uniform Consistency in Nonparametric Mixture Models
• Laplacian Mixture Modeling for Network Analysis and Unsupervised Learning on Graphs