Dual formulation of the sparsity constrained optimization problem: application to classification

We tackle the sparsity constrained optimization problem by resorting to polyhedral k-norm as a valid tool to emulate the (Formula presented.) -pseudo-norm. The main novelty of the approach is the use of the dual of the k-norm, which allows to obtain a formulation amenable for a relaxation that can be efficiently handled by block coordinate methods. The advantage of the approach is that it does not require the solution of difference-of-convex programmes, unlike other k-norm based methods available in the literature. In fact, our block coordinate approach requires, at each iteration, the solution of two convex programmes, one of which can be solved in (Formula presented.) time. We apply the method to feature selection within the framework of Support Vector Machine classification, and we report the results obtained on some benchmark test problems.