Influential Feature PCA for high dimensional clustering

Abstract

We consider a clustering problem where we observe feature vectors $X_i\in R^p$, $i=1,2,\dots ,n$, from $K$ possible classes. The class labels are unknown and the main interest is to estimate them. We are primarily interested in the modern regime of $p\gg n$, where classical clustering methods face challenges. We propose Influential Features PCA (IF-PCA) as a new clustering procedure. In IF-PCA, we select a small fraction of features with the largest Kolmogorov-Smirnov (KS) scores, where the threshold is chosen by adapting the recent notion of Higher Criticism, obtain the first $(K-1)$ left singular vectors of the post-selection normalized data matrix, and then estimate the labels by applying the classical k-means to these singular vectors. It can be seen that IF-PCA is a tuning free clustering method. We apply IF-PCA to $10$ gene microarray data sets. The method has competitive performance in clustering. Especially, in three of the data sets, the error rates of IF-PCA are only $29\%$ or less of the error rates by other methods. We have also rediscovered a phenomenon on empirical null by \cite{Efron} on microarray data. With delicate analysis, especially post-selection eigen-analysis, we derive tight probability bounds on the Kolmogorov-Smirnov statistics and show that IF-PCA yields clustering consistency in a broad context. The clustering problem is connected to the problems of sparse PCA and low-rank matrix recovery, but it is different in important ways. We reveal an interesting phase transition phenomenon associated with these problems and identify the range of interest for each.

62 pages, 6 figures

References in corpus (8)

• Fast community detection by SCORE
• Hypothesis test for normal mixture models: The EM approach
• Higher Criticism for Large-Scale Inference, Especially for Rare and Weak Effects
• Convergence and prediction of principal component scores in high-dimensional settings
• Spectral Clustering Based on Local PCA
• Augmented sparse principal component analysis for high dimensional data
• Covariate assisted screening and estimation
• Phase Transitions for High Dimensional Clustering and Related Problems

Cited by in corpus (6)

• Higher Criticism for Large-Scale Inference, Especially for Rare and Weak Effects
• Statistical and Computational Guarantees of Lloyd's Algorithm and its Variants
• A Simple Approach to Sparse Clustering
• Rate-Optimal Perturbation Bounds for Singular Subspaces with Applications to High-Dimensional Statistics
• Phase Transitions for High Dimensional Clustering and Related Problems
• A Sparse PCA Approach to Clustering