Abstract:
In recent years, Compressed Sensing (CS) has been a hot research topic. It has a wide range of applications, such as image processing and speech signal processing owing to its characteristic of removing redundant information by reducing the sampling rate. The disadvantage of CS is that the number of iterations in a greedy algorithm such as Orthogonal Matching Pursuit (OMP) is fixed, thus limiting reconstruction precision. Therefore, in this study, we present a novel Reducing Iteration Orthogonal Matching Pursuit (RIOMP) algorithm that calculates the correlation of the residual value and measurement matrix to reduce the number of iterations. The conditions for successful signal reconstruction are derived on the basis of detailed mathematical analyses. When compared with the OMP algorithm, the RIOMP algorithm has a smaller reconstruction error. Moreover, the proposed algorithm can accurately reconstruct signals in a shorter running time.

Abstract:
Orthogonal Matching Pursuit (OMP) has long been considered a powerful heuristic for attacking compressive sensing problems; however, its theoretical development is, unfortunately, somewhat lacking. This paper presents an improved Restricted Isometry Property (RIP) based performance guarantee for T-sparse signal reconstruction that asymptotically approaches the conjectured lower bound given in Davenport et al. We also further extend the state-of-the-art by deriving reconstruction error bounds for the case of general non-sparse signals subjected to measurement noise. We then generalize our results to the case of K-fold Orthogonal Matching Pursuit (KOMP). We finish by presenting an empirical analysis suggesting that OMP and KOMP outperform other compressive sensing algorithms in average case scenarios. This turns out to be quite surprising since RIP analysis (i.e. worst case scenario) suggests that these matching pursuits should perform roughly T^0.5 times worse than convex optimization, CoSAMP, and Iterative Thresholding.

Abstract:
In this paper, we consider the problem of compressed sensing where the goal is to recover almost all the sparse vectors using a small number of fixed linear measurements. For this problem, we propose a novel partial hard-thresholding operator that leads to a general family of iterative algorithms. While one extreme of the family yields well known hard thresholding algorithms like ITI (Iterative Thresholding with Inversion) and HTP (Hard Thresholding Pursuit), the other end of the spectrum leads to a novel algorithm that we call Orthogonal Matching Pursuit with Replacement (OMPR). OMPR, like the classic greedy algorithm OMP, adds exactly one coordinate to the support at each iteration, based on the correlation with the current residual. However, unlike OMP, OMPR also removes one coordinate from the support. This simple change allows us to prove that OMPR has the best known guarantees for sparse recovery in terms of the Restricted Isometry Property (a condition on the measurement matrix). In contrast, OMP is known to have very weak performance guarantees under RIP. Given its simple structure, we are able to extend OMPR using locality sensitive hashing to get OMPR-Hash, the first provably sub-linear (in dimensionality) algorithm for sparse recovery. Our proof techniques are novel and flexible enough to also permit the tightest known analysis of popular iterative algorithms such as CoSaMP and Subspace Pursuit. We provide experimental results on large problems providing recovery for vectors of size up to million dimensions. We demonstrate that for large-scale problems our proposed methods are more robust and faster than existing methods.

Abstract:
The newly emerging compressive sensing theory in recent years has opened up a new path for the development of signal processing, which describes that it can reconstruct the original signal from a small amount of random sampling as long as the signal is sparse or compressible, which disobeys with the traditional Nyquist sampling theorem. Based on the study and summarize of the traditional matching algorithm, this paper presented a new adaptive orthogonal matching pursuit algorithm (AOMMP) for the reconstruction of the sparse signal. The algorithm divided each iteration into two stages for the choice of matching atoms, which accelerated the matching speed of the atom and improved the accuracy of the matching, ultimately led to exact reconstruction of the original signal. Finally, compared the AOMMP algorithm with the traditional OMP algorithm under the software simulation. Experimental results show that the AOMMP reconstruction algorithm is superior to traditional OMP algorithm on the reconstruction quality and the speed of the algorithm.

Abstract:
Abstract In order to well ensure reconstruction of the original signal, the traditional Nyquist sampling theorem requires that the sampling rate must be twice as much the highest frequency of the original signal at least, which causes a tremendous amount of calculation and the waste of resources. But the compressive sensing theory describes that we can reconstruct the original signal from a small amount of random sampling as long as the signal is sparse or compressible.Based on the research and summarization of the traditional matching algorithm, this paper presented a new adaptive space orthogonal matching pursuit algorithm (ASO MP) for the reconstruction of the sparse signal. I}his algorithm introduces an regularized adaptive and spatial matching principle for the choice of matching atoms with reverse thinking,which accelerates the matching speed of the atom and improves the accuracy of the matching, ultimately leads to exact reconstruction of the original signal. Finally, we compared the ASOMP algorithm with the traditional MP and OMP algorithm under the software simulation. Experimental results show that the ASOMP reconstruction algorithm is superior to traditional MP and OMP algorithm on the reconstruction quality and the speed of the algorithm.

Abstract:
As a greedy algorithm to recover sparse signals from compressed measurements, orthogonal matching pursuit (OMP) algorithm has received much attention in recent years. In this paper, we introduce an extension of the OMP for pursuing efficiency in reconstructing sparse signals. Our approach, henceforth referred to as generalized OMP (gOMP), is literally a generalization of the OMP in the sense that multiple $N$ indices are identified per iteration. Owing to the selection of multiple ''correct'' indices, the gOMP algorithm is finished with much smaller number of iterations when compared to the OMP. We show that the gOMP can perfectly reconstruct any $K$-sparse signals ($K > 1$), provided that the sensing matrix satisfies the RIP with $\delta_{NK} < \frac{\sqrt{N}}{\sqrt{K} + 3 \sqrt{N}}$. We also demonstrate by empirical simulations that the gOMP has excellent recovery performance comparable to $\ell_1$-minimization technique with fast processing speed and competitive computational complexity.

Abstract:
In this paper we define a new coherence index, named the global 2-coherence, of a given dictionary and study its relationship with the traditional mutual coherence and the restricted isometry constant. By exploring this relationship, we obtain more general results on sparse signal reconstruction using greedy algorithms in the compressive sensing (CS) framework. In particular, we obtain an improved bound over the best known results on the restricted isometry constant for successful recovery of sparse signals using orthogonal matching pursuit (OMP).

Abstract:
We show that if a matrix $\Phi$ satisfies the RIP of order $[CK^{1.2}]$ with isometry constant $\dt = c K^{-0.2}$ and has coherence less than $1/(20 K^{0.8})$, then Orthogonal Matching Pursuit (OMP) will recover $K$-sparse signal $x$ from $y=\Phi x$ in at most $[CK^{1.2}]$ iterations. This result implies that $K$-sparse signal can be recovered via OMP by $M=O(K^{1.6}\log N)$ measurements.

Abstract:
compressive sensing is an emergent field of signal processing which states that a small number of non-adaptive linear projections on a compressible signal contain enough information to reconstruct and process it. this paper presents the results of evaluating five measurement matrices for applying them to compressive sensing in a system using orthogonal matching pursuit (omp) to reconstruct the original signal. the measurement matrices were those implicated in compressive sensing as well as in reconstructing the signal. the hadamard-random matrix stood out within this group of matrices because the lowest percentage of error in signal recovery was obtained with it. this paper also presents a methodology for evaluating these matrices, allowing subsequent analysis of their suitability for specific applications.

Abstract:
Muestreo compresivo es una rama emergente del procesamiento de se ales, basada en el hecho de que un número peque o de proyecciones lineales no adaptativas sobre una se al compresible contiene suficiente información para reconstruirla y proce- sarla. En este artículo se presentan los resultados obtenidos al evaluar cinco matrices de medición para la realización de mues- treo compresivo en un sistema que utiliza el algoritmo orthogonal matching pursuit (OMP), para la recuperación de la se al ori- ginal. Las matrices de medición están implicadas tanto en el proceso de muestreo–compresión de la se al, como en la recons- trucción de la misma. Dentro de este grupo de matrices estudiadas se destacó la matriz Hadamard aleatoria, con la cual es po- sible obtener el menor porcentaje de error en la recuperación de la se al. Adicionalmente se presenta una metodología para la evaluación de estas matrices, que permita posteriores análisis de la idoneidad de estas para aplicaciones específicas. Compressive sensing is an emergent field of signal processing which states that a small number of non-adaptive linear project- tions on a compressible signal contain enough information to reconstruct and process it. This paper presents the results of e- valuating five measurement matrices for applying them to compressive sensing in a system using orthogonal matching pursuit (OMP) to reconstruct the original signal. The measurement matrices were those implicated in compressive sensing as well as in reconstructing the signal. The Hadamard-random matrix stood out within this group of matrices because the lowest percentage of error in signal recovery was obtained with it. This paper also presents a methodology for evaluating these matrices, allowing sub- sequent analysis of their suitability for specific applications.