Orthogonal Matching Pursuit (OMP) is a canonical greedy pursuit algorithm for sparse approximation. Previous studies of OMP have considered the recovery of a sparse signal through Φ and y = Φx + b, where is a matrix with more columns than rows and denotes the measurement noise. In this paper, based on Restricted Isometry Property (RIP), the performance of OMP is analyzed under general perturbations, which means both y and Φ are perturbed. Though the exact recovery of an almost sparse signal x is no longer feasible, the main contribution reveals that the support set of the best k-term approximation of x can be recovered under reasonable conditions. The error bound between x and the estimation of OMP is also derived. By constructing an example it is also demonstrated that the sufficient conditions for support recovery of the best k-term approximation of are rather tight. When x is strong-decaying, it is proved that the sufficient conditions for support recovery of the best k-term approximation of x can be relaxed, and the support can even be recovered in the order of the entries' magnitude. Our results are also compared in detail with some related previous ones.
For @math process with @math -sparse signal @math , Davenport and Wakin proved in @cite_35 that if @math satisfies the RIP of order @math with @math and then OMP will recover @math sequentially from @math and @math in @math iterations @cite_35 .
@cite_35
1557195970 2091893102 2598205349 2568623927
We shall show that if the restricted isometry constant (RIC) @math of the measurement matrix @math satisfies @math then the greedy algorithm Orthogonal Matching Pursuit(OMP) will succeed. That is, OMP can recover every @math -sparse signal @math in @math iterations from @math . Moreover, we shall show the upper bound of RIC is sharp in the following sense. For any given @math , we shall construct a matrix @math with the RIC @math such that OMP may not recover some @math -sparse signal @math in @math iterations. This paper presents a new analysis for the orthogonal matching pursuit (OMP) algorithm. It is shown that if the restricted isometry property (RIP) is satisfied at sparsity level O(k), then OMP can stably recover a k-sparse signal in 2-norm under measurement noise. For compressed sensing applications, this result implies that in order to uniformly recover a k-sparse signal in Rd, only O(k lnd) random projections are needed. This analysis improves some earlier results on OMP depending on stronger conditions that can only be satisfied with Ω(k2 lnd) or Ω(k1.6 lnd) random projections. As a paradigm for reconstructing sparse signals using a set of under sampled measurements, compressed sensing has received much attention in recent years. In identifying the sufficient condition under which the perfect recovery of sparse signals is ensured, a property of the sensing matrix referred to as the restricted isometry property (RIP) is popularly employed. In this article, we propose the RIP based bound of the orthogonal matching pursuit (OMP) algorithm guaranteeing the exact reconstruction of sparse signals. Our proof is built on an observation that the general step of the OMP process is in essence the same as the initial step in the sense that the residual is considered as a new measurement preserving the sparsity level of an input vector. Our main conclusion is that if the restricted isometry constant δ K of the sensing matrix satisfies δ K < K - 1 K - 1 + K then the OMP algorithm can perfectly recover K(> 1)-sparse signals from measurements. We show that our bound is sharp and indeed close to the limit conjectured by Dai and Milenkovic. Consider the problem of recovering an unknown signal from undersampled measurements, given the knowledge that the signal has a sparse representation in a specified dictionary @math . This problem is now understood to be well-posed and efficiently solvable under suitable assumptions on the measurements and dictionary if the number of measurements scales roughly with the sparsity level. One sufficient condition for such is the @math -restricted isometry property ( @math -RIP), which asks that the sampling matrix approximately preserve the norm of all signals which are sufficiently sparse in @math . While many classes of random matrices are known to satisfy such conditions, such matrices are not representative of the structural constraints imposed by practical sensing systems. We close this gap in the theory by demonstrating that one can subsample a fixed orthogonal matrix in such a way that the @math -RIP will hold, provided this basis is sufficiently incoherent with the sparsifying dictionary $ ...