On the Error Probability of Support Recovery for Orthogonal Matching Pursuit with a Random Measurement Matrix

Abstract

In this paper, an asymptotic bound on the recovery error probability of a sparse signal is derived for the orthogonal matching pursuit algorithm. The proposed bound is based on the support recovery analysis with a random measurement matrix, which gets closer to the empirical bound tightly in a large system and high signal-to-noise ratio regime. During recovery, all signal associated parameters introduced in the existing analysis are considered together. Furthermore, the necessary conditions for the conventional bound derivation such as the minimum value limit of non-zero coefficients in the sparse signal can be relaxed in our proposed approach. Through numerical evaluations, our theoretical performance bounds are demonstrated to be close to the simulated results, notably closer than those obtained previously.