Improvements On Optimal Atom Selection Strategies Of Matching Pursuit And Blind Sparsity Reconstruction Algorithms In Compressed Sensing

Compressed sensing can sample signals at a rate far below Nyquist rate, and it’s a new tool in signal processing. In the l0norm based algorithms, the atom matching pursuit mainly applied greedy search, their key techniques are (1) optimal atom selection and matching criteria;(2) accurate estimate of signal sparsity. Atom selection strategies can be divided into single atom hit and a batch selection of atoms, while criteria include residual matching, current best observation and global error minimization. In addition to the atom selection related to efficiency and fault tolerance, matching criteria determine directions of atom search which approaches an optimal solution. This thesis mainly focuses on efficient atom selection and robust reconstruction of sparsity unknown signals.Main contributions include:1) To improve the accuracy of atom selection, a look-ahead and backtracking orthogonal matching pursuit (LABOMP) algorithm is proposed. In early iterations a set of candidate atoms is chosen by look ahead verification, on the contrary, an interval backtracking mechanism is triggered by a threshold in later iterations to prune error atoms. Experiments show that, for sparse signals and compressive voice, the mean exact reconstruction probability (MERP) of LABOMP is12.5%～31.3%higher than that of LAOMP, where the latter uses only the look-ahead strategy, which indicates the probability of finding a global solution is improved.2) For rapid convergence of LABOMP, a regularized LABOMP (RLABOMP) algorithm is proposed. Note that the CS reconstruction is an ill-posed solution and the difference between criterion of residual matching and criterion of global matching, multiple’good’ atoms could be regarded as equivalent candidate. Thus an equal opportunity constraint is introduced to regularize the recruitment of candidate atoms to include the atoms with similar performances, to promote fault tolerance and accelerate the convergence. Experiments show that the number of iterations of RLABOMP for choosing K atoms is42.90%～54.28%of that of LABOMP and62.85%～71.57%of that of LAOMP. However, MERP of RLABOMP is9.27%～25.12%lower than that of LABOMP and1.91%～10.80%higher than LAOMP. Obviously RLABOMP is better than LAOMP and balances the efficiency and the reconstruction performance comparing to LABOMP.3) To increase the accuracy and speed of atom selection, a generalized optimal orthogonal matching pursuit (GOOMP) algorithm is proposed. Improvements are (1) using optimal matching criterion of current observation signal to guarantee the solution can minimize matching error.(2) selecting L optimal atoms in batch to guarantee higher fault-tolerant ability. For sparse signals gOMP algorithm using current best observation criteria improves its MERP by3.16%～10.80%, OOMP algorithm selecting L optimal atoms in batch exactly reconstruct signals with number of iterations which is one third of that of OOMP, and improves MERP by31.26%～37.54%.Furthermore, this thesis proves the sufficient condition of GOOMP algorithm exactly reconstructing original signals in K iterations is:On the premise of the independence of correct atoms, unselected atoms are projected into complement space spanned by selected atoms and then normalized, then each projected and normalized error atom is projected into space spanned by all projected and normalized error atoms, each l1norm of projecting coefficient vector is smaller than1.4) Based on residual matching and atom coefficients thresholding, an improved reconstruction algorithm for blind sparsity signal is proposed. Firstly, the relationship between atom selecting threshold and sparsity in backtracking-based adaptive orthogonal matching pursuit (BAOMP) algorithm is analyzed. Then aimed at shortcomings of steep rise of residual norms and estimated signal errors aroused by selected error atoms in later iterations of BAOMP, an improved algorithm IBAOMP is proposed. When the energy of estimated signal is closed to that of target signal, by increasing atom selecting threshold according to80-20principle to control error atom selections and capacity of candidate atom set, IBAOMP effectively eliminate the phenomenon of periodic steep rise of errors.In conclusion, the researches in this thesis on atom selecting methods and blind sparsity signal reconstruction in CS give the following results:LABOMP with the interval backtracking mechanism improves the probability of hitting correct atoms, by using regular atom selection method, RLABOMP algorithm significantly improves convergence speed of LABOMP, and GOOMP algorithm can not only improve MERP but also reduce the computation time. Besides, for blind sparsity signals, IBAOMP algorithm avoids reconstruction blindness when sparsity information is missing by threshold adjustment mechanism, and ensures the estimated signal gradually approaching target signal.