Abstract
Greedy algorithms for sparse signal recovery are computationally efficient but often suffer from "myopic" decision-making, leading to local optima. This paper presents Matching Pursuit with Tree Pruning (TMP), an algorithm that combines tree search with a novel pruning strategy to explore multiple candidate recovery paths. By utilizing a "look-ahead" cost estimation, TMP maintains computational efficiency while achieving recovery performance close to the theoretical Oracle limit in high-SNR scenarios.
Introduction
The central challenge in compressive sensing is the reconstruction of a sparse signal $x$ from a limited set of linear measurements $y = \Phi x$. While finding the absolute sparsest solution is NP-hard, practitioners typically choose between accurate but complex $L_1$-optimization or fast but potentially inaccurate greedy algorithms like Orthogonal Matching Pursuit (OMP). Greedy methods often fail because they make irreversible decisions at each step based on local information. TMP addresses this by exploring a tree of potential solutions, allowing for a more global search without the prohibitive cost of exhaustive exploration.
The TMP Algorithm
The TMP algorithm consists of two distinct phases designed to balance accuracy and speed:
- Pre-selection: To constrain the search space, the algorithm first identifies a subset of promising indices $\Theta$ from the sensing matrix using a standard greedy approach (e.g., generalized OMP). This ensures the tree search focuses on the most relevant components of the signal.
- Tree Search with Pruning: A search tree is constructed where each path represents a candidate support set. To prevent exponential growth of the tree, a sophisticated pruning mechanism is employed.
Overcoming Monotonicity in Pruning
A significant hurdle in applying tree search to signal recovery is that the residual error—the typical "cost" function—is monotonically decreasing as more indices are added. Standard pruning techniques, which discard paths when current costs exceed a threshold, are ineffective here because a high current error might still lead to the best final solution.
TMP solves this by estimating a "noncausal set"—a quick approximation of the remaining indices needed to complete the support set. This allows the algorithm to calculate a "full-blown" estimated cost for the entire path. If this total estimated error exceeds the best error found so far, the branch is pruned immediately.
Performance and Results
The authors evaluated TMP using synthetic simulations with random Gaussian sensing matrices ($100 \times 256$) and $K$-sparse signals. Theoretical analysis shows that TMP's recovery conditions, based on the Restricted Isometry Property (RIP), are more relaxed than those of standard greedy algorithms.
- Recovery Accuracy: In noiseless tests, TMP significantly outperformed standard greedy methods. At a sparsity level of $K=35$, TMP achieved an ~89% recovery rate, a stark improvement over OMP's ~23%.
- Robustness to Noise: In noisy environments, TMP's Mean Squared Error (MSE) performance approached the Oracle LS estimator—the theoretical performance bound—as the Signal-to-Noise Ratio (SNR) increased.
- Computational Efficiency: While more complex than basic OMP, TMP is orders of magnitude faster than exhaustive search. By limiting the branching factor ($N_{max}$), the authors demonstrated that high accuracy can be maintained with manageable computational overhead.
Conclusion
Matching Pursuit with Tree Pruning (TMP) provides a powerful alternative for sparse signal recovery, bridging the gap between simple greedy heuristics and complex global optimization. Its ability to "look ahead" and prune unpromising paths allows it to escape local optima that trap traditional greedy algorithms. Future work may focus on refining the look-ahead strategies and adaptive branching to further optimize the trade-off between speed and recovery performance.
Summary updated