Open AccessA Manifold Proximal Linear Method for Sparse Spectral Clustering with Application to Single-Cell RNA Sequencing Data Analysis
Author(s) -
Zhongruo Wang,
Bingyuan Liu,
Shixiang Chen,
Shiqian Ma,
Lingzhou Xue,
Hongyu Zhao
Publication year - 2022
Publication title -
informs journal on optimization
Language(s) - English
Resource type - Journals
eISSN - 2575-1492
pISSN - 2575-1484
DOI - 10.1287/ijoo.2021.0064
Subject(s) - cluster analysis , spectral clustering , stiefel manifold , interpretability , smoothing , computer science , mathematics , clustering high dimensional data , relaxation (psychology) , algorithm , mathematical optimization , artificial intelligence , psychology , social psychology , geometry , computer vision
Spectral clustering is one of the fundamental unsupervised learning methods and is widely used in data analysis. Sparse spectral clustering (SSC) imposes sparsity to the spectral clustering, and it improves the interpretability of the model. One widely adopted model for SSC in the literature is an optimization problem over the Stiefel manifold with nonsmooth and nonconvex objective. Such an optimization problem is very challenging to solve. Existing methods usually solve its convex relaxation or need to smooth its nonsmooth objective using certain smoothing techniques. Therefore, they were not targeting solving the original formulation of SSC. In this paper, we propose a manifold proximal linear method (ManPL) that solves the original SSC formulation without twisting the model. We also extend the algorithm to solve multiple-kernel SSC problems, for which an alternating ManPL algorithm is proposed. Convergence and iteration complexity results of the proposed methods are established. We demonstrate the advantage of our proposed methods over existing methods via clustering of several data sets, including University of California Irvine and single-cell RNA sequencing data sets.