Efficient Clustering Using Alternating Minimization And A Projection-Gradient Method For Dimension Reduction

This paper deals with unsupervised clustering in high dimensional space. The problem is to estimate both labels and a sparse projection matrix of weights. To address this combinatorial non-convex problem maintaining a strict control on the sparsity of the matrix of weights, we propose an alternating minimization of the Frobenius norm criterion. We provide a new efficient algorithm named k-sparse which alternates k-means with projection-gradient minimization. The projection-gradient step is a method of splitting type, with exact projection on the ℓ
¹
ball to promote sparsity. The convergence of the gradient-projection step is addressed, and a preliminary analysis of the alternating minimization is provided. Experiments on Single Cell RNA sequencing datasets show that our method significantly improves the results of spectral clustering, SIMLR, and Sparcl methods. The complexity of our method is linear with the number of samples (cells), so that the method scales up to large datasets.