Research On Generalized OMP Algorithm And Dictionaries Construction In Compressive Sensing

In compressive sensing theory, sparse or compressive signals can be recovered fromits nonadaptive and insuffcient linear measurements with high probability. Greedy al-gorithms, convex optimization algorithms and nonconvex optimization algorithms weresuccessively proposed to reconstruct sparse signals in compressive sensing. To derivesuffcient conditions for sparse signal reconstruction algorithms is one of important topicsin compressive sensing. Suffcient conditions for sparse signal recovery algorithm oftendepend on the characteristics of measurement dictionary. Therefore, to construct mea-surement dictionaries with desired properties is a valuable research direction in compres-sive sensing. This dissertation mainly analyzes generalized Orthogonal Matching Pursuit(g OMP) algorithm and designs dictionaries in compressive sensing. The contributions ofthe dissertation are listed as follows:Firstly, suffcient conditions are given for g OMP algorithm to recover support of s-parse signal in both noiseless and noisy cases. Moreover, error bound of the recoveredsparse signal is given. Besides general sparse signal, suffcient conditions for strong de-caying sparse signals are also derived. Compared with the existing suffcient conditionsof g OMP algorithm, the proposed conditions are more relaxed. As g OMP algorithm isa generalization of OMP algorithm, the conditions proposed for g OMP algorithm can beeasily modified to fit OMP algorithm.Secondly, dictionaries construction algorithm is proposed. Sensing dictionary canbe incorporated in greedy algorithms and it is proved that sensing and measurement dic-tionaries with small coherence can improve sparse signal recovery performance of greedyalgorithms. Based on alternating projection method, sensing and measurement dictionar-ies are constructed to make their type Gram matrix near the set of ideal Gram matrix.The constructed sensing and measurement dictionaries are with small mutual coherenceand small cumulative mutual coherence. Simulation experiments are utilized to prove theperformance improvement of both OMP and g OMP algorithms when incorporated withdesigned sensing and measurement dictionaries.Thirdly, we propose an algorithm to design block sensing and measurement dic-tionaries in block compressive sensing. The proposed algorithm alternatively optimizesblock sensing and measurement dictionaries. In each iteration, optimization of one atomof block sensing or measurement dictionary can be formulated as a linear constrain-t quadratic programming problem and therefore the closed form solution can be easilyderived. According to the expression of the solution, a fast way to calculate the atom isgiven to reduce computational complexity. The designed block sensing and measurementdictionaries are with small sub and intro block mutual coherence. Simulations validatesthe performance improvement of BOMP algorithm if the designed dictionaries are used.Finally, partial Fourier dictionary construction algorithm is given to design partialFourier dictionary with small coherence. Complex Fourier matrix is converted to real oneand each row is used to calculate sub Gram matrix. Row selection of partial Fourier dic-tionary are based on correlation of sub Gram matrix and residual signal. When a set ofsub Gram matrix are selected, alternating projection method is utilized to calculate affnecombination of sub Gram matrix and its projection on the set of ideal Gram matrix. Withthese two matrix, residual signal can be updated. Based on special structure of Fouriermatrix, a fast method is given to calculate the affne coeffcients of the selected sub Grammatrix. Empirical experiments indicate that the designed partial Fourier dictionary is withsmall coherence and small cumulative coherence. With the designed dictionary, perfor-mance of OMP algorithm improves. It is necessary to point out that the designed partialFourier dictionaries can be used in any applications that incoherent partial dictionaries areneeded.