Grouped Orthogonal Matching Pursuit for Variable Selection and Prediction

Aurelie C. Lozano, Grzegorz Swirszcz, Naoki AbeNeurIPS 2009 · OpenReview

Introduction

In many regression problems, explanatory variables are not independent entities; they naturally belong to functional groups. For instance, in a multifactor ANOVA, several dummy variables might represent a single categorical factor, or in genomics, multiple genes might belong to the same biological pathway. Standard selection methods like the Lasso or basic Orthogonal Matching Pursuit (OMP) select individual variables, which often breaks these natural groups apart. This leads to models that are harder to interpret and potentially less accurate.

While "Group Lasso" exists to address this by keeping groups intact, it relies on complex convex optimization. This paper introduces Group Orthogonal Matching Pursuit (Group-OMP), a greedy algorithm designed for variable selection when features have a natural grouping structure. The authors demonstrate that this simpler, stage-wise approach can consistently identify the correct groups of variables even in noisy conditions, often outperforming Group Lasso in both prediction accuracy and selection precision.

Methods: The Group-OMP Algorithm

Group-OMP is an extension of the classical OMP algorithm tailored for group structures. The core steps and theoretical insights include:

  1. The Greedy Step: Instead of picking the single best variable that correlates with the current residual, Group-OMP selects the entire group of variables that provides the greatest reduction in residual error.
  2. Orthonormalization: To simplify the mathematics and improve computational stability, the algorithm assumes (or pre-processes) each group to be orthonormal.
  3. The Update: After selecting a group, the algorithm performs an Ordinary Least Squares (OLS) regression on all currently selected groups to update the coefficients and calculate a new residual.
  4. Theoretical Guarantees: The paper provides a rigorous proof of consistency by generalizing the "Exact Recovery Condition" to a group setting. A core insight is the parameter $\mu_X(G_{good})$, which measures how well "bad" groups can mimic "good" groups. If this "mimicry" value is strictly bounded, the algorithm is theoretically guaranteed to pick the correct variables in the noiseless case.

Experiments and Results

The authors evaluated Group-OMP using both synthetic and real-world data to test its ability to recover true underlying structures and predict unseen data.

Simulated Experiments

The synthetic evaluation comprised four distinct additive models (Exp 1-4) with varying complexities, including categorical variables, third-order polynomial expansions, and hidden latent variables.

Simulation Results across four experiments

Across these four experiments, Group-OMP consistently achieved higher $F_1$ scores (a measure of selection accuracy) than Group Lasso, OMP, and standard Lasso. The results demonstrate that the greedy approach is not just a heuristic but a highly effective method for group variable selection.

Real-World Data: Boston Housing

For real-world validation, the authors used the classic Boston Housing dataset. To create a group structure, each continuous variable was expanded into a third-order polynomial ($X_i, X_i^2, X_i^3$), treating the three terms as a single group.

Boston Housing Dataset Results

Group-OMP achieved the lowest prediction error ($17.60 \pm 0.51$) compared to Group Lasso ($18.45 \pm 0.59$) and OLS ($29.30 \pm 3.25$). Furthermore, Group-OMP exhibited superior model parsimony. It selected only ~9 groups on average, whereas Group Lasso and OMP selected 11-12. This proves that Group-OMP finds more compact, efficient representations of the data by effectively "cutting the fat" from the model.

Limitations and Future Work

While Group-OMP shows strong performance, the authors note a few limitations and avenues for future research:

  • Disjoint Groups: The current framework assumes that groups do not overlap (each variable belongs to exactly one group). Many real-world problems involve overlapping groups (e.g., a gene belonging to multiple pathways), which this version does not address.
  • Group Size Penalty: The current selection step doesn't explicitly penalize larger groups over smaller ones. Adding a penalty for group size in the selection criteria could be a valuable modification.
  • Forward-Backward Refinement: A "forward-backward" extension—allowing the algorithm to remove a group it previously picked—could help correct early mistakes and further improve consistency.

Summary updated

Abstract

We consider the problem of variable group selection for least squares regression, namely, that of selecting groups of variables for best regression performance, leveraging and adhering to a natural grouping structure within the explanatory variables. We show that this problem can be efficiently addressed by using a certain greedy style algorithm. More precisely, we propose the Group Orthogonal Matching Pursuit algorithm (Group-OMP), which extends the standard OMP procedure (also referred to as ``forward greedy feature selection algorithm for least squares regression) to perform stage-wise group variable selection. We prove that under certain conditions Group-OMP can identify the correct (groups of) variables. We also provide an upperbound on the $l_\infty$ norm of the difference between the estimated regression coefficients and the true coefficients. Experimental results on simulated and real world datasets indicate that Group-OMP compares favorably to Group Lasso, OMP and Lasso, both in terms of variable selection and prediction accuracy.
BibTeX
@inproceedings{lozano2009grouped,
  author = {Aurelie C. Lozano and Grzegorz Swirszcz and Naoki Abe},
  title = {{Grouped Orthogonal Matching Pursuit for Variable Selection and Prediction}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2009},
  url = {https://openreview.net/forum?id=r1-AWvWdZr},
}
Figure