l0-norm based structural sparse least square regression for feature selection

This paper presents a novel approach for feature selection with regard to the problem of structural sparse least square regression (SSLSR). Rather than employing the l1-norm regularization to control the sparsity, we directly work with sparse solutions via l0-norm regularization. In particular, we develop an effective greedy algorithm, where the forward and backward steps are combined adaptively, to resolve the SSLSR problem with the intractable l r , 0 -norm. On the one hand, features with the strongest correlation to classes are selected in the forward steps. On the other hand, redundant features which contribute little to the improvement of the objective function are removed in the backward steps. Furthermore, we provide solid theoretical analysis to prove the effectiveness of the proposed method. Experimental results on synthetic and real world data sets from different domains also demonstrate the superiority of the proposed method over the state-of-the-arts. HighlightsWe impose l0-norm inequality constraint to build the structural sparse LSR problem.We develop an adaptive algorithm to ensure the structural sparsity accurately.Theoretical results on the efficiency and effectiveness of our method are provided.Experimental results prove the superiority of our method over the state-of-the-arts.