RIP based condition for support recovery with A* OMP in the presence of noise

A* orthogonal matching pursuit (A* OMP) aims at combination of best‐first tree search with the OMP algorithm for the compressed sensing problem. In this study, the authors present a new analysis for the A* OMP algorithm using the restricted isometry property (RIP). The results show that if the sampling matrix satisfies the RIP with ( ), then under some constraints on SNR, A* OMP accurately recovers the support of any K ‐sparse signal from the samples , where B is the number of child paths for each candidate in the algorithm. In addition, the proposed condition is an optimal condition that guarantees the success of A* OMP in the noise‐free case.