Greedy Sparse Signal Recovery with Tree Pruning

Jaeseok Lee, Suhyuk Kwon, Jun Won Choi, Byonghyo ShimarXiv 2014 · arXiv

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:

  1. 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.
  2. 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.
The TMP framework: Pre-selection narrows the search space, followed by a structured tree search with pruning.

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.

Pruning strategy: (a) A path is pruned if its estimated final cost exceeds the current best. (b) Lower intermediate cost does not guarantee a superior final result, necessitating the look-ahead approach.

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

Abstract

Recently, greedy algorithm has received much attention as a cost-effective means to reconstruct the sparse signals from compressed measurements. Much of previous work has focused on the investigation of a single candidate to identify the support (index set of nonzero elements) of the sparse signals. Well-known drawback of the greedy approach is that the chosen candidate is often not the optimal solution due to the myopic decision in each iteration. In this paper, we propose a greedy sparse recovery algorithm investigating multiple promising candidates via the tree search. Two key ingredients of the proposed algorithm, referred to as the matching pursuit with a tree pruning (TMP), to achieve efficiency in the tree search are the {\it pre-selection} to put a restriction on columns of the sensing matrix to be investigated and the {\it tree pruning} to eliminate unpromising paths from the search tree. In our performance guarantee analysis and empirical simulations, we show that TMP is effective in recovering sparse signals in both noiseless and noisy scenarios.
BibTeX
@misc{lee2014greedy,
  author = {Jaeseok Lee and Suhyuk Kwon and Jun Won Choi and Byonghyo Shim},
  title = {{Greedy Sparse Signal Recovery with Tree Pruning}},
  year = {2014},
  eprint = {1409.5606},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1409.5606},
}
Figure