2017/12/08 by Canyi Lu, Lu, Canyi, Jiashi Feng +5 · 2 citations
Computer Science · Engineering · #FOS: Computer and information sciences #Face and Expression Recognition #Indoor and Outdoor Localization Technologies #Machine Learning (cs.LG) #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.1712.02979
openalex publication_date 2017/12/08 · openalex created_date 2017/12/22 · openalex updated_date 2026/07/28
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.