PECOK: a convex optimization approach to variable clustering

Abstract

The problem of variable clustering is that of grouping similar components of a $p$-dimensional vector $X=(X_1,\dots ,X_p)$, and estimating these groups from $n$ independent copies of $X$. When cluster similarity is defined via $G$-latent models, in which groups of $X$-variables have a common latent generator, and groups are relative to a partition $G$ of the index set $\{1,\dots ,p\}$, the most natural clustering strategy is $K$-means. We explain why this strategy cannot lead to perfect cluster recovery and offer a correction, based on semi-definite programing, that can be viewed as a penalized convex relaxation of $K$-means (PECOK). We introduce a cluster separation measure tailored to $G$-latent models, and derive its minimax lower bound for perfect cluster recovery. The clusters estimated by PECOK are shown to recover $G$ at a near minimax optimal cluster separation rate, a result that holds true even if $K$, the number of clusters, is estimated adaptively from the data. We compare PECOK with appropriate corrections of spectral clustering-type procedures, and show that the former outperforms the latter for perfect cluster recovery of minimally separated clusters.

References in corpus (2)

• Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
• A Generic Sample Splitting Approach for Refined Community Recovery in Stochastic Block Models

Cited by in corpus (6)

• Clustering with feature selection using alternating minimization, Application to computational biology
• Hanson-Wright inequality in Hilbert spaces with application to $K$-means clustering for non-Euclidean data
• Adaptive Estimation in Structured Factor Models with Applications to Overlapping Clustering
• Cutoff for exact recovery of Gaussian mixture models
• Partial recovery bounds for clustering with the relaxed $K$means
• Efficient, Certifiably Optimal Clustering with Applications to Latent Variable Graphical Models