The K-Sparse Lsr for Subspace Clustering Via 0-1 Integer Programming

Subspace clustering is a powerful technology for clustering high-dimensional data according to the underlying subspaces. Least Squares Regression (LSR) is a classical subspace clustering model because of its explicit solution and the good grouping effect that ensure the coefficient of close samples to be similar. However, one obvious limitation of it is lacking the sparsity. To introduce appropriate sparsity into LSR, we introduce an ℓ 0 norm based inequality constraint directly without any relaxation into the LSR. Since the ℓ 0 norm constrained optimization problem is difficult to solve, we first propose an appropriate variable substitution to transform the ℓ 0 norm constraint into an equivalent 0-1 integer constraint and then replace the 0-1 integer constraint with two continuous constraints. The obtained model with 0-1 integer constraint is the new model proposed in this paper, named k -sparse LSR (KSLSR), which can be effectively solved by the alternating direction method of multipliers (ADMM), an advanced solution for 0-1 integer programming. The proposed model is proved to have both sparsity and the grouping effect, which are beneficial for improving the clustering accuracy. Experimental results show the effectiveness and robustness of the proposed subspace clustering model