Pursuit And Generalized Approximate Message Passing Algorithm

With the coming of big data age, the demand of high dimensional data processing technique increases fast. It has pushed the research of sparse signal processing and compressed sensing powerfully, especially the development of highly efficient sparse reconstruction algorithms. In response to this trend, we focus on the research of classical?0 norm optimization algorithm and generalized approximate message passing(GAMP)algorithm, which is attractive to ever-increasing researchers. To solve the divergence problem of approximate message passing(AMP) type algorithms in non-zero mean and small variance dictionary matrix scenario, Three improved GAMP algorithms have been proposed in this work. To propose the second improved GAMP algorithm, two new ?0norm matching pursuit algorithms have been pre-proposed. Furthermore, the second improved GAMP algorithm introduces the marginal posterior probability variation of each entry of the sparse vector to find the non-zero elements indexes, it can be regarded as a new pursuit process. This pursuit process differs from the matching pursuit process which uses correlations between the residual and the columns of the dictionary matrix.The main innovation of this work includes four points:1.A matching pursuit GAMP(MPGAMP) algorithm has been proposed, which finds the support of a sparse vector sequentially by matching pursuit process, and then obtains the amplitudes on the support by a fixed support GAMP(Fs GAMP) algorithm. With this method, the robustness of AMP type algorithms is improved significantly. The convergence has been analyzed by a construction process to make a factor graph.2.Since orthogonal matching pursuit(OMP) algorithm can not remove incorrect non-zero element index in the pursued support, two new matching pursuit based methods have been considered to overcome this flaw. These two methods randomly shuffle and update support elements, termed random splitting support orthogonal matching pursuit(RSSOMP) and random regularized matching pursuit(Rr MP), respectively. The latter is an improvement of the former. The convergence of Rr MP has been proved mathematically, and the convergence conditions of it have been provided.3.The Rr MP algorithm has been combined with the fixed support GAMP(Fs GAMP)algorithm. The new algorithm is termed random regularized matching pursuit generalized approximate message passing(Rr Mp GAMP). The convergence of FsGAMP has been analyzed by replica method, and the convergence conditions of it have been provided.4.The posterior marginal probability variation of each entry of a sparse vector in the estimation process has been utilized to improve the Bernoulli-Gaussian prior GAMP algorithm, this reversion can be regarded as a kind of pursuit. And then the Fs GAMP could be used to estimate the amplitudes on the support.Both simulation data and real-world data are used as input to investigate and verify the properties of these algorithms. Results show that they can reconstruct the sparse signal of compressed sensing problems in more general dictionary conditions.