Some Algorithms And Applications For Sparse Signal Recovery Problem

Sparse signal recovery problem has been a hot topic in the field of compressed sens-ing which is a new research direction in recent years,here sparse refers to the most of the elements of a signal are zero.It has a wide range of applications in signal processing,medical imaging,radar systems as well as the interdisciplinary fields where the sparse features of a signal or image are exploited,and has attracted extensive attention and re-search in recent years.Some fast reconstruction algorithms for sparse signal recovery problem and its applications in image processing are systematically studied in this dis-sertation,including the analysis and improvement to the orthogonal matching pursuit?OMP?and the alternating direction method of multipliers?ADMM?,and the fast recon-struction algorithm for analysis sparse recovery problem and total variation?TV?model.Firstly,we investigate sufficient conditions for the recovery of sparse signals vi-a the OMP algorithm.As the main representative of the greedy algorithms,OMP has the advantages of small computation and fast reconstruction speed,but it often fails in reconstructing sparse signals.Therefore,in the noiseless case,we present a novel suffi-cient condition for the exact recovery of all k-sparse signals by the OMP algorithm,and demonstrate that this condition is sharp.Generally,the computation for the restricted isometry constant?RIC?in these sufficient conditions is typically difficult,therefore we provide a new condition which is not only computable but also sufficient for the exact recovery of all k-sparse signals.In addition,we also consider the problem of identifying significant components in the case where some of the nonzero components are possibly small.It is shown that in this case the OMP algorithm will still select all the significant components before possibly selecting incorrect ones.Moreover,with modified stopping rules,the OMP algorithm can ensure that no zero components are selected.Secondly,in view of the sparse signal recovery problem can be modeled as a con-vex relaxation problem which can be efficiently solved by ADMM in many cases,and inspired by the inexact proximal point algorithm and the inexact augmented Lagrangian method,we study an inexact version of ADMM for solving two-block separable linear-ly constrained convex optimization problems.Specifically,the two subproblems in the classic ADMM are allowed to be solved inexactly by certain relative error criteria,in the sense that only two parameters are needed to control the inexactness,which overcomes the nonnegative summable sequences should be chosen to control the error.Related convergence analysis are established under the assumption that the solution set to the the KKT system of the problem is not empty.Numerical results on solving the l₁/l₁-regularization problems derived from the application of sparse signal recovery are also provided to demonstrate the efficiency of the proposed algorithm.Preliminary numerical results show that the inexact ADMM with relative error criteria is much faster than the classic ADMM.Thirdly,we propose a new method based on accelerated alternating minimization?AAM?for analysis sparse recovery problem.This method is extremely attractive as?1?it is very simple and computationally efficient,?2?it exhibits a fast convergence rate,?3?it is flexible and amenable to many kinds of reconstruction problems.We estab-lish the connection between the classical alternating minimization?AM?method and the well-known proximal gradient?PG?method.Thus combining the accelerated prox-imal gradient?APG?method with the Moreau proximal smoothing technique,a new smoothing-based AAM?SAAM?method,which can obtain an ?-optimal solution with-in O?1/??iterations,is designed.Numerical experiments on randomly generated data and real images,including the comparison with the stat-of-the-art solvers,show that this method compares favorably with those solvers.Finally,based on the classical quadratic penalty approach,a new decomposition-based accelerated alternating minimization?DAAM?method is proposed for reconstruct-ing images from blurry and noisy observations with TV regularization,it not only pre-serve the computational simplicity but also can exhibit the fast convergence rate.We es-tablish the equivalence between the DAAM and the APG method and show that DAAM can obtain an ?-optimal solution within O(1/?^1.5)iterations.Preliminary numerical ex-periments on images with various types of blurs are presented to demonstrate the effi-ciency of the proposed method.Our numerical results indicate that the proposed method is?1?indeed faster than the classical AM method and share a significantly better conver-gence rate,?2?and better than some state-of-the-art solvers.