Abstract
Among existing clustering methods, sparse subspace clustering (SSC) obtains superior clustering performance in grouping data points from a union of subspaces by solving a relaxed 0-minimization problem by 1-norm. The use of 1-norm instead of the 0 one can make the object function convex, while it also causes large errors on large coefficients in some cases. In this work, we propose using the nonconvex approximation to replace 0-norm for SSC, termed as SSC via nonconvex approximation (SSCNA), and develop a novel clustering algorithm with the enhanced sparsity based on the Alternating Direction Method of Multipliers. We further prove that the proposed nonconvex approximation is closer to 0-norm than the 1 one and is bounded by 0-norm. Numerical studies show that the proposed nonconvex approximation helps to improve clustering performance. We also theoretically verify the convergence of the proposed algorithm with a three-variable objective function. Extensive experiments on four benchmark datasets demonstrate the effectiveness of the proposed method.