Kernel spectral clustering of large dimensional data

DOI10.1214/16-EJS1144zbMATH Open1398.62160arXiv1510.03547OpenAlexW2963144092MaRDI QIDQ302428FDOQ302428

Authors: R. Couillet, Florent Benaych-Georges 

Publication date: 5 July 2016

Published in: Electronic Journal of Statistics (Search for Journal in Brave)

Abstract: This article proposes a first analysis of kernel spectral clustering methods in the regime where the dimension $p$ of the data vectors to be clustered and their number $n$ grow large at the same rate. We demonstrate, under a $k$-class Gaussian mixture model, that the normalized Laplacian matrix associated with the kernel matrix asymptotically behaves similar to a so-called spiked random matrix. Some of the isolated eigenvalue-eigenvector pairs in this model are shown to carry the clustering information upon a separability condition classical in spiked matrix models. We evaluate precisely the position of these eigenvalues and the content of the eigenvectors, which unveil important (sometimes quite disruptive) aspects of kernel spectral clustering both from a theoretical and practical standpoints. Our results are then compared to the actual clustering performance of images from the MNIST database, thereby revealing an important match between theory and practice.

Full work available at URL: https://arxiv.org/abs/1510.03547

Recommendations

• The geometry of kernelized spectral clustering
• Consistency of spectral clustering
• Covariance discriminative power of kernel clustering methods
• Eigen Selection in Spectral Clustering: A Theory-Guided Practice
• Optimality of spectral clustering in the Gaussian mixture model

zbMATH Keywords

kernel methodsrandom matrix theoryspectral clustering

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Random matrices (algebraic aspects) (15B52) Random matrices (probabilistic aspects) (60B20)

Cites Work

• Matrix Analysis
• Pattern recognition and machine learning.
• On the distribution of the largest eigenvalue in principal components analysis
• Asymptotics of sample eigenstructure for a large dimensional spiked covariance model
• DISTRIBUTION OF EIGENVALUES FOR SOME SETS OF RANDOM MATRICES
• Hanson-Wright inequality and sub-Gaussian concentration
• Consistency of spectral clustering
• The singular values and vectors of low rank perturbations of large rectangular random matrices
• No eigenvalues outside the support of the limiting spectral distribution of large-dimensional sample covariance matrices
• Analysis of the limiting spectral distribution of large dimensional random matrices
• Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices
• A Bound on Tail Probabilities for Quadratic Forms in Independent Random Variables
• Concentration of measure and spectra of random matrices: applications to correlation matrices, elliptical distributions and beyond
• On the empirical distribution of eigenvalues of a class of large dimensional random matrices
• Large deviations of the extreme eigenvalues of random deformations of matrices
• The random matrix regime of Maronna's M-estimator with elliptically distributed samples
• Fluctuations of the extreme eigenvalues of finite rank deformations of random matrices
• The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices
• A subspace estimator for fixed rank perturbations of large random matrices
• The outliers among the singular values of large rectangular random matrices with additive fixed rank deformation
• Analysis of the limiting spectral measure of large random matrices of the separable covariance type
• Fluctuations of Spiked Random Matrix Models and Failure Diagnosis in Sensor Networks
• Kernel spectral clustering of large dimensional data
• Universality of Wigner random matrices: a survey of recent results
• Local semicircle law for Wigner matrices
• Large System Analysis of Linear Precoding in Correlated MISO Broadcast Channels Under Limited Feedback
• A Deterministic Equivalent for the Analysis of Correlated MIMO Multiple Access Channels
• The spectrum of kernel random matrices

Cited In (27)

• Doubly stochastic normalization of the Gaussian kernel is robust to heteroskedastic noise
• Spectrum of large random inner-product kernel matrices generated from l_p ellipsoids
• Title not available (Why is that?)
• Spectral connectivity analysis
• \textit{Kernel cuts}: kernel and spectral clustering meet regularization
• Concentration of kernel matrices with application to kernel spectral clustering
• Latent structure blockmodels for Bayesian spectral graph clustering
• Sparse and smooth: improved guarantees for spectral clustering in the dynamic stochastic block model
• Spectral properties for the Laplacian of a generalized Wigner matrix
• MIXANDMIX: numerical techniques for the computation of empirical spectral distributions of population mixtures
• Random matrix-improved estimation of covariance matrix distances
• Kernel spectral clustering of large dimensional data
• Title not available (Why is that?)
• Spectral properties of kernel matrices in the flat limit
• KNN-kernel density-based clustering for high-dimensional multivariate data
• Spectral analysis of the Gram matrix of mixture models
• A random matrix approach to neural networks
• Spectral distribution of large generalized random kernel matrices
• The geometry of kernelized spectral clustering
• A survey of kernel and spectral methods for clustering
• Optimality of spectral clustering in the Gaussian mixture model
• Scaling up Kernel Grower Clustering Method for Large Data Sets via Core-sets
• Eigen Selection in Spectral Clustering: A Theory-Guided Practice
• Covariance discriminative power of kernel clustering methods
• Data spectroscopy: eigenspaces of convolution operators and clustering
• Eigenvalue distribution of some nonlinear models of random matrices
• Hierarchical kernel spectral clustering

Uses Software

• MNIST
• PRMLT

This page was built for publication: Kernel spectral clustering of large dimensional data

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q302428)