  Spectral clustering is one of the fundamental unsupervised learning methods
widely used in data analysis. Sparse spectral clustering (SSC) imposes sparsity
to the spectral clustering and it improves the interpretability of the model.
This paper considers a widely adopted model for SSC, which can be formulated as
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
part using certain smoothing techniques. In this paper, we propose a manifold
proximal linear method (ManPL) that solves the original SSC formulation. We
also extend the algorithm to solve the 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 the single-cell RNA
sequencing data analysis.
