1 and infinite norm support vector machine

The standard support vector machine (SVM) is celebrated for its theoretically guaranteed generalization performance. However, it lacks sparsity and thus cannot be used for feature selection. Zero norm SVM is ideal in the sense of sparsity while its optimization is prohibitive due to the combinatorial nature of zero norm. In this paper, 1 norm and infinite norm constraints are employed simultaneously to relax the zero norm while keep its sparsity. The resulted constraint regions possess much more sparse vertices than that of the 1 norm. Generally, the more sparse vertices the constraint regions have, the sparser the solution will be. Therefore, more parsimonious model can be obtained via the combination of 1 and infinite norm. Interestingly enough, although infinite norm alone does not lead to sparse results, it helps to enhance the sparsity of 1 norm regularization. The optimal solution has a favorable piecewise linearity, based on which the whole solution path can be obtained, and this greatly facilitates model selection. The strict proof for piecewise linearity is given in the appendix. Experimental results demonstrate that our approach offers comparable prediction accuracy with significantly higher sparsity.