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:
- 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.
- 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