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:
- 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.
- Orthonormalization: To simplify the mathematics and improve computational stability, the algorithm assumes (or pre-processes) each group to be orthonormal.
- 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.
- 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.
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.
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