Research On Algorithms For MP-Based Signal Sparse Decompositon

Signal sparse decomposition based on Matching Pursuit(MP) has been applied to many areas such as data compression, signal feature extraction, time-frequency analysis and etc. But it is a NP difficult problem. The large computational cost is the bottleneck of sparse decomposition. To realize sparse decomposition fastly, researchers in and aboard have put forward many fast algorithms such as genetic algorithm based MP, ant colony algorithm based MP and etc.. However, these new algorithms are based on computational intelligence, in some cases they are not inapplicable because of the randomness of the computational intelligence, In this thesis, the fast algorithms are studied to overcome computational randomness.In this thesis, the sparse decomposition is introduced firstly, the characteristic and key problems of sparse decomposition are mentioned. Afterwards the MP is introduced. Compared to other sparse decomposition algorithm, MP is easy to understand and to realize, but still has the problem of huge memory, huge computational cost. This thesis deals with these two aspects.Aiming at the problem of the large over-complete dictionary storage, a new method is proposed based on signal set partitioning method. With the equal relationship, the over-complete dictionary can be partitioned into sub-dictionaries, the intersections of which are null. Each sub-dictionary can then be represented by only one selected corresponding atom. By partitioning the over-complete dictionary, the computational space complexity in signal sparse decomposition can be degraded a lot, while the decomposition results are kept unchanged.To the problem of great computation load, a new sparse decomposition algorithm that utilizes radix-2 FFT is presented based on analysis of structure property of the over-complete atom dictionary used in signal sparse decomposition. By making use of the structure property, this new algorithm balances very well computer's speed and memory, the advantage of radix-2 FFT is presented. The new algorithm improves a lot the speed of signal sparse decomposition. According to...