Isometric Analysis Of Matching Pursuit Constraints In Compressive Sampling And Its Application

Compressive Sampling (CS) is an emerging area is signal processing domain these years. Compared with traditional sampling, CS integrates compression into the sampling process, which significantly reduces the data for transmission and storage. How to recover the original signal from fewer observations is the key problem in CS research. Previous research found that if the measurement matrix satisfies the Restricted Isometry Property (RIP), it is possible to recover the signal exactly. Among existing methods, matching pursuit algorithms attract many researchers because of their simple structure and low computational complexity. This dissertation first analyzes existing matching pursuit algorithms, then attempts to improve the performance of matching pursuit algorithms. The dissertation focuses on the following work:1) The Orthogonal Matching Pursuit (OMP) algorithm is analyzed using Restricted Isometry Property (RIP). OMP views the observation signal as a representation of atoms in a dictionary, and selects the atom best matched with the residue iteratively. We achieve the upper or lower bound of inner products between atoms and the residue using RIP. A sufficient condition for recovering the original signal is proposed and proved. We further analyze the performance for recovering strongly decaying sparse signal, and proved that OMP can achieve better performance. For block-sparse signals, similar technique is used to prove that Block-OMP can reconstruct the original signal better compared to OMP. OMP is a typical matching pursuit algorithm widely used in various applications. In-depth analysis can help the application and improvement of the algorithm.2) An algorithm named OMP-Thresholding (OMP-TH) is proposed to recover signals with partially known support. In the previous analysis of OMP, we found that in the later iterations, weaker RIP of the sampling matrix is required for successful selection of the correct atoms. OMP-TH, which performs the same as OMP in the matching pursuit stage, attempts to get a set containing all atoms representing the observation signal. In the thresholding stage, the algorithm using the atoms to approximating the observation signal and removes the atom with coefficients close to zero. We prove that the more elements of the true support set the initial estimated set contains, the weaker RIP the sampling matrix requires, which means fewer observations are required to reconstruct the signal exactly. Experiments exhibit that OMP-TH can recover original signal with much fewer samples3) An algorithm named Markov Tree OMP (MT-OMP) is proposed for CS image reconstruction. OMP assumes no prior knowledge of the sampling signal other than sparsity. Actually the structure property of sparse signal can be utilized to recover the original signal. The wavelet transform of natural image is known to possess statistical property. For example, coefficients with large amplitude usually occupy the same position across different scales. MT-OMP select atoms using Markov Tree model for wavelet coefficients. Experiments illustrate that the algorithm can select atoms correctly, therefore the quality of the reconstructed image is higher.4) An algorithm named Sparsity Adaptive Subspace Pursuit (SASP) is proposed. Subspace Pursuit (SP) considers the inner products between a group of atoms and the residual signal, while OMP consider only one atom each time. Therefore SP can recovery the signal with fewer observations. SP expects that the sparsity level of original signal is known, or the performance degrades. SASP obtain an initial estimation of the signal sparsity level, and then increases the estimated sparsity iteratively. SASP solves the problem of SP that the true sparsity is required. Experiments results show that SASP can recover original signal with low computational complexity.