Nonconvex Sparse Spectral Clustering by Alternating Direction Method of
  Multipliers and Its Convergence Analysis
  Spectral Clustering (SC) is a widely used data clustering method which first
learns a low-dimensional embedding $U$ of data by computing the eigenvectors of
the normalized Laplacian matrix, and then performs k-means on $U^\top$ to get
the final clustering result. The Sparse Spectral Clustering (SSC) method
extends SC with a sparse regularization on $UU^\top$ by using the block
diagonal structure prior of $UU^\top$ in the ideal case. However, encouraging
$UU^\top$ to be sparse leads to a heavily nonconvex problem which is
challenging to solve and the work (Lu, Yan, and Lin 2016) proposes a convex
relaxation in the pursuit of this aim indirectly. However, the convex
relaxation generally leads to a loose approximation and the quality of the
solution is not clear. This work instead considers to solve the nonconvex
formulation of SSC which directly encourages $UU^\top$ to be sparse. We propose
an efficient Alternating Direction Method of Multipliers (ADMM) to solve the
nonconvex SSC and provide the convergence guarantee. In particular, we prove
that the sequences generated by ADMM always exist a limit point and any limit
point is a stationary point. Our analysis does not impose any assumptions on
the iterates and thus is practical. Our proposed ADMM for nonconvex problems
allows the stepsize to be increasing but upper bounded, and this makes it very
efficient in practice. Experimental analysis on several real data sets verifies
the effectiveness of our method.
