Open AccessRIP based condition for support recovery with A* OMP in the presence of noise
Author(s) -
Li Haifeng,
Chen Wengu
Publication year - 2020
Publication title -
iet signal processing
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.384
H-Index - 42
ISSN - 1751-9683
DOI - 10.1049/iet-spr.2019.0478
Subject(s) - matching pursuit , restricted isometry property , compressed sensing , noise (video) , algorithm , isometry (riemannian geometry) , computer science , mathematics , tree (set theory) , matrix (chemical analysis) , property (philosophy) , basis pursuit , signal reconstruction , pattern recognition (psychology) , combinatorics , signal processing , artificial intelligence , telecommunications , philosophy , radar , materials science , epistemology , composite material , pure mathematics , image (mathematics)
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 A satisfies the RIP with δ K ⋆< B / ( K + B ) ( K ⋆ = max { 2 K , K + B } ), then under some constraints on SNR, A* OMP accurately recovers the support of any K ‐sparse signal x from the samples y = A x + e , 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.