Duality Theory And Stability Of L₁ Minimization Problem

Sparse optimization has been widely used in image processing,compressed sensing,machine learning and other fields.As is known to all,both in theory and algorithm,l₁-minimization problem is one of the important tools of sparse optimization problems,which provides a new method for solving sparse optimization problem and the train of thought.This paper mainly focuses on the establishment of the duality theory ofl₁-minimization problem and the application of sparse optimization in compressed sensing problem.The existence theory of the saddle point is obtained by theoretical analysis of the l₁-minimization problem,and the stability condition of the 1-bit compressive sensing model is obtained by using thel₁-minimization method and problem reconstruction.On the one hand,we mainly study the existence theory on saddle points forl₁-minimization problem.Firstly,to overcome the non-smoothness of 1-norm,we translate l₁-minimization problem to an optimization programming with linear cost function by introducing a new variable.Secondly,based on a new augmented Lagrangian function,the relationship on saddle points between the primal problem and the translated problems,associated with their duality problems,is established.It allows us to establish local saddle points by taking into account of second-order sufficient conditions.Finally,global saddle points is established by using two different approaches.One is requiring that the optimal solution is unique.This assumption can be further removed in our another approach by using the perturbation analysis of primal problem.On the other hand,1-Bit Compressed Sensing(CS)is an important sparse optimization problem.Taking this as the research background,we focus on the stability theory for 1-Bit CS with quadratic constraint.The model is rebuilt by reformulating sign measurements by linear equality and inequality constraints,and the quadratic constraint with noise is approximated by polytopes to any level of accuracy.A new concept called restricted weak RSP of a transposed sensing matrix with respect to the measurement vector is introduced.Our results show that this concept is a sufficient and necessary condition for the stability of 1-Bit CS without noise and is a sufficient condition if the noise is available.The structure of this paper is as follows.The first part mainly describes the research background of thel₁-minimization problem,the existence of saddle point and 1-bit compressed sensing,the research status at home and abroad,some necessary preparatory knowledge and the main innovations.In the second part,the existence theory on saddle points forl₁-minimization problem is given.In the third part,the stability analysis of 1-bit compressed sensing model in sparse data reconstruction is presented.The fourth part is the summary and outlook,which explains the follow-up work and research.