Convex approximation of the NP-hard search problem in feature subset selection

Feature subset selection, as a special case of the general subset selection problem, attracted a lot of research attention due to the growing importance of data-mining applications. However, since finding the optimal subset is an NP-hard problem, very different heuristic search methods have been suggested to approximate it. Here we propose a new second-order cone programming based search strategy to efficiently solve the feature subset selection for large-scale problems. Experimentally, it is shown that its performance is almost always better than the greedy search methods especially when the features are strongly dependent.