Phase transitions for high dimensional clustering and related problems

DOI10.1214/16-AOS1522MaRDI QIDQ1687124zbMATH OpenOpenAlexFDO

Authors Jiashun Jin, Zheng Tracy Ke, Wanjie Wang

Publication date 22 December 2017

Published in The Annals of Statistics (Search for Journal in Brave)

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

zbMATH Keywords

\(L^{1}\)-distanceclusteringcomparison of experimentsfeature selectionhypothesis testinglow-rank matrix recoverylower boundphase transition

Mathematics Subject Classification ID

Nonparametric estimation (62G05) Nonparametric hypothesis testing (62G10) Factor analysis and principal components; correspondence analysis (62H25) Classification and discrimination; cluster analysis (statistical aspects) (62H30)

Abstract: Consider a two-class clustering problem where we observe $X_i=el{l}_{i}mu+Z_i$, $Z_{i}stackreliidsimN(0,I_p)$, $1leqileqn$. The feature vector $muin{R}^p$ is unknown but is presumably sparse. The class labels $el{l}_{i}in-1,1$ are also unknown and the main interest is to estimate them. We are interested in the statistical limits. In the two-dimensional phase space calibrating the rarity and strengths of useful features, we find the precise demarcation for the Region of Impossibility and Region of Possibility. In the former, useful features are too rare/weak for successful clustering. In the latter, useful features are strong enough to allow successful clustering. The results are extended to the case of colored noise using Le Cam's idea on comparison of experiments. We also extend the study on statistical limits for clustering to that for signal recovery and that for hypothesis testing. We compare the statistical limits for three problems and expose some interesting insight. We propose classical PCA and Important Features PCA (IF-PCA) for clustering. For a threshold $t>0$, IF-PCA clusters by applying classical PCA to all columns of $X$ with an $L^2$-norm larger than $t$. We also propose two aggregation methods. For any parameter in the Region of Possibility, some of these methods yield successful clustering. We find an interesting phase transition for IF-PCA. Our results require delicate analysis, especially on post-selection Random Matrix Theory and on lower bound arguments.

Recommendations

• Influential features PCA for high dimensional clustering
• Classification of sparse high-dimensional vectors
• Clustering and feature selection using sparse principal component analysis
• Clustering High-Dimensional Data via Feature Selection
• Impossibility of successful classification when useful features are rare and weak

Cited in

(21)

• Feature screening in large scale cluster analysis
• A simple approach to sparse clustering
• Rate-optimal perturbation bounds for singular subspaces with applications to high-dimensional statistics
• Statistical limits of sparse mixture detection
• Testing equivalence of clustering
• High-dimensional incipient infinite clusters revisited
• scientific article; zbMATH DE number 7370563 (Why is no real title available?)
• Covariate regularized community detection in sparse graphs
• Influential features PCA for high dimensional clustering
• Computationally efficient sparse clustering
• Optimal Estimation of the Number of Network Communities
• Power enhancement and phase transitions for global testing of the mixed membership stochastic block model
• Estimation of the Number of Spiked Eigenvalues in a Covariance Matrix by Bulk Eigenvalue Matching Analysis
• Estimation of misclassification rate in the Asymptotic Rare and Weak model with sub-Gaussian noises
• Optimal clustering by Lloyd's algorithm for low-rank mixture model
• Spectral clustering on aggregated multilayer networks with covariates
• Uniform error bound for PCA matrix denoising
• Clustering a mixture of Gaussians with unknown covariance
• Optimal estimation of misclassification rate for two-class clustering with sub-Gaussian noises
• Network-adjusted covariates for community detection
• Mean field models for large data-clustering problems

This page was built for publication: Phase transitions for high dimensional clustering and related problems

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