Sparse subspace clustering (SSC) relies on sparse regression for accurate neighbor identification. Inspired by recent progress in compressive sensing, this paper proposes a new sparse regression scheme for SSC via two-step reweighted$\ell _{1} $-minimization, which also generalizes a two-step$\ell _{1} $-minimization algorithm introduced by E. J. Candèset al.in [The Annals of Statistics, vol. 42, no. 2, pp. 669–699, 2014] without incurring extra algorithmic complexity. To fully exploit the prior information offered by the computed sparse representation vector in the first step, our approach places a weight on each component of the regression vector, and solves a weighted LASSO in the second step. We propose a data weighting rule suitable for enhancing neighbor identification accuracy. Then, under the formulation of the dual problem of weighted LASSO, we study in depth the theoretical neighbor recovery rates of the proposed scheme. Specifically, an interesting connection between the locations of nonzeros of the optimal sparse solution to the weighted LASSO and the indexes of the active constraints of the dual problem is established. Afterwards, under the semi-random model, analytic probability lower/upper bounds for various neighbor recovery events are derived. Our analytic results confirm that, with the aid of data weighting and if the prior neighbor information is accurate enough, the proposed scheme with a higher probability can produce many correct neighbors and few incorrect neighbors as compared to the solution without data weighting. Computer simulations are provided to validate our analytic study and evidence the effectiveness of the proposed approach.

Built on the sparse representation framework, sparse subspace clustering (SSC) received considerable attention in the recent years. Conventional SSC employs ℓ1-minimization based sparse regression for neighbor identification on a sample-by-sample basis, and is unaware of the neighbor information revealed by those already computed sparse representation vectors. To rid this drawback, this paper proposes a weighted ℓ1-minimization based sparse regression method, and an associated data ordering rule able to reflect the reliability of neighbor information for further enhancing the clustering accuracy. The selection of weighting coefficients for SSC is also discussed. Computer simulations using both the synthesis and real data are provided to evidence the effectiveness of the proposed method.