Publication 15-CNA-007
A Variational Approach to the Consistency of Spectral Clustering
Nicolas García Trillos
Department of Mathematical Sciences
Carnegie Mellon University
Pittsburgh, PA 15213
ngarciat@andrew.cmu.edu
Dejan Slepčev
Department of Mathematical Sciences
Carnegie Mellon University
Pittsburgh, PA 15213
slepcev@andrew.cmu.edu
Abstract: This paper establishes the consistency of spectral
approaches to data clustering. We consider clustering of point clouds
obtained as samples of a ground-truth measure.
A graph representing the point cloud is obtained by assigning weights to
edges based on the distance between the points they connect.
We investigate the spectral convergence of both unnormalized and
normalized graph Laplacians towards the appropriate operators in the
continuum domain. We obtain sharp conditions on how the connectivity
radius can be scaled with respect to the number of sample points for the
spectral convergence to hold. We also show that the discrete clusters
obtained via spectral clustering converge towards a continuum partition
of the ground truth measure. Such continuum partition minimizes a
functional describing the continuum analogue of the graph-based spectral
partitioning. Our approach, based on variational convergence, is
general and flexible.
Get the paper in its entirety as 15-CNA-007.pdf
« Back to CNA Publications
