Fast group sparse classification

Abstract

A recent work proposed a novel Group Sparse Classifier (GSC) that was based on the assumption that the training samples of a particular class approximately form a linear basis for any test sample belonging to that class. The Group Sparse Classifier requires solving an NP hard group-sparsity promoting optimization problem. Thus a convex relaxation of the optimization problem was proposed. The convex optimization problem, however, needs to be solved by quadratic programming and hence requires a large amount of computational time. To overcome this, we propose novel greedy (sub-optimal) algorithms for directly addressing the NP hard minimization problem. We call the classifiers based on these greedy group sparsity promoting algorithms as Fast Group Sparse Classifiers (FGSC). This work shows that the FGSC has nearly the same accuracy (at 95% confidence level) as the GSC, but with much faster computational speed (nearly two orders of magnitude). When certain conditions hold the GSC and the FGSC are robust to dimensionality reduction via random projection. By robust, we mean that the classification accuracy is approximately the same before and after random projection. The robustness of these classifi ers will be theoretically proved, and will be validated by thorough experimentation.