The Study of Orthogonal Matching Pursuit Using Restricted Isometry Property in Compressive Sensing

• 1、Department of Electronics Engineering, Fudan University, ShangHai 200433
• 2、Department of Electronics Engineering, Fudan University, Shanghai, 200433

Abstract：Orthogonal Matching Pursuit (OMP), which attempts to find the sparse representation of the observed signal from over-complete dictionary, is a typical greedy method used for Compressive Sampling (CS) signal reconstruction. Using Restricted Isometry Property (RIP) in the Compressive Sampling framework, this paper gives an analysis of the algorithm and explores the method to improve the performance. Matching pursuit uses the inner product between the atom and the residue as criteria to select atoms. According to which set the atom belongs to, the upper or lower bound of the inner product can be achieved. Combined with the criteria, a sufficient condition for exact reconstruction can be proved. Similar results can be proved for successful recovery of strong decaying signal and block-sparse signal. The analysis and conclusion can strengthen the understanding of OMP and be extended to other matching pursuit algorithms.

Keywords： Compressive Sampling (CS ) Orthogonal Matching Pursuit (OMP) Block Sparse Signal Restricted Isometry Property ( RIP)