2015/10/28 by Yingzhen Yang, Yang, Yingzhen, Jiashi Feng +5
Computer Science · Social Sciences · #Advanced Clustering Algorithms Research #Advanced Computing and Algorithms #Computer Vision and Pattern Recognition (cs.CV) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Text and Document Classification Technologies #cs.CV #cs.LG
paper · pdf · doi:10.48550/arxiv.1510.08520
openalex publication_date 2015/10/28 · arxiv created 2015/11/18 · arxiv updated 2015/11/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Sparse subspace clustering methods, such as Sparse Subspace Clustering (SSC) \citeElhamifarV13 and ℓ1-graph \citeYanW09,ChengYYFH10, are effective in partitioning the data that lie in a union of subspaces. Most of those methods use ℓ1-norm or ℓ2-norm with thresholding to impose the sparsity of the constructed sparse similarity graph, and certain assumptions, e.g. independence or disjointness, on the subspaces are required to obtain the subspace-sparse representation, which is the key to their success. Such assumptions are not guaranteed to hold in practice and they limit the application of sparse subspace clustering on subspaces with general location. In this paper, we propose a new sparse subspace clustering method named ℓ0-graph. In contrast to the required assumptions on subspaces for most existing sparse subspace clustering methods, it is proved that subspace-sparse representation can be obtained by ℓ0-graph for arbitrary distinct underlying subspaces almost surely under the mild i.i.d. assumption on the data generation. We develop a proximal method to obtain the sub-optimal solution to the optimization problem of ℓ0-graph with proved guarantee of convergence. Moreover, we propose a regularized ℓ0-graph that encourages nearby data to have similar neighbors so that the similarity graph is more aligned within each cluster and the graph connectivity issue is alleviated. Extensive experimental results on various data sets demonstrate the superiority of ℓ0-graph compared to other competing clustering methods, as well as the effectiveness of regularized ℓ0-graph.