Signal Sparse Decomposition Based On The Improved Matching Pursuit Algorithm

Sparse decomposition of signals have been a very important use in signal analysis and applications, such as signal composition, signal recognition and transmission. It is a new method of signal decomposition and signal can be expressed simply. Sparse decomposition of signal is a typical NP(Non-Deterministic Polynomial) problem, that the computational complexity is very huge. In most of the studies currently, matching pursuit(MP)algorithm is used to decompose signals generally, which is an iteration algorithm. MP algorithm can not reconstruct a signal exactly, but the signal can be expressed approximately. Compared with other algorithms of sparse decomposition, MP algorithm has an advantage in computational complexity and approximation effect which make it get more attention.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 ere. But the large computational cost is the bottleneck of sparse decomposition. To realize sparse decomposition lastly, researchers in and aboard have put forward many fast algorithms. In this thesis, the fast algorithms are studied to overcome computational randomness and also ensure the performance of signal decomposition.This Paper will introduce the basic theory of the signal decomposition and the sparse signal decomposition first. Then the theory and application of the sparse decomposition of signals in MP algorithm win be mentioned. To resolve the problem of large storage and huge computational complexity, a new sparse decomposition algorithm based on improved MP algorithm will be presented. With study of the atomic structure of over-complete dictionary and the conception of set partitioning, an algorithm with2-step search method is proposed to reduce computational complexity.In this paper proposed an improved MP algorithm of one-dimensional speech signal and an improved MP algorithm of two-dimensional image signal are proposed and verified at the same time.