Discrete Optimization Methods for Group Model Selection in Compressed Sensing

Bubacarr Bah, Jannis Kurtz, Oliver Schaudt

Abstract

In this article, we investigate signal recovery for group-sparse models where signal support is restricted to a union of predefined groups. We analyze the Iterative Hard Thresholding (IHT) algorithm and its approximate variant (AM-IHT), focusing on the computational complexity of the model projection step. By framing the projection as a maximum weight coverage problem, we introduce discrete optimization techniques—specifically Dynamic Programming and Benders’ Decomposition—to handle complex, overlapping group structures. Our analysis covers both Gaussian and model expander sensing matrices, demonstrating that recovery efficiency depends heavily on the topological properties of the group overlaps, characterized by the treewidth of the group incidence graph.

Introduction

Compressed Sensing (CS) allows for the recovery of sparse signals from a limited number of linear measurements. While standard CS assumes non-zero entries are distributed randomly, many real-world signals exhibit "structured sparsity," where non-zero coefficients cluster within specific groups, such as wavelet coefficients in images or gene clusters in bioinformatics.

The Iterative Hard Thresholding (IHT) algorithm is a cornerstone of recovery in these settings. However, its effectiveness relies on an "oracle" that can project a vector onto the group model. When groups overlap, this projection step becomes a combinatorial optimization problem. For complex overlap structures, this problem is NP-hard, limiting the applicability of traditional IHT to simple, disjoint, or loopless group models. This paper bridges the gap between CS and discrete optimization to enable recovery in more intricate group-sparse environments.

The Complexity of Group Projection

The core challenge in group-sparse recovery is the model projection: finding the best fit for a signal within a budget of $G$ groups. We demonstrate that the difficulty of this task is tied to the "incidence graph" of the groups.

Exact Projection Oracles

To address the projection challenge, we propose two exact methods:

  1. Dynamic Programming (DP): We prove that if the group structure has a low treewidth (a measure of how "tree-like" the overlaps are), the projection can be solved exactly in polynomial time.
  2. Benders’ Decomposition: For more "tangled" structures where DP is infeasible, Benders’ Decomposition partitions the problem into a master problem and a sub-problem, iteratively refining the solution. This approach is flexible enough to handle any group structure and can incorporate additional sparsity constraints.

Approximate Recovery: AM-IHT

Recognizing that exact projection can be computationally expensive, we also explore the Approximate Model IHT (AM-IHT). This variant utilizes "head" and "tail" approximations to find "good enough" projections faster than exact methods:

  • Head-Approximation: A greedy method used to identify a support set that captures a significant portion of the signal's energy.
  • Tail-Approximation: A Linear Programming (LP) rounding technique to find a support set that minimizes the residual error.

Experimental Evaluation

We evaluated these methods using synthetic datasets with signals up to dimension $N=900$. We specifically focused on "overlapping block-groups," where groups consist of contiguous indices with varying degrees of overlap.

Sensing Matrices: Gaussian vs. Expander

A key contribution of this work is the comparison between Gaussian sensing matrices and Model Expander matrices (sparse, binary matrices derived from graph theory).

  • Recovery Thresholds: For expander matrices, successful recovery (median relative error near zero) was achieved when the number of measurements $m$ reached approximately 45% of the signal dimension $N$. Gaussian matrices required a higher threshold of roughly 60%.
  • Support Identification: Compared to the popular convex "Group Lasso" approach, our discrete $\ell_0$-based methods demonstrated superior performance in correctly identifying the signal's support, especially when paired with expander matrices. Unlike Group Lasso, IHT-based methods do not require the complex tuning of a regularization parameter ($\lambda$).

Conclusion

This research establishes that the topology of group overlaps is the primary bottleneck in structured compressed sensing. By integrating discrete optimization oracles into the IHT framework, we provide a robust pathway for signal recovery in complex models. While treewidth remains a limiting factor for DP, Benders’ Decomposition and approximate algorithms like AM-IHT offer practical solutions for high-dimensional applications. Future work will focus on applying these methods to real-world seismic and genomic data analysis.

Summary updated

Abstract

In this article we study the problem of signal recovery for group models. More precisely for a given set of groups, each containing a small subset of indices, and for given linear sketches of the true signal vector which is known to be group-sparse in the sense that its support is contained in the union of a small number of these groups, we study algorithms which successfully recover the true signal just by the knowledge of its linear sketches. We derive model projection complexity results and algorithms for more general group models than the state-of-the-art. We consider two versions of the classical Iterative Hard Thresholding algorithm (IHT). The classical version iteratively calculates the exact projection of a vector onto the group model, while the approximate version (AM-IHT) uses a head- and a tail-approximation iteratively. We apply both variants to group models and analyse the two cases where the sensing matrix is a Gaussian matrix and a model expander matrix. To solve the exact projection problem on the group model, which is known to be equivalent to the maximum weight coverage problem, we use discrete optimization methods based on dynamic programming and Benders' Decomposition. The head- and tail-approximations are derived by a classical greedy-method and LP-rounding, respectively.
BibTeX
@inproceedings{bah2021discrete,
  author = {Bubacarr Bah and Jannis Kurtz and Oliver Schaudt},
  title = {{Discrete Optimization Methods for Group Model Selection in Compressed Sensing}},
  booktitle = {Math. Program},
  year = {2021},
  url = {https://openreview.net/forum?id=ymDvBeAJy8},
}
Figure