Randomly Projected Convex Clustering Model: Motivation, Realization, and Cluster Recovery Guarantees
This addresses the scalability and efficiency of clustering algorithms for high-dimensional data, offering theoretical guarantees and practical improvements, though it is incremental as it builds on existing convex clustering methods.
The paper tackles clustering high-dimensional data by proposing a randomly projected convex clustering model, proving that it preserves perfect cluster recovery with reduced embedding dimensions independent of data points, and demonstrating superior performance over randomly projected K-means in experiments.
In this paper, we propose a randomly projected convex clustering model for clustering a collection of $n$ high dimensional data points in $\mathbb{R}^d$ with $K$ hidden clusters. Compared to the convex clustering model for clustering original data with dimension $d$, we prove that, under some mild conditions, the perfect recovery of the cluster membership assignments of the convex clustering model, if exists, can be preserved by the randomly projected convex clustering model with embedding dimension $m = O(ε^{-2}\log(n))$, where $0 < ε< 1$ is some given parameter. We further prove that the embedding dimension can be improved to be $O(ε^{-2}\log(K))$, which is independent of the number of data points. Extensive numerical experiment results will be presented in this paper to demonstrate the robustness and superior performance of the randomly projected convex clustering model. The numerical results presented in this paper also demonstrate that the randomly projected convex clustering model can outperform the randomly projected K-means model in practice.