Stagewise Matching Pursuits Of Sparse Representaitions

Recently, the sparse signal representation has attracted great attentions in signal processing, along with the development of various of the mathematical transform technologies, such as the Fourier Transform, the Wavelet Transform and the Singular Value Decomposition. Meanwhile, sparse representation theories have been widely applied in many research areas like noise reduction, data compression, feature extraction, pattern classification and blind source separation. Furthermore, sparse represenation directly motivated the compressed sensing theory for high-dimension information processing, which has been recognized as one of the greatest theoretical innovations in information theory since Shannon's sampling theory was published in 1950s. Hence, researches on sparse representations play a fundmental role in the extension of signal processing theories.The emphasis of this thesis is laid on the sparse representation of signals in the underdetermined system. Given a dictionary of elementary signals, called atoms, and an input signal which can be modeled with the sparse representation, i.e. is a linear combination of only a few atoms, to obtain this sparse representation is equivalent to solve the optimization problem : min ? . . . has been proven NP-hard. However, recent researches show that some methods, such as Basis Pursuit (BP) and Orthogonal Matching Pursuit (OMP), can approximate or solve exactly, if is sufficiently sparse and the coherence parameter of is small enough. We call this property of these methods exact recovery. The exact recovery capability of most existing methods are influenced by the dictionary's coherence, which leads to these methods'high requirement of the sparsity of or high computation complexity. In order to change this status, this dissertation offers the following contributions based on stagewise matching pursuits (SMP):(1) The first contribution concerns the exact recovery condition. The performance of many existing pursuit methods are limited by the dictionary's coherence because they are based on the l₁ /l₀ equivalence, i.e., the necessary and sufficient conditions of the solution of the optimization problem : min . . , being equivalent to the one of ( ). In order to break the limitation of the dictionary's coherence, Chapter 2 presents the l₂ /l₀ equivalence, i.e., the necessary and sufficient conditions of the solution of the optimization problem : min . . , being equivalent to the one of . Since the solution of only concerns the linear dependence of the atoms in , the performance of the methods based on l₂ /l₀ equivalence is free from the dictionary's coherence. If the active set Γselected by SMP from satisfies ? /? equivalence, then SMP solve . We callΓis a pseudo-frame depending on the input signal.(2) We concern the atoms selection strategy (ASS) of the existing greedy pursuit methods. SinceΓis built according to the ASS, the quality of the ASS determines the performance of the pursuit methods. In Chapter 3, we first review the ASS of the existing pure greedy methods and their inherent connections and draw a conclusion that the basis pursuit problem can be solved by matching pursuit under certain circumstance. Then, we analyze the ASS of the SMP, and point out that the threshold value of the SMP is difficult to control although they have weak dependencies on the dictionary coherence.(3) In order to make it easy to select the threshold value of the SMP, we propose a new method, Stagewise Ridge Pursuit (StRP), for isolated singular signals and multi-scale dictionaries in Chapter 4. The main ideas are as follows: first, extract the ridge of the isolated singular signals in the wavelet transform domain; second, select the atoms located in the ridge line into the active setΓ; last, solve the orthogonal projection of the input signal inΓ. It's easy to prove thatΓis a pseudo-frame depending on and ? /? equivalence is satisfied. Hence, the analysis results of StRP's must be ? minimization. Numerical experiments also show the advantages of this approach.(4) In order to overcome the difficulty of selecting threshold value of the SMP for common signals and dictionaries, we propose another SMP method, Local-competition-based Orthogonal Matching Pursuit (LStOMP), in Chapter 5. The core idea is based on the assumption that the important atoms that have larger inner products with the input signal and their neighbors in the space or frequency domain might be equally important. We can make up two or more dictionary patterns by these atoms and select the optimal one based on the local competition mechanism, which can be used to avoid that the atoms having smaller inner products with the input signal could never be selected. Meanwhile, backward greedy algorithms are also adapted to eliminate the redundancy of the active set. LStOMP has less total iterative steps and lower total computation costs than many existing methods, although the computation costs of LStOMP is higher in one iteration step. Numerical experiments show that LStOMP has better sparsity-preserving, anti-coherence and convergence than existing methods.Since all of the SMP are based on Orthogonal Matching Pursuit (OMP), we concentrate on the iterative methods for solving OMP in Chapter 6. First, we review the existing fast iterative methods for solving OMP, extend and improve the Conjugate Gradient Pursuit, and compare the computation requirements they need in each iteration step. Second, we point out that the iterative methods for solving OMP cannot be used to solve the subproblems of the SMP ifΓis rank deficient. However, the classical iterative methods, such as SYMMLQ,MINRES,LSQR, which is often used to solve the rank deficient systems, are not sparsity-preserving. It's suspended to solve the SMP's subproblems with fast iteration.