Sparse signal recovery for a new hybrid greedy algorithm based mutual coherence

Based on the application of the Orthogonal Matching Pursuit (OMP) algorithm in high-dimensional linear measurement sparse signal recovery models, this paper proposes a new hybrid greedy algorithm (NHGA) on the foundation of the core OMP concept. In each iteration, NHGA first selects the column most correlated with the current residual as the candidate column. Then, by introducing a backtracking strategy, it additionally adds P candidate columns and prunes the support set (P is the number of additional candidate columns selected), effectively eliminating misselected atoms, ensuring the accuracy and reliability of the support set, and significantly improving the signal recovery precision. We establish the theoretical guarantee of this algorithm using mutual coherence and prove that NHGA can achieve exact recovery under certain conditions. Through a series of numerical experiments and comparative analyses, the results demonstrate that NHGA can not only recover signals accurately within a reasonable timeframe but also, under various sparsity levels and signal-to-noise ratio conditions, outperform other mainstream greedy algorithms in terms of success rate and recovery error, showcasing stronger robustness and practical application potential.