The k-sparse LSR for subspace clustering via 0-1 integer programming

doi:10.1016/j.sigpro.2022.108622

2022-10-01

PRE

Ting Yang

Shuisheng Zhou *

Zhuan Zhang

DOI：10.1016/j.sigpro.2022.108622

原文链接

原文求助

摘要

En 中文

Subspace clustering is a powerful technology for clustering high-dimensional data. Least squares regression (LSR) is one of the classical subspace clustering models because of the explicit solution and grouping effect that tends to cluster highly correlated data together. However, LSR lacks sparsity, which may lead to its sensitivity to noise and dimension of data. Since the L 0-norm constrained optimization is difficult to solve, we introduce a new method based on the 0-1 integer programming, named k-sparse L SR (KSL SR), to directly solve the optimization of the LSR constrained by an L 0-norm-based constraint without any relaxation, where k represents the maximum number of non-zero elements of the representation coefficient. With the help of the 0-1 integer constraint, the L 0-norm-based constraint is equivalent to two continuous constraints. Thus, the obtained KSLSR method with two continuous constraints is equivalent to the L 0-norm constrained optimization and can be effectively solved by the alternating direction multiplier method (ADMM). In addition, the new method is proven to provide a solution with both k-sparsity and the grouping effect, which makes it robust to the noise and dimension of data. Extensive experiments are conducted to demonstrate the effectiveness and superiority of the proposed method. (C) 2022 Elsevier B.V. All rights reserved.

Keyword:

Subspace clustering

Grouping effect

0-1 integer programming

L-p-box intersection

ADMM

k-sparsity