Sparse classification using Group Matching Pursuit

Abstract Group structure exists in supervised learning problems inherently. For example, in the training data of a classification problem, samples from the same class will have similar representations. These samples from the same class will form a group. Group sparse features, such as Group Lasso, can reserve this group information and improve classification accuracy by reducing noise using sparse constraints. However, Group Lasso is a sparse approximation, and its performance and solution highly depend on the choice of group sparse penalty weight. In this paper, we propose a Group Matching Pursuit (GMP) based sparse classification approach. Group Matching Pursuit features are sparse features where coefficients of exact K groups are non-zeros. Compared to Group Lasso, 1. Group Matching Pursuit based classification is stable and has no penalty parameters to tune; 2. Group Matching Pursuit features have large Signal-to-Noise Ratio (SNR) and are class discriminant; 3. Group Matching Pursuit features are also robust for occluded images. Extensive experiments on 5 data sets and different levels of occlusion show that the proposed Group Matching Pursuit can improve Group Lasso classification accuracy up to 27.2% in some situation.