Feature selection in linear SVMs via hard cardinality constraint: a scalable SDP decomposition approach

arXiv:2404.10099v1 Announce Type: cross
Abstract: In this paper, we study the embedded feature selection problem in linear Support Vector Machines (SVMs), in which a cardinality constraint is employed, leading to a fully explainable selection model. The problem is NP-hard due to the presence of the cardinality constraint, even though the original linear SVM amounts to a problem solvable in polynomial time. To handle the hard problem, we first introduce two mixed-integer formulations for which novel SDP relaxations are proposed. Exploiting …

abstract arxiv cs.lg embedded feature feature selection linear machines math.oc np-hard paper scalable study support support vector machines type vector via