Researches On Structured Optimization Models And Related Algorithms For Sparse Data Recovery Problems

Sparse data can be sufficiently compressed to save storage space and reduce the amount of transmission. Data recovery is to restore the interfered or damaged data into real data. Sparse data recovery problems exist widely in real applications, e.g.,sparse signal compression sensing, low rank matrix completion, image restoration based on the total variation regularization, and so on. How to efficiently restore the specific information uniquely and robustly from the ill-conditioned linear inverse problem is an important topic of the concern of many researchers. Based on the special structure of the models associated to sparse data recovery problems, such as the separability of the objective function, the sparseness of the vector and the low rank property of the matrix, some structured optimization models were constructed according to the actual needs and problem characteristics, and then some related algorithms were proposed and verified to have better performance.For the structured optimization models of sparse data recovery problems, this dissertation is devoted to developing the corresponding fast algorithms for separable convex optimization problems with two, three and four block variables, respectively, and proving the global convergence of the proposed algorithms. Numerical experiments show that the proposed algorithms are valid and practicable for sparse signal compression sensing, low-rank matrix completion, image restoration,etc. The main works of this dissertation are as follows:First, a partial proximal alternating direction method based on a line-search technique(abbreviated to LSPPAD) is proposed for solving a class of structured optimization problems with two block variables. The proposed method makes full use of the special structure of problems under consideration. At each iteration,two sub-problems are solved alternately: one is solved by a proximal point method while the other don’t need to add the proximal term, both subproblems are solved inexactly by using some line search technique. Under suitable conditions, the global convergence of the LSPPAD method is proved. Some numerical results on compressed sensing and matrix completion show that the proposed method has better performance.Secondly, a parallel-alternating hybrid splitting method(HSM) is proposed for a class of smooth Tikhonov regularization problems with three block variables. At each iteration, the proposed method solves three subproblems and updates the two multipliers. The first two subproblems are solved by a parallel splitting method,and the Lagrange multipliers associated to these two block variables are updated immediately. Then, the third subproblem is solved by using the latest results of the first two subproblems and adopting the iteration of the alternating direction method. Finally, the Lagrange multipliers associated to the last two block variables are updated. The proposed algorithm is a skillful mixture of the parallel splitting method and the alternating direction method. The global convergence of the proposed method is proved under some suitable conditions. Some numerical experiments on the Discrete Ill-Posed Problems(DIPPs) show the validity and efficiency of the hybrid splitting method. The HSM is further extended to the TVIR image restoration model, and experimental results show that it is also applicable.Finally, an inexact group alternating direction method of multipliers is proposed for a class of structured optimization problems with four block variables.The proposed method divides four subproblems into two groups according to the workloads. Each group contains two subproblems with the same workloads. The method executes a parallel splitting method in each group and an alternating direction method between the two groups. All the iterative sub-problems are solved inexactly. Under some suitable conditions, the global convergence of the proposed method is proved. Compared with the existing group splitting methods, the proposed method allows the subproblems to be solved inexactly, hence it is possible more practical. This method can be directly extended to solve the analogous problem with multi-block-variables.The dissertation is organized as follows. Chapter 1 briefly introduces some typical sparse data recovery problems, including compressed sensing, matrix completion, and image restoration based on total variation, and the current research status. Chapter 2 summarizes some basic knowledge required in this dissertation.Chapter 3 to Chapter 5 are the main parts of this dissertation. In these chapters, some operator splitting algorithms are proposed for solving the separable structured convex optimization problems with two, three and four block variables,respectively. The proposed methods include a partial proximal alternating direction method based on line search, a parallel-alternating hybrid splitting method,and an inexact group alternating direction method of multipliers. Global convergence of all the proposed methods is proved under some suitable conditions.Numerical experiments show that, these methods are valid and applicable for their related problems. Finally, the conclusion part summarizes the research results of this dissertation and prospects the future research.