Abstract
In this article, we study the problem of signal recovery for group models. 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, we study algorithms which successfully recover the true signal. 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 calculates the exact projection onto the group model, while the approximate version (AM-IHT) uses head- and tail-approximations. To solve the exact projection problem, we utilize 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.
Introduction
Compressed sensing is a powerful framework for recovering sparse signals from a limited number of linear measurements. Standard approaches assume simple sparsity, where only a small number of signal components are non-zero. However, many real-world signals exhibit more complex structures. Model-based compressed sensing leverages these structures—specifically group sparsity—where non-zero entries are restricted to specific, predefined groups. This additional prior information allows for signal recovery with significantly fewer measurements than traditional methods.
The primary computational hurdle in this domain is the model projection problem. Given a noisy signal estimate, the goal is to find the closest vector that conforms to the group-sparse model. While this is straightforward for disjoint groups, it becomes NP-hard when groups overlap in complex ways, as the problem is equivalent to the Maximum Weight Coverage problem. This paper addresses this challenge by bridging the gap between compressed sensing and discrete optimization.
Methodology
The authors focus on the Iterative Hard Thresholding (IHT) algorithm, which iteratively refines a signal estimate through gradient steps followed by a projection onto the allowed signal model. They propose two main approaches to handle the projection step for complex group models.
Exact Projection Oracles
For scenarios requiring high precision, the authors develop exact projection methods:
- Dynamic Programming (DP): The complexity of the projection problem is shown to be linked to the "incidence graph" of the group model. If this graph has bounded treewidth—a measure of how closely the graph resembles a tree—the projection can be solved in polynomial time using dynamic programming.
- Benders’ Decomposition: For models with high treewidth where DP is infeasible, the authors apply Benders’ decomposition. This classic discrete optimization technique decomposes the integer programming formulation of the projection problem into simpler subproblems. This approach is particularly novel in signal processing, as it enables the handling of models that combine group-sparsity with traditional $k$-sparsity constraints.
Approximate Projection Oracles (AM-IHT)
Recognizing that exact projection can be computationally expensive, the authors introduce the Approximate Model-IHT (AM-IHT). This variant utilizes:
- Head-Approximation: Derived using a greedy method to identify a support set that captures a large portion of the signal's energy.
- Tail-Approximation: Derived via LP-rounding to find a support set that minimizes the residual error. While AM-IHT is faster, it generally requires a slightly higher number of measurements to achieve the same recovery guarantees as the exact Model-IHT.
Experimental Evaluation
The algorithms were evaluated using synthetic datasets. Signals were generated as $N$-dimensional vectors with support contained in the union of $G$ randomly selected groups. The sensing process utilized two types of matrices:
- Gaussian Matrices: Standard dense matrices used as a benchmark.
- Model Expander Matrices: Sparse matrices derived from bipartite expander graphs, which offer superior computational efficiency.
The experiments covered various group structures, including "block-group" instances with varying degrees of overlap, ranging from simple overlaps to complex "interval groups" where elements belong to numerous groups simultaneously.
Key Results and Insights
The study yielded several significant findings:
- Convergence Guarantees: The authors successfully extended convergence proofs for the Model-Expander IHT (MEIHT) algorithm to general group models, ensuring reliable recovery under specific conditions.
- Measurement Efficiency: For expander matrices, the number of measurements $m$ required for recovery scales roughly linearly with the signal dimension $N$ and the group sparsity $G$.
- Runtime Performance: In overlapping block scenarios, the approximate AM-EIHT algorithm was significantly faster than the exact Model-IHT, particularly as the number of groups $G$ increased.
- Topology Matters: The research identifies treewidth as a fundamental metric for recovery complexity. The difficulty of the problem is determined not just by the number of groups, but by the topology of their overlaps.
- Expander Superiority: Sparse expander matrices often outperformed Gaussian matrices, requiring fewer measurements for structured models while being significantly faster to compute.
Conclusion
This paper demonstrates that discrete optimization techniques like Benders' decomposition and dynamic programming can effectively solve the NP-hard projection problems inherent in structured compressed sensing. By providing both exact and approximate algorithms, the authors offer a flexible framework that balances recovery accuracy with computational speed. Future work will explore the application of these methods to real-world datasets, such as genomic sequences or seismic sensor arrays, and investigate ways to improve approximation guarantees for models with high group overlap frequency.
Summary updated