Research On Optimized-Algorithms For Signal Sparse Decomposition Based On MP With FFT

Signal sparse decomposition based on matching pursuit (MP) has widely application in many fields, such as time-frequency analysis, signal detection, signal feature extraction, data compression, image repair and so on, and it shows good performance. While the great complexity of signal decomposition becomes a great bottle-neck, which make it can not be utilized in more fields. In order to realize fast MP decomposition, many researchers have done a great deal of researches. Meanwhile, they propose some fast algorithms, such as genetic algorithm (GA), ant colony optimization (ACO), tree searching algorithm and so on. While those algorithms are based on probability in nature, so the randomization will be present in the procedure of computation. Though those algorithms can realize signal decomposing, it can not be utilized in some cases, when the demand for performance is very high. However, the proposed algorithm based on MP can realize high speed, at the same time, the performance of the signal decomposition is assured. This is the key point of the paper.The main work is carried through based on those problems, that is the computation complexity is too great based on MP decomposition, and the storage amount of the over-complete dictionary of atoms is too great. The character of signal sparse decomposition and problems to be solved are analyzed at first. And then the basic principle of MP decomposition is addressed. Meanwhile the paper highlighted the accelerating algorithm based on MP decomposition——the standard MP algorithm based on Fast Fourier Transform (FFT). Besides the improvement of MP algorithm is based on that.First, it compares the two algorithms using of FFT to achieve Sparse Decomposition (based on circular convolution and linear convolution of the MP-based method) in the two aspects of computational complexity and performance, in order to achieve flexible options according to necessary in the actual dealing with problems.Second, because there are some shortcomings in the MP algorithm based on FFT, dictionary is divided into disjoint set according to their phase parameters. Such kind child dictionary's projection coefficients can be expressed linearly, which can decrease the generation scale of the dictionary and the computation complexity of decomposition without influencing the performance. Dictionary with modulation parameter are divided into disjoint set according to their frequency parameters. Translation of the Fourier atoms can seize the generation scale of few dictionaries and the computation complexity of decomposition without influencing the performance. Combined with the two methods, we use a tree structure set partitioning methed to decrease further the computation complexity of decomposition.Then, for the problem, that is the storage amount of the atoms is too great. According to the supporting character of the gaussian window function, a new method is proposed to decrease storage scale of the anisotropic refinernent atoms dictionary. That is compressing the planar atoms using the improved Quad Tree Compression methods. Experiment finds that it can remain keeping a good quality when being a big ratio of compression with atom dictionary.In addition, the original multi_atoms rapid matching pursuit (MAMP) decomposition algorithm is improved in combination with MP decomposition based on FFT algorithm. Through a new methed to partition the dictionary into disjoint sub dictionaries and select the best atom policy. Then, decomposition speed can be improved significantly on the assumption that the decomposition performance is insured.