Research Of Intelligent And Random Methods In Sparse Recovery

Compressed sensing(CS) is a hot topic around the areas of international mathematics and information processing at present. With great effort of many scholars, this technique has formed a relatively complete system of theoretics, algorithms and applications. The core of this technique is to model and solve the sparse recovery problem. The thesis locates at the research of algorithms for solving the sparse recovery problem. To overcome the drawbacks and obstacles faced by present algorithms, this thesis proposes a class of heuristic intelligent and random modified algorithms, combining with the models and thoughts of greedy pursuit strategies. These algorithms includes the swarm evolution algorithm based on the structure of particle swarm optimization(PSO) and the randomly enhanced adaptive subspace pursuit(REASP) method. The main work and innovations are embodied as follows.Firstly, the thesis introduces the basic achievements in theories, algorithms and applications of CS in recent years. Theoretically, it mainly performs the basic process of CS and bounds the number of measurements with guaranteed recovery quality. Algorithmically, it analyzes the model, process, convergence, computational complexity as well as merits and demerits of approximate algorithms including greedy pursuit methods, convex relaxation methods and derived penalty function methods. In applications, it briefly lists three typical problems, i.e., single-pixel camera, magnetic resonance imaging(MRI) and radar imaging, then analyzes why CS is successful within them respectively.Secondly, the thesis combines the background of randomized and computational intelligence optimization algorithms and discusses some important concepts, typical algorithms and empirical results in them. For randomized algorithms, it mainly introduces the concepts and thoughts brought by them, which consist of classifications, computational complexities and universal principles in applications. And for computational intelligence optimization algorithms, it specifically describes three representatives of them, i.e., the genetic algorithm(GA), the PSO algorithm and the ant colony optimization(ACO) algorithm. In the end, differences and relations between the two main categories are presented.Thirdly, the thesis analyzes the flaws and restrictions of two major strategies for solving the sparse recovery problem at present, including convex relaxation methods and greedy pursuit(GP) methods. Hence, it proposes a sparse recovery algorithm based on swarm evolution. In the model of greedy pursuit methods, this algorithm first achieves the relations of the signal and its support through the least square(LS) method, and transforms the model into the fitness function of PSO. Then combining with the thoughts of GP methods, it defines the velocity, position as well as their initialization and updating mechanism of a particle within the structure of PSO. Theoretical and experimental results show that the proposed algorithm overcomes the drawbacks of GP and convex relaxation methods, which can not recover Gaussian signals of large sparsity levels. The algorithm also realizes a balanced way on the efficiency and ability of recovery. Especially, the structure of the algorithm has a natural parallel ability, which leads to its use on distributed processors for a higher efficiency.Fourthly, the research focuses on the similarities and differences among the widely used GP methods at present, and analyzes the drawbacks of the two major strategies in terms of the stable sparse recovery problem in the presence of noisy perturbations. Similarly based on the sparse recovery model for GP methods to solve, the thesis involves a random strategy for the process of atoms’ selection and proposes the REASP method. It first describes the way of implementation as well as the intention of each step in the algorithm, and then analyzes the superiorities of REASP for solving this model. Theoretical results and numerical experiments demonstrate that compared to the past algorithms, the proposed algorithm avoids ill-posed problems to a greater extent and has a greater ability of recovery, despite a bit higher but acceptable computational complexity.