Exact Sparse Signal Recovery via Orthogonal Matching Pursuit with Prior Information
Exact recovery of a sparse signal from a linear model arises from many applications. The orthogonal matching pursuit (OMP) algorithm is a widely used sparse signal recovery algorithm due to its excellent recovery performance and high efficiency. A fundamental question regarding the exact sparse signal recovery with OMP is what is the probability that the OMP algorithm can exactly recover the sparse signal and also what is the minimal number of measurements to guarantee a satisfactory recovery performance. This paper points out that although in practical applications, in addition to the sparsity, the k-sparse signal x usually has some additional property (for example, the nonzero entries of x independently and identically follow the Gaussian distribution, and x has exponential decaying property), as far as we know, none of existing analysis uses these properties to answer the above questions. In this paper, based on the distribution of x, we develop an upper bound on ||x||_2^2/||x||_1^2. Then, we explore this upper bound to develop a lower bound on the probability of exact recovery with OMP in K iterations. Furthermore, we develop a lower bound on $m$ to guarantee that the exact recovery probability of $K$ iterations of OMP is not lower than a given probability.